3.10 Exercises
 Exercise 3.1:
 Comment on the following quote: "One of the main goals of AI should be to build general heuristics that can be used for any graphsearching problem."
 Exercise 3.2:
 Which of the pathfinding search procedures are fair in the sense that any element on the frontier will eventually be chosen? Consider this for question finite graphs without loops, finite graphs with loops, and infinite graphs (with finite branching factors).
 Exercise 3.3:
 Consider the problem of finding a path in the grid shown in Figure 3.13
from the position s to the position
g. A piece can move on the grid
horizontally and vertically, one square at a time. No step may be made
into a forbidden shaded area.
 On the grid shown in Figure 3.13, number the nodes expanded (in order) for a depthfirst search from s to g, given that the order of the operators is up, left, right, then down. Assume there is a cycle check.
 For the same grid, number the nodes expanded, in order, for a bestfirst search from s to g. Manhattan distance should be used as the evaluation function. The Manhattan distance between two points is the distance in the xdirection plus the distance in the ydirection. It corresponds to the distance traveled along city streets arranged in a grid. Assume multiplepath pruning. What is the first path found?
 On the same grid, number the nodes expanded, in order, for a heuristic depthfirst search from s to g, given Manhattan distance as the evaluation function. Assume a cycle check. What is the path found?
 Number the nodes in order for an A^{*} search, with multiplepath pruning, for the same graph. What is the path found?
 Show how to solve the same problem using dynamic programming. Give the dist value for each node, and show which path is found.
 Based on this experience, discuss which algorithms are best suited for this problem.
 Suppose that the graph extended infinitely in all directions. That is, there is no boundary, but s, g, and the blocks are in the same positions relative to each other. Which methods would no longer find a path? Which would be the best method, and why?
 Exercise 3.4:
 This question investigates
using graph searching to design video presentations. Suppose there exists
a database of video segments, together with their length in seconds and the topics
covered, set up as follows:
Segment Length Topics covered seg0 10 [welcome] seg1 30 [skiing, views] seg2 50 [welcome, artificial_intelligence, robots] seg3 40 [graphics, dragons] seg4 50 [skiing, robots] Suppose we represent a node as a pair:
⟨To_Cover,Segs⟩,
where Segs is a list of segments that must be in the presentation, and To_Cover is a list of topics that also must be covered. Assume that none of the segments in Segs cover any of the topics in To_Cover.
The neighbors of a node are obtained by first selecting a topic from To_Cover. There is a neighbor for each segment that covers the selected topic. [Part of this exercise is to think about the exact structure of these neighbors.]
For example, given the aforementioned database of segments, the neighbors of the node ⟨[welcome,robots],[]⟩, assuming that welcome was selected, are ⟨[], [seg2]⟩ and ⟨[robots], [seg0]⟩.
Thus, each arc adds exactly one segment but can cover one or more topics. Suppose that the cost of the arc is equal to the time of the segment added.
The goal is to design a presentation that covers all of the topics in MustCover. The starting node is ⟨MustCover,[]⟩, and the goal nodes are of the form ⟨[],Presentation⟩. The cost of the path from a start node to a goal node is the time of the presentation. Thus, an optimal presentation is a shortest presentation that covers all of the topics in MustCover.
 Suppose that the goal is to cover the topics [welcome,skiing,robots]. Suppose the algorithm always select the leftmost topic to find the neighbors for each node. Draw the search space expanded for a lowestcostfirst search until the first solution is found. This should show all nodes expanded, which node is a goal node, and the frontier when the goal was found.
 Give a nontrivial heuristic function h that is an underestimate of the real cost. [Note that h(n)=0 for all n is the trivial heuristic function.] Does it satisfy the monotone restriction for a heuristic function?
 Exercise 3.5:
 Draw two different graphs, indicating start and goal nodes, for which forward search is better in one and backward search is better in the other.
 Exercise 3.6:
 Implement iterativedeepening A^{*}. This should be based on the iterative deepening searcher of Figure 3.10.
 Exercise 3.7:
 Suppose that, rather than finding an optimal path from the start to a goal, we wanted a path with a cost not more than, say, 10% greater than the leastcost path. Suggest an alternative to an iterativedeepening A^{*} search that would guarantee this outcome. Why might this be advantageous to iterativedeepening A^{*} search?
 Exercise 3.8:
 How can depthfirst branchandbound be modified to find a path with a cost that is not more than, say 10% greater than the leastcost path. How does this algorithm compare to the variant of A^{*} from the previous question?
 Exercise 3.9:
 The overhead for iterative deepening with b1 on the denominator is not a good approximation when b approx 1. Give a better estimate of the complexity of iterative deepening when b=1. What is the complexity of the other methods given in this chapter? Suggest a way that iterative deepening can have a lower overhead when the branching factor is close to 1.
 Exercise 3.10:

Bidirectional search must be able to determine when the
frontiers intersect. For each of the following pairs of searches
specify how to determine when the frontiers intersect:
 Breadthfirst search and depthbounded depthfirst search.
 Iterative deepening search and depthbounded depthfirst search.
 A^{*} and depthbounded depthbounded search.
 A^{*} and A^{*}.
 Exercise 3.11:

Consider the algorithm sketched in the counterexample of the box:
 When can the algorithm stop? (Hint: it does not have to wait until the forward search finds a path to a goal).
 What data structures should be kept?
 Specify the algorithm in full.
 Show that it finds the optimal path.
 Give an example where it expands (many) fewer nodes than A^{*}.
 Exercise 3.12:
 Give a statement of the optimality of A^{*} that specifies the class of algorithms for which A^{*} is optimal. Give the formal proof.
 Exercise 3.13:
 The depthfirst branch and bound of Figure 3.11 is like a depthbounded search in that it only finds a solution if there is a solution with cost less than bound. Show how this can be combined with an iterative deepening search to increase the depth bound if there is no solution for a particular depth bound. This algorithm must return ⊥ in a finite graph if there is no solution. The algorithm should allow the bound to be incremented by an arbitrary amount and still return an optimal (leastcost) solution when there is a solution.