Assume also that the ESTIMATED distances to the goal are given by the following table:

For EACH of the following search methods:

• (10 points) Construct the search tree and mark in it the order in which the nodes/paths are EXPANDED by the search method while looking for a solution. When everything else is equal, order the children of a node in alphabetical order.
• (10 points) Display the state of the queue after each expansion of a node in the search tree.
• (3 points) Write down the solution path from S to G (if any) found by the method.
• (2 point) Write down the cost of the solution path found by the method.

---

1. Depth 1st Search

   Search Tree:

             S
            / \ 
           A   F
          / \
         C   F
        / \
       D   G
       |    
       G
       * goal
   

   Queue:

   Depth First
      Expanded  Queue
         S      [(S)]
         A      [(A,S) (F,S)]
         C      [(C,A,S) (F,A,S) (F,S)]
         D      [(D,C,A,S) (G,C,A,S) (F,A,S) (F,S)]
         G      [(G,D,C,A,S) (G,C,A,S) (F,A,S) (F,S)]
         goal reached!
   

   List of expanded nodes: [S, A, C, D, G]

   Resulting path: SACDG

   Cost of resulting path: 12

   ---

2. (25 points) Breadth 1st Search

   Search Tree:

   Queue:

   List of expanded nodes:

   Resulting path:

   Cost of resulting path:

   ---

3. (25 points) Iterative Deepending

   Search Tree:

   Queue:

   List of expanded nodes:

   Resulting path:

   Cost of resulting path:

   ---

4. (25 points) Branch-and-Bound with Dynamic Programming (= Uniform Cost Search)

   Search Tree:

   Queue:

   List of expanded nodes:

   Resulting path:

   Cost of resulting path:

   ---

5. (25 points) Greedy Search (= Best 1st Search)

   Search Tree:

   Queue:

   List of expanded nodes:

   Resulting path:

   Cost of resulting path:

   ---

6. (25 points) A*

   Search Tree:

   Queue:

   List of expanded nodes:

   Resulting path:

   Cost of resulting path:

   ---

7. (25 points) Hill-climbing

   Search Tree:

   Queue:

   List of expanded nodes:

   Resulting path:

   Cost of resulting path:

   ---

8. (25 points) Beam search (w=2)

   Search Tree:

   Queue:

   List of expanded nodes:

   Resulting path:

   Cost of resulting path:

   ---