java - 深度优先搜索提前终止

Question

我正在用 Java 创建一个程序来解决 n-puzzle ，不使用启发式方法，只需对状态空间进行深度优先和广度优先搜索。我在实现深度优先搜索时遇到了一些困难。有时它会解决给定的难题，但有时它似乎很早就放弃了。

这是我的 DFS 类。 DepthFirstSearch() 被传递给 PuzzleBoard，它最初是通过洗牌已解决的棋盘生成的(以确保棋盘处于可求解状态)。

public class DepthFirst {
static HashSet<PuzzleBoard> usedStates = new HashSet<PuzzleBoard>(); 

public static void DepthFirstSearch(PuzzleBoard currentBoard)
{   
    // If the current state is the goal, stop.
    if (PuzzleSolver.isGoal(currentBoard)) {    
        System.out.println("Solved!");
        System.exit(0); 
    } 

    // If we haven't encountered the state before,
    // attempt to find a solution from that point.
    if (!usedStates.contains(currentBoard)) {                       
        usedStates.add(currentBoard);           
        PuzzleSolver.print(currentBoard);

        if (PuzzleSolver.blankCoordinates(currentBoard)[1] != 0) {
            System.out.println("Moving left");
            DepthFirstSearch(PuzzleSolver.moveLeft(currentBoard));
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[0] != PuzzleSolver.n-1) {
            System.out.println("Moving down");
            DepthFirstSearch(PuzzleSolver.moveDown(currentBoard)); 
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[1] != PuzzleSolver.n-1) {
            System.out.println("Moving right");
            DepthFirstSearch(PuzzleSolver.moveRight(currentBoard)); 
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[0] != 0) {
            System.out.println("Moving up");
            DepthFirstSearch(PuzzleSolver.moveUp(currentBoard));    
        }

        return; 
    } else {
        // Move up a level in the recursive calls
        return; 
    }
}   
}

我可以断言我的 moveUp()、moveLeft()、moveRight() 和 moveDown() 方法和逻辑工作正常，所以问题一定出在其他地方。

这是我的带有 hashCode 和 equals 方法的 PuzzleBoard 对象类:

static class PuzzleBoard {
    short[][] state;        
    /**
     * Default constructor for a board of size n
     * @param n Size of the board 
     */
    public PuzzleBoard(short n) {
        state = PuzzleSolver.getGoalState(n);
    }
    public PuzzleBoard(short n, short[][] initialState) {
        state = initialState; 
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + Arrays.deepHashCode(state);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        PuzzleBoard other = (PuzzleBoard) obj;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (state[i][j] != other.state[i][j])
                    return false; 
            }
        }
        return true;
    }   
}

如前所述，有时搜索工作正常并找到解决方案的路径，但有时它会在找到解决方案之前和内存耗尽之前停止。

这是输出的一个片段，在搜索停止之前开始了一些 Action 。

...
Moving down
6 1 3 
5 8 2 
0 7 4 
Moving right
6 1 3 
5 8 2 
7 0 4 
Moving left
Moving right
Moving up
6 1 3 
5 0 2 
7 8 4 
Moving left
Moving down
Moving right
Moving up
Moving up
Moving right
Moving down
Moving up
Moving down
Moving up
Moving down
Moving up
Moving down
Moving up
Moving down
...

为了简洁起见，我提前截断了它，但它最终只是上下移动了几十次，从未达到解决状态。

任何人都可以阐明我做错了什么吗？

编辑:这里是 MoveUp()。其余的移动方法以相同的方式实现。

/**
 * Move the blank space up
 * @return The new state of the board after the move
 */
static PuzzleBoard moveUp(PuzzleBoard currentState) {
    short[][] newState = currentState.state; 
        short col = blankCoordinates(currentState)[0]; 
        short row = blankCoordinates(currentState)[1]; 
        short targetCol = col; 
        short targetRow = row; 
        newState[targetCol][targetRow] = currentState.state[col - 1][row];
        newState[targetCol - 1][targetRow] = 0; 

        return new PuzzleBoard(n, newState); 
    }

Answer 1

过去，我遇到过很多关于哈希集的问题，最好的尝试是不要将对象存储在哈希集中，而是尝试将您的对象编码为字符串。

这里有一个方法:-

StringBuffer encode(PuzzleBoard b) {

   StringBuffer buff = new StringBuffer();

    for(int i=0;i<b.n;i++) {

      for(int j=0;j<b.n;j++) {

          // "," is used as separator
            buff.append(","+b.state[i][j]);

      }
   }
   return buff;
}

Make two changes in the code:-

if(!usedStates.contains(encode(currentBoard))) {

usedStates.add(encode(currentBoard));
......

}

注意:-这里不需要编写您自己的哈希码函数，也不需要实现 equals 函数，因为 java 已经在 StringBuffer 中为您完成了。