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

A problem in a search space is defined by one of this state.Initial stateLast stateIntermediate stateAll of the mentioned

Suppose you are applying the Tree Search version of Greedy Best-First Search to a search problem. Using an admissible heuristic would guarantee:Group of answer choicesTermination whenever the set of states is finite.Optimality of the first solution found.Consistency of the heuristic.None of the above. Flag question: Question 5

Which search is complete and optimal when h(n) is consistent?ans.Best-first searchA* searchDepth-first searchBoth Best-first & Depth-first search Previous Marked for Review Next

Question No. 6Marks : 1.00    Hill-climbing search           Breadth-first search           Forward state-space search           Depth-first search

(a) You will investigate various search algorithms for the graph in figure 1. Edges arelabeled with their costs, and heuristic values h for states are labeled next to thestates. S is the start state, and G is the goal state. For each of the following graphsearch strategies, work out the order in which states are expanded, the path returnedby graph search, the path cost, as well as the states that are not expanded. In allsearch algorithms, assume ties are broken in alphabetical order. Draw search tree foreach search strategy to illustrate your answer.Figure 1: Search graph 12 of 5(i) Depth first search [ 3 marks](ii) Breadth First search [ 3 marks](iii) Uniform cost Search [ 4 marks](iv) A* search [4 marks](v) Greedy Search [ 2 marks](b) The heuristic values for the graph in figure 2 are not correct. For which single state (S,A, B, C, D, or G) could you change the heuristic value to make everything admissibleand consistent? What range of values are possible to make this correction? [ 4marks]Figure 2: Search graph 2Question 3(a) Explain the role probability play in Artificial Intelligence. [2 marks](b) Covid-19, Maleria and Paralysis diseases cases have been reported in Makerere Uni-versity. The Ministry of Healthy has sent a team of experts to perform a diseasediagnosis to patients suspected being suffering from the diseases within Makerereand report on their rampage as soon as possible. But as they try to perform thedisease diagnostics, they discover that these diseases exhibit similar symptoms whichmakes the diagnosis process much more complicated, thus delaying the results. Inorder to reduce on the time delay in the provision of diagnostics results in the nearfuture, they have proposed using a machine learning diagnosis system and you havebeen approached to assist in the development of such systems. Using the knowledgeof Artificial intelligence and probability theory, discuss the steps you would followin developing such a system. You should clearly state the assumptions and relevantexamples for full marks. [18 marks]