1. Describe the characteristics of a search space in which iterative deepening search performs much worse than depth-first search. In this situation, give big-O descriptions of the running time for iterative deepening and for depth-first search. Your answer should reflect the structure of a particular search space, not where in that search space the solution happens to be or how often it appears.
2. Sometimes there is no good evaluation function for a problem, but
there is a good comparison method: a way to tell if one node is better
than another, without assigning numerical values to either. Show that
this is enough to do a best-first search. Describe in words and pseudo
code how you would implement this method, and show what the differences
in time and memory would be (if any) compared to a standard greedy
search where you know the particular value associated with each node.
(This problem is based on textbook problem 4.12)
3. The heuristic path algorithm
is a best-first search in which the objective function is f(n) =
(2-w)g(n) + w h(n). For what values of w is this algorithm guaranteed to
be optimal? Prove your results. What kind of search does this perform
when w = 0? When w = 1? When w = 2? (This problem is based on textbook
problem 4.2)
Implement regular iterative deepening and A* search for the 8-puzzle. The AIMA code library already has most of what you need for the 8-puzzle itself.
To get access to it, you need to execute the following two statements:
(load "/Accounts/courses/cs327/aima/aima.lisp")
(aima-load 'search)
From the AIMA documentation:
The representation of states is not the obvious one (a 3x3
array), but it is both efficient and fairly easy to manipulate. We
represent each tile
as an integer from 0 to 8 (0 for the blank). We also represent
each square as an integer from 0 to 8, arranged as follows:
0 1 2
3 4 5
6 7 8
Finally, we represent a state (i.e., a complete puzzle) as the
sum of the tile numbers times 9 to the power of the tile's square number.
For example:
1 2
3
1*9^0 + 2*9^1 + 3*9^2
8 . 4 is represented
by: + 8*9^3 + 0*9^4 + 4*9^5
7 6
5
+ 7*9^6 + 6*9^7 + 5*9^8 = 247893796
For your assignment, write two functions as follows:
(8-puzzle-solve1 state) - uses iterative deepening
(8-puzzle-solve2 state heuristic) - uses A* search with
appropriate heuristic
You should also implement the following two heuristic functions, either of which you can pass as arguments in 8-puzzle-solve2:
(num-wrong-tiles state) - counts the number of misplaced
tiles for the indicated state
(manhattan-distance state) - computes the Manhattan distance
for the misplaced tiles for the indicated state
Both functions should return a list containing (from to) pairs indicating where to move the blank square. For example, if the initial state was
1 . 2
8 4 3
7 6 5
The solution might appear as
((1 2) (2 5) (5 4))
You should consider the goal state to be the one that appears earlier, i.e. the empty space is in the middle and the numbers circle sequentially around it.
Run some experiments with some random states. In comments at the end of search.lisp, describe your experiments and how iterative deepening, A* with the first heuristic, and A* with the second heuristic compare.
Here are various functions you may find useful:
| (random-8-puzzle-state) | returns a random state of the 8-puzzle |
| (8-puzzle-print state) | displays the 8-puzzle associated with state |
| (move-blank state from to) | moves the blank from square from to square to |
| (blank-square state) | returns the number that the blank square is in |
| (neighbors square) | the squares that can be reached from a given square |
| (8-puzzle-location square) | return the (x y) location of a square number |
| (8-puzzle-state pos0 pos1 pos2 pos3 pos4 pos5 pos6 pos7 pos8) | define a new state with the tile number indicated in each position (use 0 for blank) |
| (8-puzzle-ref state square) | return the tile that occupies the given square |
| (abs n) | the absolute value of n |