I thought I was doing breadth-first graph search correctly, but my instructor's grading script is telling me that my answer is incorrect.
From the instructions:
Consider a breadth-first graph search on the graph below, where S is the start and G is the goal state. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A). You may find it helpful to execute the search on scratch paper.
Please enter the final path returned by breadth-first graph search in the box below. Your answer should be a string with S as your first character and G as your last character. Don't include arrows or spaces in your submission. For example, if you believe the path is S->X->G, please enter SXG in the box.
I got and input the answer SACBG, which the grading script marked as incorrect. ("Your input was evaluated as SACBG, which is not correct.")
Here are my steps for the breadth-first graph search on the above graph using the algorithm at http://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode:
- Enqueue the root node S. Queue = [S], Path = []
- Dequeue S and examine it. Queue = [], Path = [S]
- Enqueue S's children, A and C. Queue = [A, C], Path = [S]
- Dequeue A and examine it. Queue = [C], Path = [S, A]
- A has no children. Dequeue C and examine it. Queue = [], Path = [S, A, C]
- Enqueue C's children B and G. Queue = [B, G], Path = [S, A, C]
- Dequeue B and examine it. Queue = [G], Path = [S, A, C, B]
- B's only child G is already in the queue. Queue = [G], Path = [S, A, C, B]
- Dequeue the goal node G and examine it. Quit the search and return. Queue = [], Path = [S, A, C, B, G]
A node is placed in the path when it is dequeued and examined.
Ties are broken alphabetically as required in the instructions.
What am I doing wrong?