Breadth-first graph search problem

Question

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:

1. Enqueue the root node S. Queue = [S], Path = []
2. Dequeue S and examine it. Queue = [], Path = [S]
3. Enqueue S's children, A and C. Queue = [A, C], Path = [S]
4. Dequeue A and examine it. Queue = [C], Path = [S, A]
5. A has no children. Dequeue C and examine it. Queue = [], Path = [S, A, C]
6. Enqueue C's children B and G. Queue = [B, G], Path = [S, A, C]
7. Dequeue B and examine it. Queue = [G], Path = [S, A, C, B]
8. B's only child G is already in the queue. Queue = [G], Path = [S, A, C, B]
9. 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?

Answer 1

The problem appears to be that your answer is the order in which the nodes are evaluated by the breadth first search but what the questions asks for is the final path from S to G that the search would find.

I think the answer the question is looking for is SCG.

Easiest way to confirm would be to talk to your instructor.

(A depth first search using the same alphabetical precedence rules would return SCBG as the path.)

Answer 2

Since nobody provided the details yet, here is your answer with correction:

1. Enqueue the root node S. Queue = [S], Path = []
2. Dequeue S and examine it. Queue = [], Path = [S]
3. Enqueue S's children, A and C. Queue = [A, C], Path = [S]
4. Dequeue A and examine it. Queue = [C], Path = [S, A]
   -> All correct so far
5. A has no children. Dequeue C and examine it. Queue = [], Path = [S, C]
   -> This is where the mistake was: A is removed from the path, as well, since it has no children; the search switches from path S-A (a dead end) to path S-C now.
6. Enqueue C's children B and G. Queue = [B, G], Path = [S, C]
   -> Correct, except the current path is S-C (not S-A-C).
7. Dequeue B and examine it. Queue = [G], Path = [S, C, B]
8. B's only child G is already in the queue. Queue = [G], Path = [S, C, B]
   -> Correct, with the same correction as above (A is not in the path anymore).
9. Dequeue the goal node G and examine it. Quit the search and return. Queue = [], Path = [S, C, G]
   -> Dequeue G and examine it, find it's a goal, stop. Same mistake as above: B is removed from the path, and the search switches from path S-C-B to S-C-G (which happens to be the solution path).

Note that, if all edges have the same weight (of 1, as is your case), then breadth-first search finds the shortest path (minimum number of steps).