如何优化Knight的巡演算法？

Question

我使用Backtracking方法在c ++中编写骑士游览算法.但它似乎太慢或陷入无限循环n> 7(大于7乘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 的计算次数至少是 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;and保存area = s * s;在构造函数中，而不是每次都进行计算。

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

算法改进

我可以这么想：

• 对于从对角线的单元格开始的每次游览（例如在示例中从 (0,0) 开始），您只能考虑在对角线创建的两个半棋盘之一上进行第一个移动。
  • 这是因为对称性，或者存在 2 个对称解，或者不存在。
  • 对于这种情况，这给出了 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，这还不错。解决方法是不检查始终，但也许每个 n/8 标记（检查counter % 8 == 4例如或更好counter > 2*n && counter % 8 == 4
• 寻找其他想法来巧妙地尽早中断搜索，但请记住，具有 8 个选项的回溯算法始终具有 O(8^(2^n)) 的本质。

再见