Starting from:
$30
CS440-Assignment 2 Solved
Problem 1 ]. Use the generic graph search method covered in class, carry out BFS DFS, uniform-cost, and A* over the graph and the heuristic function given in the figure. The start state is xI = A and the goal state is :rc; = F. For a given state, its neighbors appear in the adjacency list in an alphabetical order. For example,
C's neighbors are ordered as A, B, D, E, F. To make 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:
Problem 2. Consider the graphs on the right, which we denote as a cycle and an infinite diamond strip (IDS). The cycle has n nodes vo that are consecutively ordered, i.e., Vi has and Vi+l mod n as its two neighbors, with Vi—l before t/'i+l 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 a;I = VI and the goal node is a;c; = TIC, 1 < k n. For the diamond strip, the distance between xI (i.e., the green node) and (i.e., the red node) is 2m. For each of the eight search combinations, provide your estimate (i.e., in big 0(•) 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, from the assumption h(x) c(x, a, x') + h(x/) and h(XG) = 0, prove that h(x) where 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 hi, 112? Which of the following are consistent, given consistent heuristics hi, 112? For your justification, prove starting with definitions of admissible heuristics and consistent heuristics.
Page 1
(i) hmm (n) = min{hl h2(n)}' (ii) ( n) ¯— max{hl (n), 112 (n)}, iii) hlin(n) = whl(n) + (1 — S W S 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 hi and from class. Recall that hi 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 hi and 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
C's neighbors are ordered as A, B, D, E, F. To make 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:
Problem 2. Consider the graphs on the right, which we denote as a cycle and an infinite diamond strip (IDS). The cycle has n nodes vo that are consecutively ordered, i.e., Vi has and Vi+l mod n as its two neighbors, with Vi—l before t/'i+l 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 a;I = VI and the goal node is a;c; = TIC, 1 < k n. For the diamond strip, the distance between xI (i.e., the green node) and (i.e., the red node) is 2m. For each of the eight search combinations, provide your estimate (i.e., in big 0(•) 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, from the assumption h(x) c(x, a, x') + h(x/) and h(XG) = 0, prove that h(x) where 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 hi, 112? Which of the following are consistent, given consistent heuristics hi, 112? For your justification, prove starting with definitions of admissible heuristics and consistent heuristics.
Page 1
(i) hmm (n) = min{hl h2(n)}' (ii) ( n) ¯— max{hl (n), 112 (n)}, iii) hlin(n) = whl(n) + (1 — S W S 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 hi and from class. Recall that hi 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 hi and 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
1 file (2.2MB)
