BFS函数是否正确？

Question

问题是使用bfs函数构造/找到一个peg solitare博弈的解。您将看到一个包含开始状态的节点，该节点将从此状态扩展到更多状态(其子节点)。一旦找到包含目标状态的节点，该函数就会停止。

public void search(){
    bfs.add(StartGoal);
while(!bfs.isEmpty()) {
    node = bfs.poll();  
    if(node.isGoal()){System.out.println("success"); return;}
    node.expand();
    for(MyNode m : node.childs){
        if(!m.isGoal()){
            m.setVisited();
            bfs.add(m);}}
        node.setVisited();
    }

expand函数初始化childs linkedlist，并根据下一个可能的板子状态创建子节点。

public void expand(){
    if(childs != null) return;//already expanded do nothing
    else{
    childs= new LinkedList<MyNode>();
    for(BoardState b: state.nextStates())
        childs.add(new MyNode(this, b));}   
}

我运行了代码，并对其进行了多次改进。一旦队列的大小达到3+百万，它就会因为空间不足而崩溃。我的问题是:这最终会奏效吗？代码是否正确？

这是我的第一篇文章，如果我的问题表达得很糟糕，我很抱歉。谢谢。

Answer 1

您的代码不正确。我看到了两个大的bug，或者可能是一个具有两个主要后果的大bug和一个小bug。可能还有其他我看不到的bug，而且肯定还有其他需要改进的地方。第一个错误是

    if(!m.isGoal()){
        m.setVisited();
        bfs.add(m);}}

明确地说，您从不将目标状态添加到队列中。

第二个bug是您永远不会测试节点是否被访问过。这可能是与第一个相同的错误，因为看起来它们可能可以通过相同的修复程序进行修复：

if (!m.isVisited()) {

第三个bug是，在处理第一个子节点之后，只标记访问过的节点。如果节点没有子节点，则永远不会将其标记为已访问，如果节点可以将其自身作为子节点，则可以在展开父节点之前将子节点添加到队列中。这不会影响你的结果的正确性，尽管它可能会影响你的效率。