c++ - 如何优化 Knight 的游览算法？

Question

我使用Backtracking方法在 C++ 中编写了Knight's tour算法。但是对于 n > 7（大于 7 x 7 棋盘），它似乎太慢或陷入无限循环。

问题是：这个算法的时间复杂度是多少，我该如何优化它？！

---

骑士之旅问题可以表述如下：

给定一个有 n × n 个方格的棋盘，为骑士找到一条恰好访问每个方格一次的路径。

这是我的代码：

#include <iostream>
#include <iomanip>

using namespace std;

int counter = 1;
class horse {
  public:
    horse(int);
    bool backtrack(int, int);
    void print();
  private:
    int size;
    int arr[8][8];
    void mark(int &);
    void unmark(int &);
    bool unvisited(int &);
};

horse::horse(int s) {
    int i, j;
    size = s;
    for (i = 0; i <= s - 1; i++)
        for (j = 0; j <= s - 1; j++)
            arr[i][j] = 0;
}

void horse::mark(int &val) {
    val = counter;
    counter++;
}

void horse::unmark(int &val) {
    val = 0;
    counter--;
}

void horse::print() {
    cout << "\n - - - - - - - - - - - - - - - - - -\n";
    for (int i = 0; i <= size - 1; i++) {
        cout << "| ";
        for (int j = 0; j <= size - 1; j++)
            cout << setw(2) << setfill ('0') << arr[i][j] << " | ";
        cout << "\n - - - - - - - - - - - - - - - - - -\n";
    }
}

bool horse::backtrack(int x, int y) {
    if (counter > (size * size))
        return true;

    if (unvisited(arr[x][y])) {
        if ((x - 2 >= 0) && (y + 1 <= (size - 1))) {
            mark(arr[x][y]);
            if (backtrack(x - 2, y + 1))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x - 2 >= 0) && (y - 1 >= 0)) {
            mark(arr[x][y]);
            if (backtrack(x - 2, y - 1))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x - 1 >= 0) && (y + 2 <= (size - 1))) {
            mark(arr[x][y]);
            if (backtrack(x - 1, y + 2))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x - 1 >= 0) && (y - 2 >= 0)) {
            mark(arr[x][y]);
            if (backtrack(x - 1, y - 2))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x + 2 <= (size - 1)) && (y + 1 <= (size - 1))) {
            mark(arr[x][y]);
            if (backtrack(x + 2, y + 1))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x + 2 <= (size - 1)) && (y - 1 >= 0)) {
            mark(arr[x][y]);
            if (backtrack(x + 2, y - 1))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x + 1 <= (size - 1)) && (y + 2 <= (size - 1))) {
            mark(arr[x][y]);
            if (backtrack(x + 1, y + 2))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x + 1 <= (size - 1)) && (y - 2 >= 0)) {
            mark(arr[x][y]);
            if (backtrack(x + 1, y - 2))
                return true;
            else
                unmark(arr[x][y]);
        }
    }
    return false;
}

bool horse::unvisited(int &val) {
    if (val == 0)
        return 1;
    else
        return 0;
}

int main() {
    horse example(7);
    if (example.backtrack(0, 0)) {
        cout << " >>> Successful! <<< " << endl;
        example.print();
    } else
        cout << " >>> Not possible! <<< " << endl;
}

上面示例 (n = 7) 的输出如下所示：

Answer 1

由于在每个步骤中您有 8 种可能性进行检查，并且必须对每个单元格（减去最后一个单元格）进行检查，因此该算法的时间复杂度为 O(8^(n^2-1)) = O(8^( n^2)) 其中 n 是棋盘边缘的方格数。准确地说，这是最坏情况下的时间复杂度（如果没有找到或者是最后一种可能性，则探索所有可能性所花费的时间）。

至于优化，可以有两种改进：

实施改进

您正在计算 x-2、x-1、x+1、x+2 和 y 至少两倍的时间。我可以建议重写这样的东西：

int sm1 = size - 1;
int xm2 = x - 2;
int yp1 = y + 1;
if((xm2 >= 0) && (yp1 <= (sm1))){
    mark(arr[x][y]);
    if(backtrack(xm2, yp1))
        return true;
    else
        unmark(arr[x][y]);
}

int ym1 = y-1;
if((xm2 >= 0) && (ym1 >= 0)){
    mark(arr[x][y]);
    if(backtrack(xm2, ym1))
        return true;
    else
        unmark(arr[x][y]);
}

注意在后续块中也重复使用预先计算的值。我发现这比我所期待的更有效；这意味着变量分配和调用比再次执行操作更快。还要考虑在构造函数中保存sm1 = s - 1;andarea = s * s;而不是每次都计算。

