Here is a map, with each arc showing the true cost (i.e., g(n)) between two adjacent states [on the left], whereas the table on the right shows the heuristic costs (i.e., h(n), an estimate of true cost from n to the goal state G):

For finding path from A (initial state) to the goal state G, apply the following algorithms one by one. Show your working by drawing the tree and queue:

1. Uniform Cost Search i.e., f(n) = g(n)
2. A* search i.e., f(n) = g(n) + h(n)
3. For A*, what value of h(A) would make the heuristic non-admissible (currently it is 17)?

20 22 19 25 n A B D E F h(n) 17 15 16 14 15 13 18 27 18 19 27 18 G 0 B H 13 H I 18 22 18 18