(b) Let x1, . . . , xn denote the blocks in a blocks world problem. Consider the heuristich2(s) :=nXi=1f (xi)for blocks world, where the function f is defined as:f (xi) := 1 + |{xj | xj is anywhere above xi}| if goalpos(xi)̸ = pos(s, xi)0 otherwise.The expression goalpos(xi)̸ = pos(s, xi) holds if block xi is on block y in state s, but shouldbe on block z̸ = y in the goal (as discussed in the lecture, y and z may also represent thetable). The heuristic h2 hence determines all blocks that are not yet at their goal positionand adds all blocks above those blocks (since they have to be moved before those blocks canbe moved). To illustrate the heuristic, consider the following example:x1x2x3x4x1 x2x3x4The initial state sI is depicted on the left side, and the goal state on the right. The heuristicvalue in the initial state is h2(sI) = 0 + 3 + 0 + 1 = 4 as x1 and x3 are on the correct blockalready and hence f (x1) = f (x3) = 0. Block x2 is on x1 instead of the table with 2 blocksabove x2, so f (x2) = 3, and block x4 is on x3 instead of the table and there are no blocksabove x4, so f (x4) = 1.Determine if h2 is safe, goal-aware, admissible and/or consistent. Justify your answer foreach property.

onsider the following 8-puzzle problem, answer the questions below.(i)           Draw state space for solving the above 8-puzzle.(ii) Suppose we define heuristic function for this problem as the number of tiles, which are out of place at a given state. For example, in the initial state the tiles 2, 8, 1, 6, 7 are in out of place. Therefore, h(initial) = 5.   And g(n) is defined as the number of levels passed in the state space, g(initial) = 0 By defining f(n) = g(n) + h(n), calculate f(n) for each node in the state space. Hence find the traversal for exploring the state space by the following algorithms. (a) Greedy Search(b) A* Search

Exercise 5.1 (1+1 marks)Execute(a) greedy best-first search (f (n) = h(n.state)) and(b) A∗ (f (n) = g(n) + h(n.state))without reopening in the state space depicted below. As heuristic, use the perfect heuristic h∗.sIs1s2 s3sg515121Describe the execution of both search algorithms with the following schema:1. expanding s10: open = ⟨s11(f = 5), s12(f = 6)⟩, closed = {s10(g = 0)}2. expanding s11: open = ⟨s13(f = 4), s12(f = 6), s16(f = 10)⟩, closed = {s10(g = 0), s11(g = 3)}. . .i. expanding si: found goal with cost xNote: This schema uses fictitious states and numbers that don’t correspond to the given state space

Suppose you were applying the Graph Search version of A* Search to a search problem. Using an admissible heuristic would guarantee that:Group of answer choicesAll nodes expanded by the search algorithm will have the same value of f(n).The first solution found is an optimal solution.The heuristic is also consistent.None of the above.

Heuristic Evaluation

5.2-2. Dijkstra’s link-state routing algorithm. Consider Dijkstra’s link-state routing algorithm that is computing a least-cost path from node a to other nodes b, c, d, e,  f.  Which of the following statements is true.  (Refer to Section 5.2 in the text for notation.)Group of answer choicesSuppose nodes b, c, and d are in the set N’.  These nodes will remain in N’ for the rest of the algorithm, since the least-cost paths from a to b, c, and d are known.The values computed in the vector D(v), the currently known least cost of a path from a to any node v, will always decrease following an iteration.Following the initialization step, if nodes b and c are directly connected to a, then the least cost path to b and c will never change from this initial cost.The values computed in the vector D(v), the currently known least cost of a path from a to any node v, will never increase following an iteration.In the initialization step, the initial cost from a to each of these destinations is initialized to either the cost of a link directly connecting a to a direct neighbor, or infinity otherwise.