如何修改广度优先搜索算法以包含解决方案路径？

Question

我的书中有以下伪代码用于广度优先搜索:

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

我自己遵循这些伪代码指令实现了类似的算法.我的问题是,修改它的最简单方法是什么,以便维护解决方案路径？

简单地知道我可以达到一个解决方案并不像有一个转换列表来获得解决方案.

Answer 1

设置Parent[childNode] = currentNode为你排队的每个节点(当你设置Visible[Node] = 1).

然后递归地查找Parent数组,从您想要的节点开始,并将您在Parent数组中看到的每个节点附加到路径.Parent[root]是的nil,递归将停在那里.