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 + costs
  • is_solution() - is the state a valid solution
  • cost() - 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

shared()

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