1. Here is a graph of some cities of Europe. Suppose that we are searching for an optimal path from Prague to Zagreb.
Consider a recursive depth-first tree search, ignoring path costs. Assume that the implementation will avoid revisiting nodes in the current path. What is the smallest and largest number of cities we might visit in searching for Zagreb?
Consider a breadth-first graph search, ignoring path costs. How many cities will we visit in the search?
Consider a uniform-cost graph search. What is the smallest and largest number of cities we might visit in the search?
Consider a recursive iterative-deepening tree search, ignoring path costs. At most how many times might we visit Bratislava in the course of the search?
2. True or false? In a uniform-cost search,
Nodes are expanded in order of their optimal path cost.
At any moment, the optimal path cost of every unexplored node is greater than the optimal path cost of every frontier node.
At any moment, the optimal path cost of every frontier node is greater than the optimal path cost of every explored node.
At any moment, the estimated path cost of at least one frontier node is actually optimal.
If all edges have the same step cost, then the uniform-cost search runs as quickly as a breadth-first search and achieves the same result.
3. Show that uniform-cost search is not complete unless step costs are bounded below by some value ε.
4. When a depth-limited tree search fails to find a solution, it might return one of two values: either (a) an indication that the search failed or (b) an indication that the search was cut off. What is the difference between these, and why might the caller care about this difference?
5. Write a Java interface Problem representing an
arbitrary problem with an initial state, actions, transition model,
goal test and step cost. Assume that states, actions and step costs
are all integers.
6. Using Java generics, generalize your interface from the preceding exercise to work with any state type S and action type A.
7. Implement the sliding block puzzle (e.g. the 8-puzzle or
15-puzzle) as an instance of the Problem interface you
designed above.
8. Implement the 8-queens puzzle as an instance of the Problem
interface.
9. Write a Java interface BTProblem that is like
Problem, but contains methods required for a
backtracking search.
10. Write a class Dfs with a recursive depth-first
tree search function that solves instances of the Problem
interface. Include a check that ensures that the search does not
revisit any state on the path from the root to the current node. Your
function should return a List of states from the initial
node to the goal, or null if no solution was found.
11. Write a class BTDfs that is like Dfs,
but performs a backtracking search.
12. Write a class Bfs with a breadth-first
graph search function that solves Problem instances.
Your function should return a List of states from the
initial node to the goal, or null if no solution was
found.
13. Modify your breadth-first search function from the previous exercise to perform a non-recursive depth-first graph search.
14. Write a class Ucs with a uniform-cost
graph search function that solves Problem instances.
Your function should return a List of states from the
initial node to the goal, or null if no solution was
found. Be sure that your implementation does not take linear time to
determine whether a node is in the frontier.
15. Write a class Ids with an iterative deepening
depth-first tree search function that solves Problem
instances. Use recursion to perform the depth-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. Your function
should return a List of states from the initial node to
the goal, or null if no solution was found.
16. Using your answers to previous exercises, compare the performance of breadth-first search and iterative deepening depth-first search on random solvable instances of the 8-puzzle.
17. Implement the well-known missionaries and cannibals
puzzle as an instance of the Problem interface. In this
puzzle, 3 missionaries and 3 cannibals are on the south bank of a
river. They all want to cross to the north bank using a boat that can
hold two people. There can never be more missionaries than cannibals
on either side of the river (for then the cannibals would feast).
18. Consider Knuth's conjecture (described in Russell & Norvig, section 3.2) about reaching any number starting from 4 by applying factorial, square root, and floor operations. Can we write a program to explore this state space using 64-bit integers, or do we need a larger integer type? If we attempt to perform a breadth-first search directly through this space, it will exhaust the computer's memory and/or CPU after exploring only a few nodes. Why?
19. (Russell & Norvig, ex. 3.26) Consider a state space consisting of an infinite 2D grid with points at every coordinate (i, j) where i and j are integers. The start state is the origin (0, 0) and the goal state is at (x, y).
What is the branching factor of this state space?
How many distinct states are there whose optimal path cost is k, for an integer k > 0?
What is the maximum number of nodes expanded by breadth-first tree search?
What is the maximum number of nodes expanded by breadth-first graph search?
20. (Russell & Norvig, ex. 3.18) Describe a state space in which iterative deepening will have a running time that is asymptotically worse than depth-first search (e.g. O(n2) vs. O(n)).
21. Suppose that a state space has the form of an infinite tree with a constant branching factor of 3 at every node.
At any moment as a breadth-first graph search runs, let E be the number of nodes in the explored set and F be the number of nodes in the frontier. What value does E/F converge to, if any, as the search proceeds?
For any depth k, let D(k) be the number of nodes generated in a depth-first search to depth k, and let I(k) be the number of nodes generated in an iterated deepening search to depth k. What value does D(k)/I(k) converge to, if any, as k goes to infinity?
22. Suppose that in a certain state space all step costs are 1 and the optimal solution has path cost 10. A depth-limited tree search with limit 10 is guaranteed to find this solution. Can a depth-limited graph search make the same guarantee? What about an iterative deepening depth-first graph search?
