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