3. A* Search algorithm with Manhattan distance as a heuristic. Diagonal movement is not allowed, in case of a tie, choose the leftmost node. ( 2 points) a. Find a real cost of arcs and heuristic cost for each node. Mark the nodes that are explored. b. Draw a search tree. Write g,h, and f next to each node. c. Number the nodes according to the exploration. d. List the nodes in the fringe at every step. e. Write down the chosen path