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

Я кодирую Рыцарский тур Алгоритм в 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) выше выглядит так:

введите описание изображения здесь

17

Решение

Поскольку на каждом шаге у вас есть 8 возможностей для проверки, и это нужно сделать для каждой ячейки (за исключением последней), временная сложность этого алгоритма составляет O (8 ^ (n ^ 2-1)) = O (8 ^ ( n ^ 2)) где n — количество квадратов по краям шахматной доски. Чтобы быть точным, это сложность времени наихудшего случая (время, затрачиваемое на изучение всех возможностей, если ничего не найдено или если оно является последним).

Что касается оптимизаций, может быть 2 типа улучшений:

Улучшения реализации

Вы вычисляете 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), как в вашем примере), вы можете рассматривать только первые ходы, находящиеся на одной из двух половин шахматных досок, созданных диагональю.
    • Это из-за симметрии или существует 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. Обходной путь — просто не проверять alwais, но, возможно, каждый n / 8 маркировок (проверка counter % 8 == 4 например или лучше counter > 2*n && counter % 8 == 4
  • найдите другие идеи, чтобы ловко прервать поиск на ранней стадии, но помните, что алгоритм возврата с 8 опциями всегда будет иметь природу O (8 ^ (2 ^ n)).

до свидания

3

Другие решения

Изучите ваш алгоритм. На каждой глубине рекурсии вы изучаете каждый из 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

Вот мои 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..'


2