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

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，递归将停在那里。

Answer 2

您是否有可能更改树结构？如果是这样，您可能希望parent在每个节点/叶中添加一个指针，这样当您找到解决方案时，您会沿着父指针向上移动到根。