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.,
[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
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).
IterativeTighteningSearch(possibilities: Iterator[B], initial_bounds: Optional[graphtage.bounds.Range] = None)¶
Implementation of iterative tightening search on a given sequence of
__init__(possibilities: Iterator[B], initial_bounds: Optional[graphtage.bounds.Range] = None)¶
Initializes the search.
possibilities – An iterator yielding
graphtage.bounded.Boundedobjects 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.
Returns the best solution the search has thus found.
The best solution the search has thus found, or
Noneif it has not yet found a feasible solution.
- Return type
remove_best() → Optional[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
True. 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() → B¶
Finds and returns the smallest item, fully tightened.
This is equivalent to:
while self.tighten_bounds(): pass return self.best_match