CECS 451 Assignment 5 SOLVED

CECS 451
Assignment 5
Total: 36 Points
General Instruction
• I recommend you can write your answer using LATEX.
• Submit uncompressed file(s) in the Dropbox folder via BeachBoard (Not email).
1. True or False? You don’t need to explain your answers.
(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?
Answer yes or no, then explain your answers.
(d) (3 points) Assume the terminal payoff at the node (4) is less than −4. Do we need
expand the node (5) and (6)? Answer yes or no, then explain your answers.
CECS 451 Assignment 5 - Page 2 of 2
Figure 1: (a) A map where the cost of every edge is 1. Initially the pursuer P is at node b
and the evader E is at node d. (b) A partial game tree for this map. Each node is labeled
with the P, E positions. P moves first.
5. True or False? You don’t need to explain your answers.
(a) (2 points) (A ∧ B) |= (A ⇔ B)
(b) (2 points) (C ∨ (¬A ∧ ¬B)) ≡ ((A ⇒ C) ∧ (B ⇒ C))
(c) (2 points) (A ∨ B) ∧ (¬C ∨ ¬D ∨ E) |= (A ∨ B)
(d) (2 points) (A ∨ B) ∧ ¬(A ⇒ B) is satisfiable.
6. (4 points) Prove using Venn diagram, or find a counterexample to the following assertion:
α |= (β ∧ γ) then α |= β and α |= γ