但是，这（作为实现改进而不是算法改进）不会改变时间复杂度顺序，只会将时间除以某个因子。我的意思是时间复杂度 O(8^(n^2)) = k*8^(n^2) 并且差异将在较低的 k 因子中。

算法改进

我可以这样想：

• 对于从对角线中的一个单元格开始的每次旅行（例如在您的示例中从 (0,0) 开始），您可以认为只有第一个移动位于对角线创建的两个半棋盘之一上。
  • 这是因为 simmetry 或者它存在 2 个 simmetric 解决方案或没有。
  • 对于这种情况，这给出了 O(4*8^(n^2-2)) ，但对于非对称的情况仍然如此。
  • 请注意，再次 O(4*8^(n^2-2)) = O(8^(n^2))
• 如果某些全球情况表明在当前标记下无法解决问题，请尝试尽早中断匆忙。
  • 例如，马不能跳过两个大容量列或行，所以如果你有两个大容量标记的列（或行）和两侧的未标记单元格，你肯定不会有解决方案。考虑到这可以在 O(n) 中检查，如果您保持每列/行更新的标记单元格的数量。然后，如果您在每次标记后检查此内容，则添加 O(n*8^(n^2)) 时间，如果 n < = 8，这还不错。解决方法就是不检查 alwais，但可能每 n/8 个标记（检查counter % 8 == 4例如或更好counter > 2*n && counter % 8 == 4
• 找到其他想法巧妙地提前中断搜索，但请记住，具有 8 个选项的回溯算法将始终具有 O(8^(2^n)) 的性质。

再见

Answer 2

这是我的 2 美分。我从基本的回溯算法开始。正如你提到的，它无限期地等待 n > 7。我实现了 warnsdorff 规则，它就像一个魔术一样工作，并且对于直到 n = 31 的大小板在不到一秒的时间内给出结果。对于 n > 31，它给出了 stackoverflow 错误，因为递归深度超过了限制。我可以在这里找到更好的讨论，讨论警告多夫规则的问题和可能的进一步优化。

仅供参考，我提供了带有warnsdorff优化的Knight's Tour问题的python实现

    def isValidMove(grid, x, y):
            maxL = len(grid)-1
            if x  maxL or y  maxL or grid[x][y] > -1 :
                    return False
            return True

    def getValidMoves(grid, x, y, validMoves):
            return [ (i,j) for i,j in validMoves if isValidMove(grid, x+i, y+j) ]

    def movesSortedbyNumNextValidMoves(grid, x, y, legalMoves):
            nextValidMoves = [ (i,j) for i,j in getValidMoves(grid,x,y,legalMoves) ]
            # find the number of valid moves for each of the possible valid mode from x,y
            withNumNextValidMoves = [ (len(getValidMoves(grid,x+i,y+j,legalMoves)),i,j) for i,j in nextValidMoves]
            # sort based on the number so that the one with smallest number of valid moves comes on the top
            return [ (t[1],t[2]) for t in sorted(withNumNextValidMoves) ]


    def _solveKnightsTour(grid, x, y, num, legalMoves):
            if num == pow(len(grid),2):
                    return True
            for i,j in movesSortedbyNumNextValidMoves(grid,x,y,legalMoves):
            #For testing the advantage of warnsdorff heuristics, comment the above line and uncomment the below line
            #for i,j in getValidMoves(grid,x,y,legalMoves):
                    xN,yN = x+i,y+j
                    if isValidMove(grid,xN,yN):
                            grid[xN][yN] = num
                            if _solveKnightsTour(grid, xN, yN, num+1, legalMoves):
                                    return True
                            grid[xN][yN] = -2
            return False

    def solveKnightsTour(gridSize, startX=0, startY=0):
            legalMoves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
            #Initializing the grid
            grid = [ x[:] for x in [[-1]*gridSize]*gridSize ]
            grid[startX][startY] = 0
            if _solveKnightsTour(grid,startX,startY,1,legalMoves):
                    for row in grid:
                            print '  '.join(str(e) for e in row)
            else:
                    print 'Could not solve the problem..'

Answer 3

检查你的算法。在每个递归深度，您检查 8 个可能的移动中的每一个，检查哪些在棋盘上，然后递归处理该位置。什么数学公式最能描述这种扩展？

你有一个固定的板尺寸，int[8][8]，也许你应该让它动态，

class horse
{
    ...
    int** board; //[s][s];
    ...
};

horse::horse(int s)
{
    int i, j;
    size = s;
    board = (int**)malloc(sizeof(int*)*size);
    for(i = 0; i < size; i++)
    {
        board[i] = (int*)malloc(sizeof(int)*size);
        for(j = 0; j < size; j++)
        {
            board[i][j] = 0;
        }
    }
}

通过添加一个检查棋盘移动是否合法的函数来稍微改变你的测试，

