java - 深度优先搜索错误

Question

我正在做一个编程作业(用java)来解决a fifteen-puzzle sort of thing 。第一部分是使用深度优先搜索来寻找解决方案。我希望它能够解决任意大的难题，因此整个状态空间图可能无法放入内存中。相反，该算法将保留一个已探索状态的列表，以检查 future 的状态。该算法是这样的:

如果我们处于目标状态，那么我们就完成了。
如果没有，则对于不在探索列表中的每个邻居，将其添加到探索列表中并递归地深度优先搜索它。

但是，它无法正常工作。我做了一些测试，我认为问题在于，当我将状态插入探索列表时，它实际上插入了相同的对象，因此当我稍后更改状态时，探索列表也会发生变化。因此，程序永远不会认为某个状态尚未被探索过。

我尝试编写一个方法来复制状态，并将副本传递给探索列表；但同样的问题仍然存在。但是，当我独立测试复制方法时，它似乎成功复制了状态。我完全不知道问题出在哪里。

涉及到的代码比较多，不知道问题出在哪里，但是这里是深度优先搜索的代码:

this class we're in is the puzzle class, and this is the depth first search
'state' keeps track of the current state we're in
'explored' is a linked list of explored states

public String depthFirst(){
    state.clearPath();            // state keeps track of the path taken
    explored = new LLNode(state); // create explored list with starting state
    this.dfs();                   // depth first search
    return state.path();
}

private boolean dfs(){
    if(state.equals(goal))        // if we're in the goal state, then done
        return true;
    char[] directions = {'n', 'e', 's', 'w'};
    for(char dir : directions){   // otherwise, for each direction
        if(state.move(dir)){      // if we can move in that direction, then do
            if(!explored.contains(state)){  // if the new state is unexplored
                explored = explored.insert(state.copy());
                if(this.dfs())              // add it to explored and recurse
                    return true;
            }
            switch(dir){                    // if search failed, move back and
                                            // search the next direction
                case 'n': state.move('s');
                case 'e': state.move('w');
                case 's': state.move('n');
                case 'w': state.move('e');
            }
        }
    }
    return false;  // indicates failure
}

以下是探索的插入和包含方法:

public LLNode insert(Node gameState){
    if(state == null){        // if this list node doesn't have a state
        state = gameState;    // then give it this one
        return this;
    }                         // otherwise tack it on the front of the list
    return new LLNode(gameState, this);  // and return the new head
}

public boolean contains(Node gameState){
    // I had a test here that printed a message if (state == gameState)
    // which was triggered when I ran the program, suggesting the problem
    // I explained above
    if(state.equals(gameState))
        return true;
    else if(next == null)
        return false;
    else
        return next.contains(gameState);
}

这是 Node 类的复制函数

public Node copy(){
    int[][] newState = new int[state.length][state[0].length];
    for(int i = 0; i < state.length; ++i)
        for(int j = 0; j < state[0].length; ++j)
            newState[i][j] = state[i][j];
    return new Node(newState);
}

感谢您的任何想法!

Answer 1

我会检查 state.move() 根本没有引用 explored - 查看提供的代码，这是我可以想象您的变量可能引用相同数组的唯一地方。

作业是否要求滚动您自己的数据结构(即链表)？如果没有，那么我会使用标准的 Java HashSet (或任何最适合您的要求的内容)，因为我认为不需要记住搜索的顺序，只需记住您已经探索了特定状态这一事实。

此外，是否有必要为每个探索的状态存储整个数组？只记住每个探索状态的哈希值(可以将其存储在 HashSet 中)可能会更好(消耗更少的内存，并且通常更高效)。

注意:您的 copy() 方法假定一个 NxN 数组(这对于您的示例来说很好，但如果拼图是矩形则不起作用)。