graphtage.search¶
A module for solving a search problem in an iteratively revealed search space.
Given: an iterator that yields an unknown but finite number of integer range objects, e.g., [100, 200]
,
[50, 1000]
, [60, 500]
, …. Each integer range object has a member function that is guaranteed to tighten the
bounds of the range, such that the range monotonically shrinks and converges toward a specific number (i.e., it
conforms to the graphtage.bounds.Bounded
protocol). For example, [100, 200].tighten()
→
[150, 160].tighten()
→ [150, 155].tighten()
→ [153, 153]
→ 153
. Each object might have a different
tighten function; we cannot make any assumptions about the rate of convergence, other than that the bounds are
guaranteed to shrink with each call to tighten()
.
Goal: Create the most computationally efficient algorithm to determine the range object that converges to the smallest integer (i.e., with the fewest possible tightenings).
search classes¶
IterativeTighteningSearch¶
- class graphtage.search.IterativeTighteningSearch(possibilities: Iterator[graphtage.search.B], initial_bounds: Optional[graphtage.bounds.Range] = None)¶
Bases:
graphtage.bounds.Bounded
,Generic
[graphtage.search.B
]Implementation of iterative tightening search on a given sequence of
graphtage.bounds.Bounded
objects.The search class itself is
graphtage.bounds.Bounded
, with bounds on the value of the optimal solution. Each call toIterativeTighteningSearch.tighten_bounds()
will improve these bounds, if possible.- __bool__()¶
Returns whether or not this search’s bounds are
definitive
.
- __init__(possibilities: Iterator[graphtage.search.B], initial_bounds: Optional[graphtage.bounds.Range] = None)¶
Initializes the search.
- Parameters
possibilities – An iterator yielding
graphtage.bounded.Bounded
objects over which to search.initial_bounds – Bounds on the optimal solution, if known. Having good initial bounds can greatly speed up the search. However, if the initial bounds are incorrect (i.e., if the true optimal solution lies outside of
initial_bounds
, then the resulting solution may be incorrect.
- property best_match: Optional[graphtage.search.B]¶
Returns the best solution the search has thus found.
- Returns
The best solution the search has thus found, or
None
if it has not yet found a feasible solution.- Return type
Optional[B]
- bounds() graphtage.bounds.Range ¶
Returns the bounds of this object.
- goal_test() bool ¶
Returns whether
best_match
is the optimal solution.
- remove_best() Optional[graphtage.search.B] ¶
Removes and returns the current best solution found by the search, if one exists.
This enables one to iteratively sort the input sequence. However, this function is only guaranteed to return the globally optimal item if
IterativeTighteningSearch.goal_test()
returnsTrue
. Therefore, to generate a total ordering over the input sequence, you should tighten bounds until the goal is reached before each call to this function:while search.tighten_bounds(): while not search.goal_test() and search.tighten_bounds(): pass if search.goal_test(): yield search.remove_best() while search.goal_test(): yield search.remove_best()
However, if your goal is to produce a total ordering,
graphtage.bounds.sort()
is more efficient.
- search() graphtage.search.B ¶
Finds and returns the smallest item, fully tightened.
This is equivalent to:
while self.tighten_bounds(): pass return self.best_match