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

Question

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

问题是: Time complexity 是什么？ 对于这个算法，我该如何优化它？!

---

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

Given a chess board with n × n squares, find a path for the knight that visits every square exactly once.

这是我的代码:

#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]);
}

注意在后续 block 中也重复使用预先计算的值。我发现这比我所期待的更有效；这意味着变量分配和调用比再次执行操作更快。还要考虑在构造函数中保存sm1 = s - 1;和area = 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)) 的性质。

再见