solvi.search¶
Search over alternatives: candidates (a list, a dict of domains, a depth-first Tree, or a space read from the facts)
run through a System's checks, the best kept by an objective, partial candidates pruned by failed hard checks and a
bound, a budget of asks, a record of what was searched and when the result is exact.
Search over alternatives: candidates run through a System's checks, the best kept by an objective — a meeting slot, an order of cities, a day of meetings, an assignment — with pruning of partial candidates by failed hard checks, a bound, a budget of asks, and a record of what was searched.
from solvi.search import Tree, search
run = search(system, {"problem": text}, "accept",
space=lambda facts: Tree([], lambda order: [order + [c] for c in facts["trip"].cities if c not in order],
complete=lambda order: len(order) == len(facts["trip"].cities)),
into="order", prune=["direct_flights", "events_kept"], keep=2)
run.best, run.value, run.response # the best accepted candidate, its objective, its Response (asked in full)
run.exact, run.why_exact # whether the search can say it is the best, and why (or why not)
run.asked, run.rejected, run.pruned # what was searched: asks, rejections and cuts by check
run.replay(system) # the winner's trace replays and is accepted; its objective recomputes
A candidate is given to the System under into (or, from a dict of domains, as several given facts) next to state,
and the System is asked question. It is accepted when accept says so — as in solvi.refine: "checks" (default: every
hard check that governs the question was evaluated and passed), an answer or a list of answers, or a function of the
Response — and the question did not abstain: a candidate the System could not decide is never chosen.
The space
a list, a tuple or any iterable (a generator) — complete candidates, in its order;
a dict {fact: [values]} — every combination (the first fact outermost), each given as those facts (into = None);
Tree(root, children, complete=None, bound=None) — a depth-first walk: children(node) → the nodes one step
further, a node is a candidate when complete(node) (default: when it has no children); a partial node is asked
only when prune is given (to cut below it);
a function of the facts computed once from state (below) → one of the above: the space read from the problem.
What is cut. prune: hard checks that, false on a node, are false on every node below it (a city visited twice stays
visited twice, a meeting that cannot be reached stays out of reach) — a node on which one of them is false is not
expanded. A Tree's bound(node): the best objective any candidate below the node can have (at least, when maximizing); a node
whose bound cannot beat what is kept is not expanded. Neither promise is checked: a prune check that is not monotone,
or a bound below a real candidate's value, can cut the best candidate; the record names the checks and the bound it
relied on. budget: asks at most.
What is kept: with an objective (a function of the candidate, or the name of a fact of its Response; maximize=True)
the keep best accepted candidates (the first found among equals); without one, the first keep accepted in the
space's order, and the search stops there (keep=2 says whether the first is the only one).
Exactness. run.exact is True when the search ended by itself — every candidate of the space was asked or cut by a
prune check or the bound — and then the best is the best of the space under those two promises (and THE only one
when keep ≥ 2 and one was found). It is False when the budget stopped it, and why_exact says so with the count.
Facts computed once. The facts the System computes from state alone (the problem read into typed facts, by rules or
by a model) are computed once and held for every candidate — only parts that read the candidate (directly or through
other facts) are re-run, so a model reading the problem is called once, not once per candidate. The winner is then
asked again in full with the System itself (stored when the System has storage): run.response is an ordinary decision
whose trace replays. If that full ask does not accept it — a held fact that should have been recomputed — the search
escalates and says so, instead of returning it.
Not done here: no proposals by a model (solvi.refine re-asks one; when run.best is None because the space was too big
for the budget, a refinement can take over), no search over numbers by bisection (res.counterfactual does that), no
parallel asks, and no proof of the prune / bound promises.
Tree
dataclass
¶
Tree(root: Any, children: Callable, complete: Callable | None = None, bound: Callable | None = None)
A space walked depth-first: root, children(node) → the next nodes, complete(node) → is the node a candidate
(default: when it has no children), bound(node) → the best objective any candidate below the node can reach (at
least, when maximizing; at most, when minimizing) — a node whose bound cannot beat what is kept is not expanded.
SearchRun
dataclass
¶
SearchRun(question: str, into: str | None, space: str, best: Any = None, value: Any = None, response: Any = None, kept: list = list(), asked: int = 0, accepted: int = 0, rejected: dict = dict(), pruned: dict = dict(), exhausted: bool = False, budget: int = 0, objective: str | None = None, maximize: bool = True, prune: list = list(), bound: str | None = None, keep: int = 1, held: list = list(), escalation: str | None = None, seconds: float = 0.0)
The record of one search: what was found (best, value, response, kept), what was searched (asked,
accepted, rejected by deciding check, pruned by check and "bound"), how it ended (exact, why_exact,
exhausted), and why a person gets it when nothing is returned (escalation). to_dict / from_dict; replay.
from_dict
classmethod
¶
A stored search back (the response restored with catalog's types, as Response.model_validate does).
replay ¶
Re-check the result: the winner's trace replays under system, the winner is accepted by its response (pass
accept again when it was not "checks"), and its objective recomputes to the recorded value (pass the objective
function again when it was one; a fact's name is read from the response). → {"ok", "mismatches": [(what, why)],
"trace": the trace replay}. Not re-checked: that no other candidate is better — run the search again for that.
search ¶
search(system, state, question, space, *, into=None, objective=None, maximize=True, prune=(), keep=1, budget=10000, accept='checks', store=True, hold=True)
Candidates from space through system's checks for question → a SearchRun (see the module docs).
space: a list / iterable of candidates, a dict {fact: [values]}, a Tree, or a function of the facts computed once
from state returning one of them. into: the given fact a candidate is passed as (required except for a dict).
objective: a function of the candidate, or a fact name read from its Response (None: the first accepted wins);
maximize: largest (default) or smallest. prune: hard checks that stay false below a Tree node (a Tree's bound
cuts by the objective). keep: how many accepted candidates to keep. budget: asks at most.
accept: as in solvi.refine (default "checks"). store: store the winner's full ask when the System has storage.
hold: compute the facts that do not read the candidate once (default) — False re-runs every part per candidate.