[SOLVED] Cs440 – introduction to artificial intelligence   – assignment 2 –

Search Problems in AI Problem 1 (10 points): Trace the operation of A^∗ search (the tree version) applied to the problem of getting to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes that the algorithm will consider and the f, g, and h score for each node. You don’t need to draw the graph, just right down a sequence of (city,f(city),g(city),h(city)) in the order in which the nodes are expanded.Figure 1: A simplified road map of part of Romania indicating distances between different cities.Figure 2: Straight-line distances to BucharestProblem 2 (10 points): Consider a state space where the start state is number 1 and each state k has two successors: numbers 2k and 2k +1.Problem 3 (5 points): Which of the following statements are correct and which ones are wrong?Problem 4 (2 points): Iterative deepening is sometimes used as an alternative to breadth first search. Give one advantage of iterative deepening over BFS, and give one disadvantage of iterative deepening as compared with BFS. Be concise and specific.Problem 5 (10 points): Prove that if a heuristic is consistent, it must be admissible. Construct an example of an admissible heuristic that is not consistent. (Hint: you can draw a small graph of 3 nodes and write arbitrary cost and heuristic values so that the heuristic is admissible but not consistent).Problem 6 (3 points): In a Constraint Satisfaction Problem (CSP) search, explain why it is a good heuristic to choose the variable that is most constrained but the value that is least constraining.Problem 7 (10 points): Consider the following game tree, where the first move is made by the MAX player and the second move is made by the MIN player.Problem 8 (10 points): Which of the following are admissible, given admissible heuristics h₁, h₂? Which of the following are consistent, given consistent heuristics h₁, h₂? Justify your answer.Which one of these three new heuristics (a, b or c) would you prefer to use for A*? Justify your answer.Problem 9 (10 points): Simulated annealing is an extension of hill climbing, which uses randomness to avoid getting stuck in local maxima and plateaux.