CSE326 Summer 2006

CSE Home

326 Home

About Us

Search

Contact Info

Administrative  Home  Message Board  Annoucement Archive  Class List Archive  Anonymous Feedback  Mail Instructor & TAs Lectures  Calendar & Slides  Midterm Study Guide Projects  Project 1  Project 2 Phase A  Project 2 Phase B  Project 2 Phase C  Project 3 Homework  Homework 1  Homework 2  Homework 3  Homework 4  Homework 5  Homework 6  Homework 7  Homework 8 Policies  General Guidelines  Grading Policies  Programming Guidelines  Writeup Guidelines Computing  Unix Basics

A* Search combines the best features of Breadth-first search (always finds optimal paths) and Best-First search (visits fewer nodes).  A* is like Best-First search, except that the priority for a node is the sum of the actual distance from the start to the node and the estimated distance to the goal: key(node) = distance_from_start_to_node + |nodex - exitx| + |nodey - exity| You will need to keep track of the true distance from the start in each node.  Then, when find the neighbors of a node, their distance is the distance of the current node plus one. There are also some other minor but important modifications you need to make to the Best-First algorithm: After you first see a node, you might see it again but along a shorter path.  Therefore, instead of just checking whether a node has been visited or not before adding it to the queue, you have to check whether it has been visited and whether the distance from the start to that node previously calculated is the same or shorter than the distance along the current path.  If both conditions hold, then you don't add it to the queue.  But, if you have found a shorter path to the node, go ahead and insert it into the queue again.  It is okay to have several copies of the same node, but with different priorities, in the queue. Do not stop the search until the goal is first removed from the queue, not when it is first inserted in the queue.  This is because the first time you insert the goal you may not have found the shortest path to it.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to gyngve]