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

Ответ 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), как в вашем примере), вы можете рассматривать только первые ходы, находящиеся на одной из двух половинных карт, созданных по диагонали.
  • Это символ симметрии или существует 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)).

Bye

Ответ 2

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

Обратите внимание, что метки() и 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++;
    ...

Вот стоимость для 5x5, 6x6, 7x6,

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

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

{ +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), хотя он может найти ответ после всего лишь п ^ 2. Я позволю вам преобразовать это в метрику сложности O().

Я думаю, это поможет вам ответить, не сказав вам ответа.

Ответ 3

Вот мои 2 цента. Я начал с базового алгоритма обратного отслеживания. Он ожидал бесконечно для n > 7, как вы упомянули. Я внедрил правило warnsdorff и работает как магия и дает результат менее чем за секунду для досок размером до 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..'

Ответ 4

    internal static IList < Cell > GetPossibleSteps(int row, int col, int size, int[, ] board) {
     // 1st Quadrent cells
     Cell cell_1 = new Cell() {
      Row = row + 2, Col = col + 1
     };
     Cell cell_2 = new Cell() {
      Row = row + 1, Col = col + 2
     };
     // 2nd Quadrent cells
     Cell cell_3 = new Cell() {
      Row = row - 2, Col = col + 1
     };
     Cell cell_4 = new Cell() {
      Row = row - 1, Col = col + 2
     };
     // 3rd Quadrent cells
     Cell cell_5 = new Cell() {
      Row = row - 2, Col = col - 1
     };
     Cell cell_6 = new Cell() {
      Row = row - 1, Col = col - 2
     };
     // 4th Quadrent cells
     Cell cell_7 = new Cell() {
      Row = row + 2, Col = col - 1
     };
     Cell cell_8 = new Cell() {
      Row = row + 1, Col = col - 2
     };

     // After filtering -Ve and exceeding waal values
     IList < Cell > cells = new List < Cell > ();
     if ((cell_1.Row >= 0 && cell_1.Row <= size) && (cell_1.Col >= 0 && cell_1.Col <= size) && board[cell_1.Row, cell_1.Col] == 0)
      cells.Add(cell_1);
     if ((cell_2.Row >= 0 && cell_2.Row <= size) && (cell_2.Col >= 0 && cell_2.Col <= size) && board[cell_2.Row, cell_2.Col] == 0)
      cells.Add(cell_2);
     if ((cell_3.Row >= 0 && cell_3.Row <= size) && (cell_3.Col >= 0 && cell_3.Col <= size) && board[cell_3.Row, cell_3.Col] == 0)
      cells.Add(cell_3);
     if ((cell_4.Row >= 0 && cell_4.Row <= size) && (cell_4.Col >= 0 && cell_4.Col <= size) && board[cell_4.Row, cell_4.Col] == 0)
      cells.Add(cell_4);
     if ((cell_5.Row >= 0 && cell_5.Row <= size) && (cell_5.Col >= 0 && cell_5.Col <= size) && board[cell_5.Row, cell_5.Col] == 0)
      cells.Add(cell_5);
     if ((cell_6.Row >= 0 && cell_6.Row <= size) && (cell_6.Col >= 0 && cell_6.Col <= size) && board[cell_6.Row, cell_6.Col] == 0)
      cells.Add(cell_6);
     if ((cell_7.Row >= 0 && cell_7.Row <= size) && (cell_7.Col >= 0 && cell_7.Col <= size) && board[cell_7.Row, cell_7.Col] == 0)
      cells.Add(cell_7);
     if ((cell_8.Row >= 0 && cell_8.Row <= size) && (cell_8.Col >= 0 && cell_8.Col <= size) && board[cell_8.Row, cell_8.Col] == 0)
      cells.Add(cell_8);
     return cells;
    }
    internal static bool PlaceNight(int[, ] board, int r, int c, int markedPlace, int size) {
     Counter++;
     if (markedPlace >= size * size) {
      Console.WriteLine("Total steps = {0}", Counter);
      return true;
     }
     IList < Cell > cells = GetPossibleSteps(r, c, size - 1, board);
     List < KeyValuePair < int, Cell >> stepsCount = new List < KeyValuePair < int, Cell >> ();
     foreach(Cell item in cells) {
      stepsCount.Add(new KeyValuePair < int, Cell > (GetPossibleSteps(item.Row, item.Col, size - 1, board).Count, item));
     }
     foreach(Cell item in stepsCount.OrderBy(d => d.Key).Select(data => data.Value).ToList()) {
      // Mark if unoccupied
      if (board[item.Row, item.Col] == 0) {
       board[item.Row, item.Col] = ++markedPlace;
       if (PlaceNight(board, item.Row, item.Col, markedPlace, size))
        return true;
       else {
        board[item.Row, item.Col] = 0;
        --markedPlace;
       }
      }
     }
     return false;[See the link below for out put of 10 X 10 board][1]
    }