Question $3$ The map below shows the distances $($in miles$)$ between some major cities in the US$.$ Your friend is traveling from Chicago $($Start$)$ to New York $($Goal$)$ and needs your help to find the route with the shortest distance $($in miles$).$ Note: your answers should be based on the costs given, no heuristic values are available.

$($a$)$ From the list of search methods given below, which search method can you use to find the route with the shortest distance? Search strategies: BFS$,$ DFS$,$ Iterative Deepening DFS$,$ Uniform cost search,

Hill Climbing, Best$-$first search, Algorithm A$.$

$($b$)$ Apply your search method of choice to the problem. Show the states $($cities$)$ visited, along with the open and closed lists at each step $($if it applies$).$ Stop once the goal state $($New York$)$ is visited.

$($c$)$ Based on your search method, what route should your friend follow? What is the cost of this path?