(SUBJECT IS AI) Search Algorithms: for each of the following search strategies, execute a tree search through the given graph from Start to Goal. Expand each state only once (handle repetitions). Show the order in which states are expanded and the path returned by each search algorithm. Ties are solved in alphabetical order. Step costs are given next to each arc. Heuristic values are given in the table below.

Depth-first search [4 points]

- States expanded:

- Path found:

Breadth-first search [4 points]

- States expanded:

- Path found:

Uniform cost search [4 points]

- States expanded:

- Path found:

Greedy (best-first) search [4 points]

- States expanded:

- Path found:

A* search [4 points]

- States expanded:

- Path found:

\begin{tabular}{|l|l|} \hline node & h(n) \\ \hline Start & 6 \\ \hline A & 5 \\ \hline B & 5 \\ \hline C & 1 \\ \hline D & 1 \\ \hline Goal & 0 \\ \hline \end{tabular}