The A* algorithm.
+INFINITY+
|
(find-path successors previous set-previous cost set-cost estimate-distance goalp start-node goal-node) |
function |
DO: Implement the A* algorithm.
SUCCESSORS: a function giving for each node, the list of its
successors.
PREVIOUS: a getter giving the current previous node for the
given node.
SET-PREVIOUS: a setter to set the current previous node for the
given node. (lambda (new-previous node))
COST: a getter giving the current cost of the given
node. The default should be +INFINITY+.
SET-COST: a setter setting the current cost of the given
node. (lambda (new-cost node))
ESTIMATE-DISTANCE: a function of two nodes returning a cost estimate
of the distance between them.
GOALP: a predicate indicating whether the node is the
GOAL-NODE (or close enough).
START-NODE: the start node of the searched path.
GOAL-NODE: the end node of the searched path.
RETURN: a path, ie. a list of nodes from START-NODE to
GOAL-NODE.