Question $45$

Consider the search problem represented in the following figure, where $a$ is the start node and there are goal nodes at $f$ and $j.$ For each node, the

heuristic cost is indicated on the node, and for each arc, the arc cost is indicated along the arc. Neighbors are ordered according to the f function. The

following questions based on applying the branch & bound search on this problem.

a$)$ In branch & bound search, how is the upper bound calculated? What is the upper bound when only the start node has been explored? $[1$

points$]$

b$)$ How is the lower bound calculated for a path? Which goal node is found first by the branch & bound search? What is the upper bound

immediately after the first goal node is found? $[2$points$]$

c$)$ With branch & bound search, when do we prune a path? Is the second goal found by this search or not and why? $[2$ points$]$