(d) Consider the directed graph shown in Figure Q2(d), S is the start state and G1,G2,...

Transcribed Image Text:

(d) Consider the directed graph shown in Figure Q2(d), "S" is the start state and "G1,G2, G3" are 3 goal states. When traversing the graph, one can move only in the direction indicated by the arrows. The numbers on the edges indicate the step-cost for traversing that edge. The numbers in the nodes represent the estimated cost to the nearest goal state. For each search strategies below: a Greedy Best First Search b Depth-First Search C Uniform Cost Search Answer the following questions: i. Trace out the steps of each search. ii. Show the solution path from the start state to the goal state. iii. Calculate the total cost to the goal. iv. Is this guaranteed to be the optimal solution? v. Determine the time and space complexity of each search. [3 x 5 Marks] 5 3 4 10 G1 0 2 E 1 5 1 5 2 11 (d) Consider the directed graph shown in Figure Q2(d), "S" is the start state and "G1,G2, G3" are 3 goal states. When traversing the graph, one can move only in the direction indicated by the arrows. The numbers on the edges indicate the step-cost for traversing that edge. The numbers in the nodes represent the estimated cost to the nearest goal state. For each search strategies below: a Greedy Best First Search b Depth-First Search C Uniform Cost Search Answer the following questions: i. Trace out the steps of each search. ii. Show the solution path from the start state to the goal state. iii. Calculate the total cost to the goal. iv. Is this guaranteed to be the optimal solution? v. Determine the time and space complexity of each search. [3 x 5 Marks] 5 3 4 10 G1 0 2 E 1 5 1 5 2 11

Answer rating: 100% (QA)

In Tree or graph search there are two types of searching algorithm Uninformed Search Blind search and Informed Search Heuristic Search A search and g ... View the full answer