Как оптимизировать алгоритм тура Найта?

Изучите ваш алгоритм. На каждой глубине рекурсии вы изучаете каждый из 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 () являются очень повторяющимися, вам действительно нужно только пометить () доску, проверить все допустимые ходы, затем снять метку () местоположение, если ни один из методов 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++;
...

Вот затраты на 5х5, 6х6, 7х6,

./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;
}
}

Изменение первоначальной последовательности перемещения на эту, и запуск в течение 7×7 дает другой результат,

{ +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 ().

Я думаю, что это ведет вас к ответу, не говоря вам ответ.

Вот мои 2 цента. Я начал с базового алгоритма возврата. Это ожидало бесконечно n> 7, как вы упомянули. Я реализовал правило предупреждений и он работает как по волшебству и дает результат менее чем за секунду для плат размером до n = 31. Для n> 31 он выдавал ошибку stackoverflow, поскольку глубина рекурсии превысила предел. Я мог бы найти лучшее обсуждение Вот который говорит о проблемах с правилом warnsdorff и возможных дальнейших оптимизациях.

Просто для справки, я предоставляю свою реализацию Python для решения задачи Knight Tour с оптимизацией warnsdorff.

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..'