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

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

您正在通过非常大的搜索进行暴力搜索 space。如果您的搜索方式不走运，您可能会花很长时间都找不到解决方案。

答案是要么你幸运地选择了开始 place/starting 模式，要么你需要更聪明地识别 "hopelessly stuck".

例如，每回溯 10,000 次，扫描整个棋盘。如果你能找到你不可能回到的洞，然后设置一个标志，让你回溯到你可以访问它的最后一步。然后继续。这使您可以跳过一大堆可能无用的工作，并返回寻找要找到的 many possible tours 之一。

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

Knight tour problem - order of moves affect performance

java

algorithm

recursion

backtracking

knights-tour