For the graph below, the start node is S and the goal node is G. The cost of traversing an edge is inside the rounded rectangles on top of the edge. The estimated cost to a goal from a node is inside the node below the label (e.g. below the letter).

For each search strategy listed below, indicate the solution path. Some search strategies may not reach a goal node.

In addition, list, in order, the nodes that are visited. These are nodes that are popped off the open list and expanded. If there is a tie when choosing nodes, pick the node whose label comes first in the alphabet. For example, if the choices are A or B and the algorithm ranks them as a tie, pick A.

Best First

Hill Climbing

Uniform Cost

A* Search