1. Implement the Search Tree in Python that would find the goal from the Start Node using (Explain the Python structure you are using to implement the Search Tree):

a) A Depth First Search

b) A breadth First Search

2.

a) Draw the search tree for solving this puzzle

b) Implement the Search Tree in Python (State clearly what Python structure you are to use).

c) Find the sequence of states to get from start to goal using:

i) Depth First Search

ii) Breadth First Search

iii) Devise a metric to improve the search using Hill Climbing

iv) Implement a beam search

4 4 A B C 3 S 5 7 4 E F 4 Start Goal 1 4 3 1 2 3 3 7 8 8_ 4 | 6 2 5 7 6 5 4 4 A B C 3 S 5 7 4 E F 4 Start Goal 1 4 3 1 2 3 3 7 8 8_ 4 | 6 2 5 7 6 5