6.01 Lecture Notes - Lecture 30: Euclidean Distance, Taxicab Geometry, Admissible Heuristic

• School: MIT
• Department: Electrical Engineering and Computer Science
• Course: 6.01

Document Summary

If we modify the uniform-cost search algorithm to take advantage of a heuristic function, we get an algorithm called a (pronounced "a star"). It is given below, with the di erences highlighted in red. The only di erence is that, when we insert a node into the priority queue, we do so with a cost that is newn. cost + heuristic(news). Now, we can try to search in the big map for a path from g to x, using, as our heuristic function, the distance between the state of interest and x. Here is a trace of what happens (with the numbers rounded to increase readability): we get the start node out of the agenda, and add its children. Note that the costs are the actual path cost plus the heuristic estimate. G agenda: pq([(107, g-0->i), (101, g-1->f), (79, g-2->h)]: the least cost path is g-2->h, so we extract it, and add its successors.