[Solved] CS440 Homework 2

it simpler to write down the solution, duplicate nodes may be removed from the queue (without changing the behavior of the algorithm). Your answer should start with the initial queue followed by the status of the search after each while loop. Search status should be given as the node that gets expanded followed by the current queue. For each search, you only need to provide the complete list of statuses. For uniform-cost and A*, the entries in the queue should be accompanied by the value of the evaluation function; use alphabetical order for breaking ties. As an example, the first two entries of the answer for uniform-cost search should be:

1. q= [A(0)]
2. A, q = [B(3), D(4), C(5)]

Problem 2 [20 points]. Consider the graphs on

the right, which we denote as a cycle and an in-

finite diamond strip (IDS). The cycle has n nodes

v₁, , v₇₁ = v_o that are consecutively ordered, i.e.. v_i has v₁_₁ and Vii mod n as its two neigh-

bors. with vi_i before v_i+1 mod n The IDS extends infinitely to both left and right. For any node in the IDS, assume that in its adjacency list, the neighbors on the left appear before the neighbors on the right. Now consider running BFS and DFS tree and graph searches on these two graphs. For the cycle graph, suppose the start node is xI = v1 and the goal node is xG = xk. 1 < k < n. For the diamond strip, the distance between xi (i.e., the green node) and xG (i.e., the red node) is 2m. For each of the eight search combinations, provide your estimate (i.e., in big OH notation) of the number of nodes that has been added to the queue when the search is complete. If you think that the search does not end, the answer should be infinity. Briefly justify your answer.

Problem 3 Prove that consistent heuristics are always admissible. That is, for a heuristics function h(x) and transition cost c(x, a, x), from the assumption h(x) < c(x, a, x) 144 and h(xG) = 0, prove that h(x) < Cl; where Cl; is the optimal cost from x to xG. You may assume that all costs c(x, a, x) are non-negative.

Problem 4. Which of the following are admissible. given admissible heuristics h1. h₂? Which of the following are consistent, given consistent heuristics h₁, h₂? For your justification. prove starting with definitions of admissible heuristics and consistent heuristics.

• h_mi_n(n) = mint/4(n), h2(n)},
• hmax (n) = max fh_i(n) , h₂(n)} ,
• hu_m(n) = whi (n) + (1 w)h₂(n), 0 < w < 1.

Problem 5. Consider an informed, best-first search algorithm in which the evaluation function is f (n) = (2 w)g (n) +wh(n), 0 < w < 2. For what values of w is this algorithm guaranteed to be optimal when h is admissible (consider the case of TREE-SEARCH)? What kind of search does this perform when w = 0? When w = 1? When w = 2? In your proof, you may assume that if the heuristic in a standard A* search is inadmissible, then optimality cannot be guaranteed. Note that f (n) here does not always directly correspond to the evaluation function in a standard A* search.

Problem 6 . 4 Queens problem. Consider the 4-queens setup given in the figure. Apply hill-climbing to the problem until no more moves are possible. The objective function value of a given setup is equal to the number of pairs of attacking queens (without considering blocking). Each queen is allowed to move in the column she belongs. For breaking ties, if there are multiple choices for moving the queens, first use the left most column with the best move and then favor the least number of blocks moved. If there are still ties. move up instead of down. You need to show at each iteration the objective function value for all 16 positions and the move that you will make.

Problem 7 [. Consider the 8-puzzle problem and the two heuristics h1 and h2 from class. Recall that h1 counts the number of misplaced tiles and h2 counts the total Manhattan distance of the tiles to their target locations. Prove that both heuristics are admissible.

Problem 8. For h1 and h2 in the previous problem, show that they are consistent. Note that if you are sure you can prove consistency, you answer also works for the previous problem.