Find the path from node A to node G using breadth$-$first search, depth$-$first search,

hill$-$climbing and A$*$ search.

Instruction: For each search algorithm, $(1)$ draw a search tree with node A as the initial state, $(2)$

label nodes in this tree by the order of explorations, and $(3)$ write down the path and the path

length. You do NOT need to draw the complete search tree. Draw only the part explored in each

algorithm.

Rubric: For each search algorithm, $4$ points are given to a correct search tree, $4$ points are given

to the right labeling of nodes by the order of explorations, and $2$ points are given to the right

path $($i$.$e$.$ solution$)$ and path length $($i$.$e$.$ total cost of solution$).$