开发者

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 myse开发者_StackOverflow中文版lf 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.


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.


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