Question 8
SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.
Emulate A*, WA* and Branch-and-Bound on the given map, then answer the subquestions.
Is the heuristic admissible in the given map?
Yes
No
Cannot be determined