如何优化 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) 的输出如下所示：

原文由 Kasra 发布，翻译遵循 CC BY-SA 4.0 许可协议

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; 和 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)) 的性质。

再见

原文由 Diego Mazzaro 发布，翻译遵循 CC BY-SA 3.0 许可协议