dcsext.algorithms.search_astar
search_astar - performs an A* shortest path search over a graph.
Contents
Description
The search expands nodes from start towards goal ordered by path cost plus the estimated cost-to-go given by heuristic, so it finds the cheapest path when the heuristic never overestimates.
Functions
search_astar(graph, start, goal, heuristic)
Run an A* search over graph from start to goal.
Parameters
- graph
- a graph that provides a
neighbors(node)method returning a table keyed by neighboring nodes whose values are edges exposing acost()method. - start
- the starting node in graph
- goal
- the goal node in graph, must provide a
found(node)predicate used to test whether a candidate node satisfies the goal condition. - heuristic
- a function of the form
number heuristic(candidate_node, goal)where the numerical value represents an estimated cost to reach the goal from candidate_node.
Returns
- Queue holding the found path from start to goal.
- number the total cost of the path.