8. Consider the search graph below, where S is the start node and G1, G2, and G3 are goal states. Arcs are labelled with the cost of traversing them and the heuristic cost to a goal is shown inside the nodes. 10 10 3 11 10 a. For each of the search strategies below, indicate which of the goal states is reached first and write the complete path of nodes from the start node to the goal: i. Depth First Search ii. Breadth First Search iii. Greedy search iv. A* search b. Assume closeness between two nodes computed based on the straight line distance between them. Use Hill Climbing to find the path to G2 (draw the search tree). 0