1. Here is a graph of some cities of Europe. Each city c in the graph is annotated with a value h(c) indicating a heuristic estimate of the city's distance from Zagreb. We would like to find an optimal path from Prague to Zagreb.
Is this heuristic admissible?
Is this heuristic consistent?
If we use a greedy best-first search, will we necessarily find an optimal path? Might we find an optimal path?
If we use A*, how many nodes will be expanded in the search?
2. In chess, a rook can move any number of squares horizontally or vertically, but cannot jump over other pieces. Is Manhattan distance is an admissible heuristic for the minimum number of moves to move a rook between two given squares with a certain set of pieces on the board?
3. True or false?
A* always expands nodes in decreasing order of h(n).
A* always expands nodes in increasing order of f(n).
Depth-first search always expands at least as many nodes as A* with a consistent heuristic.
Uniform-cost search always expands at least as many nodes as A* with a consistent heuristic.
Whenever A* expands a node, it has found the optimal path from the start node to that node.
4. Is the heuristic function h(n) = 0 consistent? How will A* behave using this heuristic function?
5. Consider a heuristic function h(n) that returns the exact cost of the cheapest path from a node n to a goal state. Is h consistent? How will A* behave using this heuristic function?
6. True or false?
The maximum of two admissible heuristics is admissible.
The maximum of two consistent heuristics is consistent.
The sum of two admissible heuristics is admissible.
7. Prove that every consistent heuristic is admissible.
8. In A* we use a cost function f(n) = g(n) + h(n), where g(n) is the total cost of the path from the start node to node n, and h(n) estimates the cost of the path from n to the goal. Consider the optimal path from the start node to the goal. As we walk along this path, how will f(n) change from node to node? Will it be (a) increasing, (b) decreasing, (c) non-increasing, (d) non-decreasing, or (e) not necessarily any of these? What about g(n)? h(n)?
9. (Russell & Norvig, ex. 3.25) Consider a version of best-first search that uses f(n) = (2 – ω) g(n) + ω h(n) for some constant ω. What kind of search does this perform for ω = 0, ω = 1, and ω = 2? For which values of ω is the search optimal, assuming that h is admissible?