bool canmove(int mx, int my)
{
    if( (mx>=0) && (mx<size) && (my>=0) && (my<size) ) return true;
    return false;
}

注意 mark() 和 unmark() 是非常重复的，你真的只需要 mark() 棋盘，检查所有合法的移动，然后 unmark() 位置，如果 backtrack() 没有返回 true，

重写函数让一切变得更清晰，

bool horse::backtrack(int x, int y)
{

    if(counter > (size * size))
        return true;

    if(unvisited(board[x][y]))
    {
        mark(board[x][y]);
        if( canmove(x-2,y+1) )
        {
            if(backtrack(x-2, y+1)) return true;
        }
        if( canmove(x-2,y-1) )
        {
            if(backtrack(x-2, y-1)) return true;
        }
        if( canmove(x-1,y+2) )
        {
            if(backtrack(x-1, y+2)) return true;
        }
        if( canmove(x-1,y-2) )
        {
            if(backtrack(x-1, y-2)) return true;
        }
        if( canmove(x+2,y+1) )
        {
            if(backtrack(x+2, y+1)) return true;
        }
        if( canmove(x+2,y-1) )
        {
            if(backtrack(x+2, y-1)) return true;
        }
        if( canmove(x+1,y+2) )
        {
            if(backtrack(x+1, y+2)) return true;
        }
        if( canmove(x+1,y-2) )
        {
            if(backtrack(x+1, y-2)) return true;
        }
        unmark(board[x][y]);
    }
    return false;
}

现在，想想递归必须有多深才能访问每个 [x][y]？很深吧？因此，您可能需要考虑一种更有效的策略。将这两个打印输出添加到板显示应该会显示发生了多少回溯步骤，

int counter = 1; int stepcount=0;
...
void horse::print()
{
    cout<< "counter: "<<counter<<endl;
    cout<< "stepcount: "<<stepcount<<endl;
    ...
bool horse::backtrack(int x, int y)
{
    stepcount++;
    ...

这是 5x5、6x6、7x6 的成本，

./knightstour 5
 >>> Successful! <<< 
counter: 26
stepcount: 253283

./knightstour 6
 >>> Successful! <<< 
counter: 37
stepcount: 126229019

./knightstour 7
 >>> Successful! <<< 
counter: 50
stepcount: 56342

为什么 7 步比 5 步少？想想回溯中移动的顺序——如果你改变顺序，步骤会改变吗？如果您列出了可能的移动 [ {1,2},{-1,2},{1,-2},{-1,-2},{2,1},{2,1} ,{2,1},{2,1} ]，并以不同的顺序处理它们？我们可以更轻松地重新排序动作，

int moves[ ] =
{ -2,+1, -2,-1, -1,+2, -1,-2, +2,+1, +2,-1, +1,+2, +1,-2 };
...
        for(int mdx=0;mdx<8*2;mdx+=2)
        {
        if( canmove(x+moves[mdx],y+moves[mdx+1]) )
        {
            if(backtrack(x+moves[mdx], y+moves[mdx+1])) return true;
        }
        }

将原始移动顺序更改为这个顺序，并运行 7x7 会产生不同的结果，

{ +2,+1, +2,-1, +1,+2, +1,-2, -2,+1, -2,-1, -1,+2, -1,-2 };


./knightstour 7
 >>> Successful! <<< 
counter: 50
stepcount: -556153603 //sheesh, overflow!

但你原来的问题是，

问题是：这个算法的时间复杂度是多少，我该如何优化它？！

回溯算法大约是 8^(n^2)，尽管它可能在 n^2 移动之后找到答案。我会让您将其转换为 O() 复杂度指标。

我认为这会引导你找到答案，而不是告诉你答案。

Answer 4

这是一个新的解决方案：

在这种方法中，使用马在棋盘中的下一次移动时的死锁概率预测，将选择一个移动，它倾向于死锁概率小于其他移动，我们在第一步知道这个死锁概率为零对于每个细胞，它会逐渐改变。棋盘中的马有 2 到 8 步，因此每个单元格都有下一步的预定值。

选择具有较少可用移动的单元格是最佳选择，因为除非它被填充，否则它将在未来趋于死锁。允许的移动次数与进入僵局之间存在反比关系。外部牢房是最高优先级，关于骑士旅行问题，骑士必须穿越一个牢房一次，这些值将在以后的旅行中逐渐改变。然后在下一步中，将选择具有这些条件的单元格

1. 其相邻空单元的数量少于其他单元，或者换句话说被填充的概率更多
2. 选择后，相邻的房子不会死锁

你可以在这里阅读我关于这个问题的完整文章 骑士之旅问题文章

您可以从 GitHub 中的 Full Source找到完整源代码

我希望它会有用