问题描述
此问题似乎幼稚的，因为我是新手在编程。 ;）
This question might seem naive, because I'm newbie in programming. ;)
I $ C C在 骑士之旅$ 算法的C ++使用的 回溯 方式。但似乎过于缓慢或滞留在无限循环的N> 7（大于7 7棋盘）。
I code the Knight's tour algorithm in c++ using Backtracking method.But it seems too slow or stuck in infinite loop for n > 7 (bigger than 7 by 7 chessboard).
现在的问题是：什么是 时间复杂度 作为这个算法我怎么能优化呢？！
The question is: What is the Time complexity for this algorithm and how can I optimize it?!
骑士旅行问题可以表述如下：
The Knight's Tour problem can be stated as follows:
由于棋盘与n×n的平方，找到该访问每平方恰好一次骑士的路径。
Given a chess board with n × n squares, find a path for the knight that visits every square exactly once.
下面是我的code：
#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）上面是这样的：
output for the example (n = 7) above is like this:
推荐答案
由于在每一步，你有8个可能性，检查和这对每个单元做（除去最后一个），该算法的时间复杂度为O （8 ^（N ^ 2-1））= 0（8 ^（N ^ 2）），其中n是正方形的上方格的边的数目。为了precise这是最坏情况下的时间复杂度（采取探索做好一切准备的时间，如果没有被发现，或者如果它是最后一个）。
Since at each step you have 8 possibilities to check and this has to be done for each cell (minus the last one) the time complexity of this algorithm is O(8^(n^2-1)) = O(8^(n^2)) where n is the number of squares on the edges of the checkboard. To be precise this is the worst case time complexity (time taken to explore all the possibilities if none is found or if it is the last one).
对于优化可以有2种类型的改进：
As for the optimizations there can be 2 types of improvements:
您正在计算的X 2，X 1，X + 1，X + 2和相同的y的至少次的两倍。我可以建议改写这样的事情：
You're calculating x-2, x-1, x+1, x+2 and the same for y at least the double of the times.I can suggest to rewrite things like this:
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]);
}
请注意precalculated值也会在后续块的重用。我发现这是比我especting更有效;这意味着变量赋值和召回不是老毛病又犯了操作速度更快。还请考虑保存 SM1 = S - 1; 和面积= S * S; 在构造函数中，而不是计算每个时间
note the reusing of precalculated values also in subsequent blocks.I've found this to be more effective than what I was especting; meaning that variable assignment and recall is faster than doing the operation again.Also consider saving sm1 = s - 1; and area = s * s; in the constructor instead of calculating each time.
然而，这（被一个实现的改进，而不是算法的改善）将不会改变的时间复杂度顺序，而是仅由某个因数划分时间。我的意思是时间复杂度为O（8 ^（N ^ 2））= K * 8 ^（N ^ 2）差异会在一个较低的K系数。
However this (being an implementation improvement and not an algorithm improvement) will not change the time complexity order but only divide the time by a certain factor.I mean time complexity O(8^(n^2)) = k*8^(n^2) and the difference will be in a lower k factor.
我能想到这样的：
- 在每个巡演开始在一个单元格中的对角线（如开始在（0,0）在你的例子），你可以只考虑第一个动作是由对角线创建的两个半checkboards之一。
- 这是beacouse的simmetry或存在2 simmetric的解决方案或无。
- 这给了O（4 * 8 ^（N ^ 2-2））为案件，但相同的遗体非simmetric的。
- 请注意，再次O（4 * 8 ^（N ^ 2-2））= 0（8 ^（N ^ 2））
- for each tour starting on in a cell in the diagonals (like starting in (0,0) as in your example) you can consider only the first moves being on one of the two half checkboards created by the diagonal.
- This is beacouse of the simmetry or it exists 2 simmetric solutions or none.
- This gives O(4*8^(n^2-2)) for that cases but the same remains for non simmetric ones.
- Note that again O(4*8^(n^2-2)) = O(8^(n^2))
- 例如马不能跳两个大容量的行或列，所以如果你有两个批量标记两侧列（或行）和未标记细胞你确信不会有任何的解决方案。想想看，这可以在O（n）的检查，如果你每十个分量COL /行更新标记细胞的数量。然后，如果你之后的每个检查这标志着你要添加为O（n * 8 ^（N ^ 2））的时间，是不是坏如果n＆LT; = 8。解决方法是根本不检查alwais但也许每一个N / 8标记（检查
柜台％8 == 4，例如或更好的计数器＆GT 2 * N＆功放;＆放大器，计数器％8 == 4
- for example the horse cannot jump two bulk columns or rows so if you have two bulk marked columns (or rows) and unmarked cells on both sides you're sure that there will be no solution. Consider that this can be checked in O(n) if you mantain number of marked cells per col/row updated. Then if you check this after each marking you're adding O(n*8^(n^2)) time that is not bad if n < = 8. Workaround is simply not to check alwais but maybe every n/8 markings (checking
counter % 8 == 4for example or bettercounter > 2*n && counter % 8 == 4
再见
这篇关于如何优化骑士之旅算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！