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

(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.

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

Exercise 5: A smaller rowboatIn the traditional version of this puzzle the robot can only fit one thing on the boat with it. The state space is still the same, but fewer transitions are possible.Using the diagram with the possible states below as a starting point, draw the possible transitions in it (it is MUCH easier to do this with a pencil and paper than without).Having drawn the state transition diagram, find the shortest path from NNNN to FFFF, and calculate the number of transitions on it.Please type your answer as the number of transitions in the shortest path (just a single number like "12"). Do NOT include any further description of your solution. Hint: Do not count the number of states, but the number of transitions. For example, the number of transitions in the path NNNN→FFNF→NFNF→FFFF is 3 instead of 4.

Exercise 3.2 (1+1+1 marks)Consider a search problem on a square grid of size 2n + 1 (for n ∈ N). An agent is initially locatedin state sI in the grid cell with coordinates (n + 1, n + 1) and has the goal to reach state sG locatedin the grid cell with coordinates (n + 1, 1). The agent has the possibilities to move north, east,south, and west in the grid if there is a grid cell in the corresponding direction (otherwise, thecorresponding action is not applicable). We assume that the agent uses breadth-first search tocompute a solution.1 . . . n n+11 sG. . .nn+1 sI(a) What is the minimum number of search nodes that are inserted into the open list until theagent finds a solution using tree search (BFS-Tree)? Give an answer as a function of n andjustify your answer.(b) How does that answer differ when using graph search (BFS-Graph)?(c) Compare the number of search nodes that are inserted into the open list in the last searchlayer that are created completely for grids with n = 10 and n = 20 for tree search and graphsearch and discuss the results.

There is a circle of red and blue tiles. You are given an array of integers colors. The color of tile i is represented by colors[i]:colors[i] == 0 means that tile i is red.colors[i] == 1 means that tile i is blue.Every 3 contiguous tiles in the circle with alternating colors (the middle tile has a different color from its left and right tiles) is called an alternating group.Return the number of alternating groups.Note that since colors represents a circle, the first and the last tiles are considered to be next to each other. Example 1:Input: colors = [1,1,1]Output: 0Explanation:Example 2:Input: colors = [0,1,0,0,1]Output: 3Explanation:Alternating groups: Constraints:3 <= colors.length <= 1000 <= colors[i] <= 1