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?
If we use iterative deepening A*, how many cost-limited searches will run in the course of the search?
If we use recursive best-first search, how many nodes will be expanded in the search?
2. (Russell & Norvig, ex. 3.14) 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?
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.
A* always expands nodes in decreasing order of h(n).
A* always expands nodes in increasing order of f(n).
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?
10. In Java, write a interface HeuristicProblem that
extends the Problem interface from last week's exercises
with a heuristic function estimating the cost of the cheapest path to
a goal state.
11. Implement an A* graph search function in Java that
solves HeuristicProblem instances. A* is quite similar
to uniform-cost search, but do not copy and paste your uniform-cost
search implementation from last week's exercises. Instead, generalize
it so that the bulk of the implementation can be shared between your
uniform-cost and A* search functions.
12. Implement an iterative-deepening A* tree search
function in Java that solves HeuristicProblem instances.
Use recursion to perform the cost-limited searches. Include a check
that ensures that the search does not revisit any state on the path
from the root to the current node.
13. Implement a recursive best-first tree search function
in Java that solves HeuristicProblem instances. Include
a check that ensures that the search does not revisit any state on
the path from the root to the current node.
14. Extend your sliding block puzzle implementation from last
week's exercises to implement the HeuristicProblem
interface. Use the minimum of Manhattan distance and number of
misplaced tiles as your heuristic.
15. Using your answers to previous exercises, compare the performance of A*, iterative deepening A*, and recursive best-first search on random solvable instances of the 15-puzzle.
