Assignment 1 – Question 9 (Written Problem)
This non-programming problem is part of Assignment 1. Please add your answers to this document and submit your completed document along with your Pac-Man solutions.
Look at the following graph. Node A is the start node (indicated by the arrow with no tail node) and G is the goal (indicated by the double circle).
The table gives you the heuristic values h(n) for each node, however h(C) is unknown.
n
h(n)
A
5
B
5
C
?
D
3
E
3
F
1
G
0
(a) Provide the range of values for h(C) for which h would be admissible.
(b) Provide the range of values for h(C) for which h would be consistent.
(c) If you were to follow the search strategies listed in the table, which of the listed paths are possible? Indicate valid paths by marking an X in the appropriate row(s). You may assume that h is admissible in each case. In some cases, more than one path may be a valid result, and you should mark all such paths.
Search algorithm
A – C – E – G
A – B – C – E – G
A – B – D – G
A – B – D – F – G
Depth first
Breadth first
A* with heuristic h
