Clever Geek Handbook

How do I change the Breadth First Search algorithm to include the solution path as well?

I have the following pseudocode in my book for 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 have implemented a similar algorithm following these pseudocode instructions. My question is, what's the simplest way to change it so that it supports the solution path?

Just knowing that I can find a solution is not as useful as a jump list to get to a solution.

+2


source to share


2 answers


Is it possible to change the tree structure? If so, you can add a pointer parent

to every node / leaf, so when you find the solution you hoist, follow the parent's pointers to the root.



+3


source


Install Parent[childNode] = currentNode

when you enqueue each node (on install Visible[Node] = 1

).



Then recursively find the array Parent

starting at the node you want and add each node you see in the array Parent

to the path. Parent[root]

nil

and the recursion will stop there.

+6


source






More articles:


All Articles