Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

breadth-first search on graph

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.)

share|improve this answer
    
I'm not sure how to get SCG. How would that path be stored/recorded by the algorithm? –  user93172 Sep 7 '13 at 17:13
    
The algorithm you're using there only gets you the breadth first tree, to get the shortest path you need to use Dijkstra's algorithm instead. See this answer for more info. –  combinatorics Sep 8 '13 at 13:19

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.