miércoles, 5 de enero de 2011

Deitel_C++_4.25(Recorrido del Caballo, Método de Fuerza Bruta)

_____________________________________________________________________________________
4.25 (Paseo del Caballo: Métodos de Fuerza Bruta) En la parte c del ejercicio 4.24 desarrollamos una solución al problema del paseo del caballo. El método utilizado, llamado "heurística de accesibilidad", genera muchas soluciones y se ejecuta con eficiencia. A medida que se incremente de manera continua la potencia de las computadoras, seremos capaces de resolver más problemas con menos potencia y algoritmos relativamente menos sofisticados. A éste le podemos llamar el método de la "fuerza bruta" para resolver problemas.

a) Utilice la generación de números aleatorios para permitir que el caballo se desplace a lo largo del tablero (mediante sus movimientos legítimos en L) en forma aleatoria. Su aplicación debe ejecutar un paseo e imprimir el tablero final. ¿Qué tan lejos llegó el caballo?
_____________________________________________________________________________________
SOLUCIÓN:
Un Circuito del Caballo
Este problema es clásico. En los comentarios aparece el algoritmo, que es bastante sencillo y, por lo mismo, fácil de seguir. La principal característica de la fuerza bruta es que los algoritmos son directos y muy fáciles. Si un algoritmo por fuerza bruta es difícil de entener, tal vez no estamos haciendo lo mejor. Debo decir que es muy gratificante cuando aparece el primer circuito completo (de 64 casillas), o al menos lo fue para mi cuando, hace mucho tiempo y mediante algoritmos más complicados, pude resolverlo. A este programa le adapté un ciclo que pregunta al usuario cuántas casillas quiere que el caballo recorra por lo menos, esto para no tener que ejecutar el programa cada vez. El tiempo de ejecución se va incrementando bastante con el numero de casillas ( supongo que de manera exponencial, pero no estoy seguro) aunque en el peor de los casos, y con una máquina no muy buena, deberían obtener un ciclo completo en unos 10 minutos cuando más. Si ustedes comparan los circuitos completos con los que ocurren cuando ejecuta el programa Recorrido del Caballo, Enfoque Heurístico se darán cuenta de que son muy parecidos, es decir que el caballo debe ir por los bordes primero y, principalmente, ir a las esquinas en cuanto pueda, para quedar en el centro al final. Este programa inicia con el caballo en una esquina, la superior izquierda del tablero, o a8 para los que juegan ajedrez, pero esto no representa ninguna limitacion y se puede poner el caballo en la casilla que se quiera. También pueden adaptar el programa, con sólo cambiar la variable TAMANO, indicada en el código, para resolver el circuito del caballo en un tablero de N*N. Tiempo despues de hacer este programa un amigo me comentó que es posible analizar este problema mediante caminos entre puntos con teoria de grafos (de hecho se trata del circuito de Hamilton). Sería interesante un algoritmo basado en ese enfoque, pero yo no lo conozco.


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  *                                                                        *
  *                                                                        *
  *           CIRCUITO DEL CABALLO (FUERZA BRUTA)                          *
  *                                                                        *
  *  Este programa intenta el recorrido del caballo en un tablero de       *
  *  ajedrez mediante la fuerza bruta.                                     *
  *                                                                        *
  *                                                                        *
  *++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

  /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   *                                                                       *
   *                               ALGORITMO:                              * 
   *                               __________                              *
   *                                                                       * 
   *  La idea de este algorimo es bastante simple:                         *
   *                                                                       *
   * PASO 1: El tablero de ajedrez (arreglo de 8x8) se llena con 0 en todas*
   * las entradas exepto en la esquina superior derecha, que se coloca un 1*
   * De ahi es de donde parte el caballo.                                  *
   *                                                                       *  
   * PASO 2: Se lanza un par de "dados" de ocho caras El primer dado decide*
   * el renglon, el siguiente decide la columna donde se colocara el       *
   * caballo a continuacion.                                               *
   *                                                                       *
   *PASO 3: Es necesario verificar que el caballo no haya pasado antes por *
   *ahi, o que la casilla seleccionada tenga un 0 Si no es asi se repite el*
   *Paso2. Si efectivamente es un 0, entonces se verifica que la casilla   *
   *elegida al azar sea "legal" o este en forma de L Para esto se verifican*
   *las distancias en X y en Y. Si el valor absoluto de la diferencia entre*
   *la casilla elegida por el dado1 y la casilla x actual es igual a 2 o  1*
   *se procede a checar el valor absoluto de la distancia entre dado2 y Y. *
   *1 para el primer caso y 2 para el segundo, indican que la casilla es   *
   *valida. Se procede a poner el numero  2 ( o 3 o 4 o el que sea)  en la *
   *casilla, lo cual indica que esa es la siguiente parada del caballo. Se *
   *incrementa la variable contador y se procede de esa manera.            * 
   *                                                                       * 
   *                                                                       *  
   *Eso es todo. Esa es la idea central. Lo demas consiste en decirle al   *
   *programa cuando ya no es posible encontrar mas casillas, y por lo      * 
   *tanto se ha llegado a un rincon sin salida. Para eso se introduce una  *
   *variable que cuenta el numero de veces que se ha lanzado los dos dados *
   *sin cambiar de casilla.  Si se cumplen estos el programa entiende que  *
   *no hay salida y deja de intentar buscarla. Esto significa que 15 de    *
   *cada 1000 veces dejara de intentar cuando en realidad hay una casilla  *
   *a la cual mover. Se puede cambiar y poner un limite mas grande, pero   *
   *como he puesto un ciclo mas grande afuera que permite al usuario pedir *
   *una cuota minima de recorrido, hacerlo significa mas tiempo.           *
   *                                                                       *
   *                                                                       *
   *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

 #include <iostream>
 using namespace::std;
 #include <ctime>
 #include <cmath>
 #include <cstdlib>
 
 int x = 1; // El caballo inica en la casilla superior
 int y = 1; // izquierda
 const int TAMANO = 8; // Cambiar esta variable para resolver el problema del
                 // recorrido del caballo en un tablero de N * N
 int contador = 1; // Esta variable lleva la cuenta de las casillas 
                   // recorridas 
 int ciclos = 0; // Esta variable cuenta los ciclos que se intentan
                 // antes de terminar que ya no haya lugares a los cuales
                 // ir
 int intentos_fallidos = 0; // Esta variable cuenta cuantos ciclos se 
 // intentan antes de obtener el que pidio el usuario.

 // Prototipo de funcion Imprime
 void Imprime( int a[][TAMANO + 1]);
 int main()
 {    // Abre main
 srand(time(NULL));
 int Arreglo[TAMANO + 1][TAMANO + 1] = { {0, 0}, {0, 0} };
 Arreglo[y][x] = 1;     
 int dado1;
 int dado2;
 int casillas_requeridas = 0;

 do
 {   // Abre while 
 cout <<"\nCuantas casillas quiere que recorra por lo menos?";
 cout <<"\n(Un numero positivo menor que " << TAMANO*TAMANO <<" )" <<endl;
 cin >> casillas_requeridas;
 }  while ((TAMANO*TAMANO < casillas_requeridas) || (0 > casillas_requeridas));

 while ( contador < casillas_requeridas )
 {    // Abre while
 intentos_fallidos++; // Se incrementa cada que inica un intento de
                      // completar las casillas pedidas por el usuario
 contador = 1; // Dado que ya se ha colocado al caballo en (y,X), se
               // inicia el contador en 1 
 int ciclos = 0; // Se inicia con 0 ciclos o lanzamientos de dados infructuosos
 // Cada vez que se aborta un intento han de limpiarse las casillas, con 
 // el siguiente par de ciclos se establecen a 0 nuevamente.

 for ( int s = 0; s <= TAMANO; s++ )
 {        // Abre for
 for ( int t = 0; t <= TAMANO; t++ )
 Arreglo[s][t] = 0;
 }        // Cierra for 

 // Se ha de colocar el caballo en la esquina superior izquierda cada vez
 // Desde luego se puede poner en cualquier parte
 x = 1;
 y = 1;
 Arreglo[y][x] = 1;

 // Mientras no se encuentre un lugar para el caballo
 while ( 1000 != ciclos )
 // Por que 100? En el caso extremo en el que solo falte una casilla por 
 // llenar (la 64 para un tablero de 8*8) la mayoria de las casillas aleatorias
 // estaran ya ocupadas, pero a la larga, una de cada 64 (TAMANO*TAMANO) sera
 // la correcta. Para evitar que el intento se aborte debido a una fluctuacion
 // estadistica (por ejemplo que de 500 casillas aleatorias ninguna sea la 
 // casilla en blanco) se pone un "colchon" de 1000 casillas. Esto se puede 
 // cambiar, desde luego, teniendo en cuenta cual es la probabilidad de que se
 // obtenga una casilla cualquiera.

 {        // Abre while
 ciclos++;
 dado1 = 1 +  rand() % TAMANO;
 dado2 = 1 +  rand() % TAMANO;
 
 if ( 2 == std::abs(x - dado1))  
 {       // Abre if
 if ( 1 == std::abs(y - dado2))
 if ( 0 == Arreglo[dado1][dado2] )
 {     // Abre if
 Arreglo[dado1][dado2] = ++contador;
 x = dado1;
 y = dado2;
 ciclos = 0;
 }     // Cierra if 
 }       // Cierra if

 if ( std::abs(std::abs(x) - std::abs(dado1)) == 1) 
 {  // abre if
 if ( std::abs(std::abs(y) - std::abs(dado2)) == 2  )
 if ( 0 == Arreglo[dado1][dado2] )
 {    // Abre if 
 Arreglo[dado1][dado2] = ++contador; 
 x = dado1;
 y = dado2;
 ciclos = 0;
 }  // Cierra if
 }  // Cierra if

 }       // Cierra while
 }    // Cierra while
 
 cout<<"\nLISTO!"<<endl;
 cout<<"\nSe recorrieron " << contador << " casillas.\n";
 cout<<"\nSe intentaron "<<intentos_fallidos<<" circuitos antes de obtener";
 cout<<" el requerido.\n";
 Imprime( Arreglo);


 }    // Cierra main


/*La funcion siguiente despliega el tablero de ajedrez */

 //////////////////////////////////////////
 // Imprime
 ///////////////////////////////////////////
 
void Imprime( int Matriz[][TAMANO + 1])

{ // Abre la funcion Imprimir

cout << endl << endl<< "Este es el tablero: " << endl << endl;
for ( int i = 1; i <= TAMANO; i++ )
{ // Abre for
for ( int j = 1; j <= TAMANO; j++)
{ // abre for anidado
cout << Matriz[i][j] <<" \t";
} // Cierra for anidado
cout << endl <<endl << endl;
} // Cierra for
cout << endl << endl;
} // Cierra la funcion Imprimir

No hay comentarios:

Publicar un comentario

Related Posts Plugin for WordPress, Blogger...