A traveler visits the eight places as shown below from S to G. Some pairs of places are connected to each other by Bidirectional bridges running over water. Traveller hates to cross these bridges as they require a lot of efforts. He is standing at place #S and wants to reach the destination #G. Find the minimum the number of bridges that he shall have to cross, if he takes the optimal route.

a. Explain the cost function associated with your search in reaching the goal

b. Use the best algorithm suitable for this search c. Implement the algorithm in PYTHON d. Print the path taken by the traveller. e. Print the minimum the number of bridges that he shall have to cross.

which is the best algorithm to implement this question? Is Iterative deepening A* algorithm or IDDFS or BIDDFS good?

4 A 11 18 1 9 3 1 G S 16 5 2 2