attelo.optimisation package¶
Submodules¶
attelo.optimisation.astar module¶
Various search algorithms for combinatorial problems:
[OK] Astar (shortest path with heuristics), and variants:
[OK] beam search (astar with size limit on waiting queue)
- [OK] nbest solutions: implies storing solutions and a counter, and changing
return values (actually most search will make use of a recover_solution(s) to reconstruct desired data)
branch and bound (astar with forward lookahead)
-
class
attelo.optimisation.astar.
BeamSearch
(heuristic=<function <lambda>>, shared=None, queue_size=10)¶ Bases:
attelo.optimisation.astar.Search
search with heuristics but limited size waiting queue (restrict to p-best solutions at each iteration)
-
add_queue
(items, ancestor_cost)¶
-
new_state
(data)¶
-
-
class
attelo.optimisation.astar.
Search
(heuristic=<function <lambda>>, shared=None, queue_size=None)¶ Bases:
object
abstract class for search each state to be explored must have methods
next_states()
- successor states + costsis_solution()
- is the state a valid solutioncost()
- cost of the state so far (must be additive)
default is astar search (search the minimum cost from init state to a solution
Parameters: - heuristic – heuristics guiding the search (applies to state-specific
data(), see
State
) - shared – other data shared by all nodes (eg. for heuristic computation)
- queue_size – limited beam-size to store states. (commented out, pending tests)
-
add_queue
(items, ancestor_cost)¶ Add a set of succesors to the search queue
:type items [(data, float)]
-
add_seen
(state)¶ Mark a state as seen
-
has_empty_queue
()¶ Return True if the search queue is empty
-
is_already_seen
(state)¶ Return True if the given search state has already been seen
-
launch
(init_state, verbose=False, norepeat=False)¶ launch search from initital state value
Param: norepeat: there’s no need for an “already seen states” datastructure
-
new_state
(data)¶ Build a new state from the given data
-
pop_best
()¶ Return and remove the lowest cost item from the search queue
-
reset_queue
()¶ Clear out the search queue
-
reset_seen
()¶ Mark every state as not yet seen
Information that can be shared across states
-
class
attelo.optimisation.astar.
State
(data, cost=0, future_cost=0)¶ Bases:
object
state for state space exploration with search
(contains at least state info and cost)
Note the functions is_solution and next_states which must be implemented
-
cost
()¶ past path cost
-
data
()¶ actual distinguishing contents of a state
-
future_cost
()¶ future cost
-
is_solution
()¶ return True if the state is a valid solution
-
next_states
()¶ return the successor states and their costs
-
total_cost
()¶ past and future cost
-
update_cost
(value)¶ add to the current cost
-