Problem 1: For the following tree find the path from the start node A to the goal state G using: (show all your work) [25 points] a) Depth First Search. b) Breadth First Search c) Hill Climbing Search d) Best First Search. e) A*Algorithm Problem 2: [20 points] Consider the 8-puzzle problem, where the board is 33 and there are eight tiles, numbered 1,2,3,4,5,6,7 and 8 . There are four moves: move the blank up, right, down, and left. Use A algorithm to find the path from start state to the goal state, where h(n)=3 the number of tiles out of place and g(n)= the actual distance from n to the start state. The start and goal states are: Problem 3: Suppose we have the following problem which is called Towers of Hanoi. Initially, the disks are placed in decreasing size on support 1 , and the objective is to move them to support 3. The conditions for moving the disks are: [20 points] all disks (except the one to be moved) have to be on one the three supports; it is possible to move only one disk at a time, taking it from the top of the tower on of the supports and placing it on the top of the tower on another support; a disk can never be placed on a smaller disk. The initial state and the final state for a set of 3 disks are shown in the following figures. Use A algorithm to find the path from the start state to the goal state