c++ - preorden - ¿Cómo optimizar el algoritmo de recorrido de Knight?

eliminar nodo arbol binario en c

Question

Codifico el algoritmo de recorrido de Knight en c ++ utilizando el método de Backtracking . Pero parece demasiado lento o atascado en un bucle infinito para n> 7 (más grande que 7 por 7 tablero de ajedrez).

La pregunta es: ¿Cuál es la complejidad del tiempo para este algoritmo y cómo puedo optimizarlo?

El problema de Knight''s Tour se puede expresar de la siguiente manera:

Dado un tablero de ajedrez con n × n casillas, encuentra una ruta para el caballero que visita cada casilla exactamente una vez.

Aquí está mi código:

#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;

}

La salida para el ejemplo (n = 7) anterior es así:

Answer 1

Aquí están mis 2 centavos. Comencé con el algoritmo básico de backtracking. Estaba esperando indefinidamente por n> 7 como mencionaste. Implementé la regla warnsdorff y funciona como una magia y da un resultado en menos de un segundo para tablas de tamaños hasta n = 31. Para n> 31, estaba dando un error de flujo de apilamiento cuando la profundidad de la recursión excedía el límite. Podría encontrar una mejor discusión here que habla sobre problemas con la regla warnsdorff y posibles optimizaciones adicionales.

Solo para la referencia, estoy proporcionando mi implementación en Python del problema Knight''s Tour con la optimización 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..''

Answer 2

Como en cada paso tiene 8 posibilidades para verificar y esto debe hacerse para cada celda (menos la última), la complejidad temporal de este algoritmo es O (8 ^ (n ^ 2-1)) = O (8 ^ ( n ^ 2)) donde n es el número de cuadrados en los bordes del tablero de control. Para ser precisos, esta es la complejidad del peor de los casos (tiempo que se tarda en explorar todas las posibilidades si no se encuentra ninguna o si es la última).

En cuanto a las optimizaciones puede haber 2 tipos de mejoras:

Mejoras en la implementación

Estás calculando x-2, x-1, x + 1, x + 2 y lo mismo para y al menos el doble de los tiempos. Puedo sugerir reescribir cosas como esta:

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]);
}

note la reutilización de valores precalculados también en bloques subsiguientes. He encontrado que esto es más efectivo de lo que esperaba; lo que significa que la asignación y recuperación de variables es más rápida que volver a realizar la operación. También considere guardar sm1 = s - 1; y area = s * s; En el constructor en lugar de calcular cada vez.

Sin embargo, esto (siendo una mejora de implementación y no una mejora de algoritmo) no cambiará el orden de complejidad del tiempo, sino que solo dividirá el tiempo por un factor determinado. Me refiero a la complejidad del tiempo O (8 ^ (n ^ 2)) = k * 8 ^ (n ^ 2) y la diferencia estará en un factor k más bajo.

Mejoras de algoritmo

Puedo pensar esto:

• para cada recorrido que comienza en una celda en las diagonales (como comenzar en (0,0) como en su ejemplo), puede considerar solo los primeros movimientos que se realizan en una de las dos mitad de los tablones de control creados por la diagonal.
  • Esto se debe a la simetría o existen 2 soluciones simétricas o ninguna.
  • Esto da O (4 * 8 ^ (n ^ 2-2)) para esos casos, pero lo mismo permanece para los no simétricos.
  • Note que nuevamente O (4 * 8 ^ (n ^ 2-2)) = O (8 ^ (n ^ 2))
• intente interrumpir la carrera antes si alguna condición global sugiere que una solución es imposible dadas las marcas actuales.
  • por ejemplo, el caballo no puede saltar dos columnas o filas en masa, por lo que si tiene dos columnas (o filas) marcadas en masa y celdas sin marcar en ambos lados, está seguro de que no habrá solución. Tenga en cuenta que esto puede comprobarse en O (n) si mantiene actualizado el número de celdas marcadas por col / fila. Luego, si marca esto después de cada marca, está agregando O (n * 8 ^ (n ^ 2)) tiempo que no es malo si n <= 8. La solución es simplemente no verificar siempre, pero quizás cada marca de n / 8 ( comprobando el counter % 8 == 4 por ejemplo o mejor counter > 2*n && counter % 8 == 4
• encuentre otras ideas para interrumpir inteligentemente la búsqueda temprano, pero recuerde que el algoritmo de retroceso con 8 opciones siempre tendrá su naturaleza de ser O (8 ^ (2 ^ n)).

Adiós

Answer 3

Examina tu algoritmo. En cada profundidad de recursión, examina cada uno de los 8 movimientos posibles, verificando cuáles están en el tablero y luego procesa esa posición recursivamente. ¿Qué fórmula matemática describe mejor esta expansión?

Tiene un tamaño de placa fijo, int [8] [8], tal vez debería hacerlo dinámico,

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

Cambiando un poco sus pruebas agregando una función para verificar que un movimiento de la junta es legal,

bool canmove(int mx, int my)
{
    if( (mx>=0) && (mx<size) && (my>=0) && (my<size) ) return true;
    return false;
}

Tenga en cuenta que las marcas () y desmarcar () son muy repetitivas, realmente solo necesita marcar () el tablero, verificar todos los movimientos legales, luego desmarcar () la ubicación si ninguno de los pasos atrás () devuelve verdadero,

Y reescribir la función hace que todo sea un poco más claro,

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

Ahora, piense qué tan profunda debe ser la recursión para visitar cada [x] [y]? Bastante profundo, ¿eh? Por lo tanto, es posible que desee pensar en una estrategia que sea más eficiente. Agregar estas dos impresiones a la pantalla del tablero debe mostrarle cuántos pasos de retroceso se produjeron,

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++;
    ...

Aquí están los costos de 5x5, 6x6, 7x6,

./knightstour 5
 >>> Successful! <<< 
counter: 26
stepcount: 253283

./knightstour 6
 >>> Successful! <<< 
counter: 37
stepcount: 126229019

./knightstour 7
 >>> Successful! <<< 
counter: 50
stepcount: 56342

¿Por qué tomó menos pasos para 7 que para 5? Piense en el orden de los movimientos en la pista de retroceso: si cambia el orden, ¿cambiarían los pasos? ¿Qué pasa si hiciste una lista de los movimientos posibles [{1,2}, {- 1,2}, {1, -2}, {- 1, -2}, {2,1}, {2,1} , {2,1}, {2,1}], y los procesó en un orden diferente? Podemos hacer que reordenar los movimientos sea más fácil,

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

Cambiando la secuencia de movimiento original a esta, y ejecutando para 7x7 da un resultado diferente,

{ +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!

Pero tu pregunta original era,

La pregunta es: ¿Cuál es la complejidad del tiempo para este algoritmo y cómo puedo optimizarlo?

El algoritmo de retroceso es aproximadamente 8 ^ (n ^ 2), aunque puede encontrar la respuesta después de tan solo n ^ 2 movimientos. Te dejaré convertir eso a O () métrica de complejidad.

Creo que esto te guía a la respuesta, sin decirte la respuesta.