Question $4$

Searching

$[18]$

Consider the above state graph, with path costs as indicated. Node A is the start node and node J the goal node in this state graph.

$($a$)$ Perform a bi$-$directional search using the breadth$-$first search algorithm to find the lowest cost path between the start node A and the goal node J$.$ Show the expression of the expansion of nodes after each step. Use the lowest path cost to choose the first node to expand at each search step. Show every expansion of each of the two breadth$-$first searches.

$($b$)$ What is the cost of the lowest cost path $($as found by your search$)?$

$(12)$

$($c$)$ Iterative deepening search combines the benefits of depth$-$first and breadth$-$first search. When is iterative deepening the preferred uninformed search method?

$(4)$