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.