EECS 391/491 PS#3 FAQ

EECS 391/491: PROBLEM SET #3 FAQ

Note: it is not a requirement that answers be typeset. Hint: drawing trees by hand might be faster than drawing them on a computer

Note: in A*, f(n) = g(n) + h(n)

Problem 3.1

Your formulations need only be parallel in scope to those in Section 3.2 of R&N.

For the "entire state space", just state what it is. For example, the entire state space of the 8-puzzle consists of the 9! configurations of the tiles. There is no need to depict this graphically!

Problem 3.2

In (b), it is enough to merely list the nodes.

Problem 3.3

Note that you only have to draw one tree for each part! You do not have to show successive trees at different levels of growth. Also, You don't have to, but it might also be faster to compute these if you label all edges with their costs.

Here are some notes that add clarification to the second part:

Note: the h in the formula is the original heuristic: straight line distances in Figure 4.1, page 95 of R&N.
Note: at the goal node you do not use the above formula, you merely set h' (goal) = 0 [which is necessary for it to be admissible].
When you redo A* you will order nodes by f'=g+h'. That is, you use the same g as in the first part but the new heuristic.

For example, looking at 4.1 (p. 95) of R&N, we see that h(Arad)=366. Using Figures 3.2 (p. 63) and 4.1 (p. 95) of R&N, we see that Arad has three neighbors/successors (Zerind, Sibiu, and Timisoara), and that the new heuristic is

h'(Arad) 
   = min { c(Arad,Zerind)+h(Zerind), c(Arad,Sibiu)+h(Sibiu), c(Arad,Timisoara)+h(Timisoara) } 
   = min { 75+374, 140+253 , 118+329 }
   = min { 449, 393, 447 }
   = 393

Note that 366 = h(Arad) <= h'(Arad) = 393 and that 393 = h'(Arad) <= h*(Arad) = 418

Problem 3.4

Each answer is just a couple words.

Problem 3.5

The "proofs" he's asking for may be no more than a simple demonstration. For example, suppose one defines a "rational number" as one that can be written as p/q, where p and q are integers. Then to "prove" that "An integer is a special case of a rational number" one might simply say, "For any integer k, k=k/1".

Problem 3.6

Note the problem explicitly says you do not have to return the path.
The problem is much simpler if you don't have keep track of these "pointers".
You do not have to implement a tree structure in your program to solve the problem
You can use vectors, arrays with "pointers", hash tables, sets, etc. For my implementation, I used Matlab's "set" operators, which work on sorted vectors. Another approach is simply to use separate two-d arrays for storing the required information: g, h, f (=g+h), and whether a node is on the fringe or not.

Created: 2008-01-30. Modified: 2008-02-04.