CPSC 322 Lecture Notes - Lecture 4: Priority Queue
Document Summary
Search heuristic h(n) is an estimate of the cost of the shortest path from node n to goal node. A search heuristic is admissible if it is an underestimate of the cost from n to goal. Lowest-cost-first search: frontier is a priority queue ordered by cost(p) Best-first search: frontier is a priority queue ordered by h(p) A* search: frontier is a priority queue ordered by f(p) = cost(p) + h(p) For a* search, the frontier is a priority queue ordered by f(p) = cost(p) + h(p). However, using a heap to implement a priority queue may present sorting and comparison problems when there are two tuples with the same priority. In our case, this would be when two paths have the same value. We solve this problem by storing the path information as a triple (value, index, path) and usi(cid:374)g i(cid:374)dex to (cid:862)break ties(cid:863) (cid:449)he(cid:374) there are t(cid:449)o paths (cid:449)ith the sa(cid:373)e (cid:448)alue.
