# Artificial Intelligence 1 – Tutorial Week 5 – Optional Exercises

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.

2. Is this heuristic consistent?

3. If we use a greedy best-first search, will we necessarily find an optimal path? Might we find an optimal path?

4. 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?

1. A* always expands nodes in decreasing order of h(n).

2. A* always expands nodes in increasing order of f(n).

3. Depth-first search always expands at least as many nodes as A* with a consistent heuristic.

4. Uniform-cost search always expands at least as many nodes as A* with a consistent heuristic.

5. 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?