Consider the puzzle shown next. Green square is the start block and red square is the goal block. The green block can move one square at a time in the 4 directions (Left, right, up, down). a. Give a formulation of the search problem. b. Solve the problem using greedy search with the Manhattan distance as heuristic. Show the search tree. c. Solve the problem using A* search using Manhattan distance as heuristic. Show the search tree.

_______________________________________________________________________

Assume that a rook can move on a chessboard any number of squares in a straight line, vertically or horizontally, but cannot jump over other pieces. Can the Manhattan distance be considered an admissible heuristic for the problem of moving the rook from square A to square B in the smallest number of moves?

Solution: No. The Manhattan distance may over-estimate the optimal remaining number of moves to the goal because a rook may cover several squares in a single move. NOTE: If the path cost instead were the number of squares covered, then Manhattan distance would be admissible.

____________________________________________________________

Consider the 8-puzzle problem. Assume that the goal state is the following state: In any state s, for any non-empty tile i = 1 to 8, the number ni of permutation inversions is the number of tiles j < i that appear after tile i. The total number of permutation inversions of s is P = n 8i=1 i Let h(N) be the heuristic function that evaluates to the total number of permutation inversions in the state of node N. e.g. h(N) = sum of permutation inversions = n5 + n8 + n4 + n2 + n1 + n7 + n3 + n6 = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16 Is h admissible? If yes, prove it. If not, show a counter-example

_____________________________________________________________________--

The state space consists of states S, A, B, C, D, E, G1, and G2. S is the initial state. G1 and G2 are both goal states. The possible transitions between states are indicated by arcs. So, for instance, the successor function applied to state S returns {A, B}; applied to state A it returns {C, D}, etc... The number labelling each arc (roughly at the mid-point of the arc) is the actual cost of the corresponding action. For example, the cost of going from S to A is 3. The number in bold italic near each state is the value of the heuristic function h at that state. For example, the value of h at state C is 3. a. Is the heuristic function h defined by values provided in the figure admissible? How do you know? How does this affect the search? b. Is the heuristic function h defined by values provided in the figure consistent?