^{Please provide the path found by the greedy search}

Consider the problem of finding a path in the grid shown below from the position to the position G. The agent can move on the grid horizontally and vertically, one square at a time (each step has a cost of one). No step may be made into a forbidden crossed area. (a) Number the nodes in order in which they are traversed in a greedy search. Manhattan distance should be used as the heuristic function. That is, h(n) for any node n is the Manhattan distance from n to G. The Manhattan distance between two points is the distance in the x-direction plus the distance in the y-direction. It corresponds to the distance traveled along city streets arranged in a grid. For example, the Manhattan distance between G and S is 4. What is the path that is found by the greedy search? (b) Number the nodes in order in which they are traversed in an A* search. Manhattan distance should be used as the heuristic function. What is the path that is found by the A* search? G S