骑士旅行问题 - 移动顺序会影响性能

Question

我试图为骑士旅行问题实施解决方案。我面临一个有趣的问题。我想知道行为的原因。

这是代码 - 它可以正常工作。

public class OpenKnightTour {
    private int[][] chessTable;
    private int startRow;
    private int startCol;
    private int ChessBoardSize;

    private final int[][] moves = {
            {-1, -2},
            {-2, -1},
            {-2, 1},
            {-1, 2},
            {1, -2},
            {2, -1},
            {2, 1},
            {1, 2}
    };
    public OpenKnightTour(int ChessBoardSize, int startRow, int startCol){
        this.ChessBoardSize = ChessBoardSize;
        this.startRow = startRow;
        this.startCol = startCol;
        this.chessTable = new int[ChessBoardSize][ChessBoardSize];
    }
    void move(){
        //first move
        this.chessTable[this.startRow][this.startCol] = 1;
        //start with 2nd move recursively
        moveHelper(this.startRow, this.startCol, 2);
        //print results
        this.print();
    }
    private boolean moveHelper(int r, int c, int count){
        if((count-1) == (this.ChessBoardSize * this.ChessBoardSize))
            return true;
        for(int[] move: moves){
            int nextR = r + move[0];
            int nextC = c + move[1];
            if(isMoveValid(nextR, nextC)){
                chessTable[nextR][nextC] = count;
                if(moveHelper(nextR, nextC, count + 1)){
                    return true;
                }
                chessTable[nextR][nextC] = 0;
            }
        }
        return false;
    }
    private void print(){
        Arrays.stream(this.chessTable)
                .forEach(a -> System.out.println(Arrays.toString(a)));
    }
    private boolean isMoveValid(int r, int c){
        if(!(r >= 0 && r < this.ChessBoardSize))
            return false;
        if(!(c >= 0 && c < this.ChessBoardSize))
            return false;
        return chessTable[r][c]==0;
    }
}

现在，我们可以运行此操作，从矩阵中的 (2, 2)开始

中的骑士位置

    OpenKnightTour o = new OpenKnightTour(8, 2, 2);
    o.move();

当我尝试将起始位置作为(0, 0)运行时，它会连续运行而不会显示任何结果。因此，我认为没有任何解决方案。但是，如果我稍微更改订单以下，它立即工作正常。

private final int[][] moves = {
        {-1, -2},
        {-2, -1},
        {-2, 1},
        {-1, 2},
        {1, -2},
        {1, 2}, //moved from last 
        {2, -1},
        {2, 1},
};

到底发生了什么？这种举动的位置如何影响绩效？然后，在这种情况下，我们如何知道动作的正确顺序？

Answer 1

您正在通过非常大的搜索空间进行蛮力搜索。如果您对自己的搜索方式不幸，则可以花费很长时间而没有解决方案。

答案是，要么您可以选择起点/起点模式，否则您需要更聪明地识别"绝望地卡住"。

例如，您回溯每10,000次，对整个板进行扫描。如果您可以找到可能无法回到的孔，请设置一个标志，使您回溯到您可以从中访问的最后一步。然后继续。这使您可以跳过可能无用的大部分工作，然后回到找到许多可能的旅行中之一。