CECS 451 Assignment 5

\$30.00

Rate this product

CECS 451
Assignment 5
Total: 36 Points
General Instruction
• Submit uncompressed file(s) in the Dropbox folder via BeachBoard (Not email).
(a) (2 points) h(n) = 0 is an admissible heuristic for the 8-queens problem.
(b) (2 points) Assume that a rook can move on a chessboard one square at a time in
vertically or horizontally, but cannot jump over other pieces. Manhattan distance is
an admissible heuristic for the problem of moving the rook from square A to square
B in the smallest number of moves.
2. (6 points) The heuristic path algorithm is a best-first search in which the evaluation
function is f(n) = (2 − w)g(n) + wh(n). What kind of search does this perform for
w = 0, w = 1, and w = 2?
3. Give the name of the algorithm that results from each of the following cases:
(a) (2 points) Local beam search with k = 1.
(b) (2 points) Simulated annealing with T = ∞ at all times.
4. Imagine that, one of the friends wants to avoid the other. The problem then becomes a
two-player pursuit–evasion game. We assume now that the players take turns moving.
The game ends only when the players are on the same node; the terminal payoff to the
pursuer is minus the total move taken. An example is shown in Figure 1.
(a) (2 points) What is the terminal payoff at the node (1)?
(b) (2 points) What are the positions of the two players at the node (2) and (2)’s
children?
(c) (3 points) Can we assume the terminal payoff at the node (2) is less than < −4?
(d) (3 points) Assume the terminal payoff at the node (4) is less than −4. Do we need