Consider tree search $($i$.$e$.$ no closed set$)$ on an arbitrary search problem with max branching factor b$.$ Each

search node n has a backward $($cumulative$)$ cost of g$($n$),$ an admissible heuristic of h$($n$),$ and a depth of d$($n$).$

Let c be a minimum$-$cost goal node, and let s be a shallowest goal node.

For each of the following, you will give an expression that characterizes the set of nodes that are expanded

before the search terminates. For instance, if we asked for the set of nodes with positive heuristic value, you

could say h$($n$)>=0.$ Don$$t worry about ties $($so you won$$t need to worry about $>$ versus $>=).$ If there are no

nodes for which the expression is true, you must write $$none$.$

$1.$ Give an expression $($i$.$e$.$ an inequality in terms of the above quantities$)$ for which nodes n will be expanded

in a breadth$-$first tree search.

$2.$ Give an expression for which nodes n will be expanded in a uniform cost search.

$3.$ Give an expression for which nodes n will be expanded in an A$$

tree search with heuristic h$($n$).$

$4.$ Let h$1$ and h$2$ be two admissible heuristics such that $$n$,$ h$1($n$)>=$ h$2($n$).$ Give an expression for the nodes

which will be expanded in an A$$

tree search using h$1$ but not when using h$2.$

$5.$ Give an expression for the nodes which will be expanded in an A$$

tree search using h$2$ but not when using

h$1.$

$3$

$(1$ point$)$

$(1$ point$)$

$($