Informed Search

Please put expert answer in python code.

Edit your previous program to solve text-based grids (using DFS and BFS) to solve the grids using A* and greedy search algorithms.

Write the final path to a file (as in the previous assignment), and print the following data to console:

1)If a solution could be found or local minima

2)Number of states expanded

3)Final path (list the locations), if one can be found

4)What heuristic function you used - e.g., Manhattan distance

Edit your program to toggle between using A* and greedy-search without separate functions.

A big difference in this problem is that the values on the grids will have any value from0-9. Any nonzero value represents the step cost to move to that location from any of its neighbors. A value of 0 indicates that the location cannot be traversed. An example grid can be seen below.

1 5 2 4 1 5 1 0 4 0

1 5 0 2 4 1 0 2 5 0

1 0 5 5 1 2 1 4 4 3

2 1 2 2 0 0 2 4 4 0

2 0 4 2 2 1 1 5 1 2

0 3 4 1 3 3 4 2 1 3

1 0 3 5 2 5 1 0 4 3

2 4 0 1 0 2 4 2 4 0

0 4 5 5 2 5 3 1 4 3

3 0 3 3 5 5 3 4 1 1

Instructors helpful hints

You may want separate functions for checking if something is in the open list or in the closed list so that you can return different information based on which one youre checking. Dont forget you can return multiple things from a Python function.

a.For the closed list, we may only be concerned with if a Node is in there. For the open list, we may want more information if a Node is in there.

The expandNode function will need to be more involved to handle the different behaviors of the informed searches