How can I modify the breadth-first search algorithm to also include the solution path?

I have the following pseudo-code in my book for a breadth-first search:

function breadth_first_search:
    begin
        open := [Start]
        closed := [];
        while open != [] do
            begin
                remove leftmost state from open, call it X;
                    if X is a goal then return SUCCESS
                        else begin
                            generate children of X;
                            put X on closed;
                            discard children of X if already on open or closed;
                            put remaining children on right end of open;
                        end
            end
       return FAIL;
    end

I've implemented a similar algorithm myself following these pseudo-code instructions. My question is, what is the simplest way to modify it so it maintains the solution path?

Simply knowing I can reach a solution isn't nearly as useful as having a list of transitions to get to the solution.

13.10.2009 19:56:26
Look at stackoverflow.com/questions/1579399/…; I've implemented the correct solution, but it's in Java.
giolekva 16.10.2009 19:28:27
2 ОТВЕТА
РЕШЕНИЕ

Is there any possibility for you to change the Tree structure? If so, you might want to add a parent pointer in each node/leaf so when you find the solution you go up following parent pointers up to the root.

3
13.10.2009 20:01:47

Set Parent[childNode] = currentNode as you enqueue each node (when you set Visible[Node] = 1).

Then recursively look up the Parent array, starting at the node you want and append each node you see in the Parent array to the path. Parent[root] is nil and the recursion will stop there.

6
13.10.2009 19:59:15