ES

www.codigo-facil.com > Salida mas corta de un laberinto

Salir de un laberinto


Algorimo que busca la salida mas corta de un laberinto.

Introduccion


Cuando cursaba mis estudios de programacion recuerdo que uno de los ejercicios que nos propusieron fue el de formular un algoritmo que fuera capaz de buscar la salida mas corta a un laberinto. Recuerdo que en su momento no llegue a dar con una solucion que resolviera el problema de forma eficiente.

Con el paso del tiempo y gracias a la experiencia acumulada logre  dar con una solucion que resolvia el problema y me dejaba mas o menos satisfecho. Asi que con nostalgia aqui os dejo este algoritmo que tantos quebraderos de cabeza me dio es su momento.

Solucion en PHP


Antes de empezar solo indicar las normas que he seguido para la construccion del laberinto :
  • Solamente analizaremos laberintos en 2D.
  • Todos los laberintos tienen una entrada y una unica salida.
  • Los laberintos son de una unica via.
  • La salida se puede encontrar en cualquiera de los extremos del laberinto.
  • Pueden existir varios caminos que lleven a la salida.
Antes de empezar con el analisis del algoritmo puedes ver el resultado final en este enlace.
  1. <?
  2. /*
  3. Inicializacion de las variables principales
  4. */
  5. $total = 0;
  6. $pasos = array();
  7. $mapaOri = array();

  9. /*
  10. Procedimiento para cargar el laberinto y guardarlo en
  11. una matriz para poder recorrelo
  12. */
  13. $lineas = file('./laberinto.txt');
  14. $i = 0;
  15. while ($tupla = each($lineas))
  16. {
  17.   for ($j=0; $j<strlen($tupla[1]); $j++ )
  18.   {
  19.     if ($tupla[1][$j]=='0' || $tupla[1][$j]=='s' || $tupla[1][$j]=='1')
  20.       $mapaOri[$i][$j] = $tupla[1][$j];
  21.   }
  22.   $i++;
  23. }
  24. /*
  25. Definicion de algunas funciones que van a intervenir en el algoritlmo
  26. principal, esta primera funcion se encargara de buscar posibles
  27. rutas segun la direccion y los posibles obstaculos
  28. */
  29. function alternativas($direccion,$posY,$posX,$pasos)
  30. {
  31. global $mapaOri;
  32. $posib = array();

  34. if ( $direccion!=4 && $posY>0 && !isset($pasos[($posY-1).'-'.$posX]) && $mapaOri[$posY-1][$posX]==0)
  35.   $posib[]=3;

  37. if ( $direccion!=3 && $posY<(count($mapaOri)-1) && !isset($pasos[($posY+1).'-'.$posX]) && $mapaOri[$posY+1][$posX]==0 )
  38.   $posib[]=4;

  40. if ($direccion!=1 && $posX>0 && !isset($pasos[$posY.'-'.($posX-1)]) && $mapaOri[$posY][$posX-1]==0)
  41.   $posib[]=2;

  43. if ( $direccion!=2 && $posX<(count($mapaOri[$posY])-1) && !isset($pasos[$posY.'-'.($posX+1)]) && $mapaOri[$posY][$posX+1]==0 )
  44.   $posib[]=1;

  46.   return $posib;
  47. }

  49. /*
  50. Esta funcion tambien sera invocada por la funcion principal,
  51. al llegar a un final de un camino sin salida por lo que cerrara
  52. dicho camino hasta la siguiente interseccion que encuentre.
  53. Esto evita que el algoritlo evalue de nuevo esta posibilidad
  54. con lo que ahorramos tiempo y recursos al sistema.
  55. */
  56. function cerrarCamino($posY,$posX)
  57. {
  58. global $mapaOri;
  59. $posi = array();

  61. if ($mapaOri[$posY+1][$posX]==0)
  62.   $posi[]=array(0=>($posY+1),1=>$posX);

  64. if ($mapaOri[$posY-1][$posX]==0)
  65.   $posi[]=array(0=>($posY-1),1=>$posX);

  67. if ($mapaOri[$posY][$posX+1]==0)
  68.   $posi[]=array(0=>$posY,1=>($posX+1));

  70. if ($mapaOri[$posY][$posX-1]==0)
  71.   $posi[]=array(0=>$posY,1=>($posX-1));

  73. if (count($posi)==1)
  74.   {
  75.   $mapaOri[$posY][$posX] = 1;
  76.   cerrarCamino($posi[0][0],$posi[0][1]);
  77.   }
  78. }

  80. /*
  81. Funcion principal encargda de buscar las
  82. diferentes salidas y obtener la mas corta
  83. */
  84. function salida($direccion,$posY,$posX,$tot,$pasos)
  85. {
  86.   global $total,$mapaOri;
  87.   if ($tot>=$total && $total!=0)
  88.     return -1;
  89.   else
  90.   if ($mapaOri[$posY][$posX]=='s')
  91.   {
  92.     if ($total==0 || $tot<$total)
  93.       {
  94.       global $pasosF;
  95.       $pasosF = $pasos;
  96.       $total=$tot;
  97.       }
  98.       return $tot;
  99.   }
  100.   else
  101.   {
  102.     $pasos[$posY.'-'.$posX]=2;
  103.     $posib = alternativas($direccion,$posY,$posX,$pasos);
  104.     if (!count($posib))
  105.     {
  106.     cerrarCamino($posY,$posX);
  107.     return -1;
  108.     }
  109.     else
  110.     {
  111.       $caminos = array();
  112.       while ($tupla = each($posib))
  113.       {
  114.         if ($tupla[1]==1)
  115.           $caminos[] = salida($tupla[1],$posY,($posX+1),($tot+1),$pasos);

  117.         if ($tupla[1]==2)
  118.           $caminos[] = salida($tupla[1],$posY,($posX-1),($tot+1),$pasos);

  120.         if ($tupla[1]==3)
  121.           $caminos[] = salida($tupla[1],($posY-1),$posX,($tot+1),$pasos);

  123.         if ($tupla[1]==4)
  124.           $caminos[] = salida($tupla[1],($posY+1),$posX,($tot+1),$pasos);
  125.       }

  127.       $valor=null;
  128.       while ($tupla = each($caminos))
  129.       {
  130.         if (($valor==null  || $tupla[1]<$valor) && ($tupla[1]!=-1))
  131.         $valor = $tupla[1];
  132.       }

  134.       if ($valor==null)
  135.           $valor = -1;

  137.       return $valor;
  138.      
  139.     }
  140.   }
  141. }

  143. /*
  144. Invoco la funcion principal, encargada de buscar la
  145. salida mas corta al laberinto
  146. */
  147. $valor =salida(1,4,0,0,$pasos);
  148. ?>
Analisis del codigo :

El codigo empieza con la  inicilizacion de las variables principales :
  • $total : Esta varible la utilizo para contalibilizar los pasos del camino mas corto hacia la salida.
  • $pasos : Utilizada como registro del recorrido que se va efectuando a lo largo de todos los casos que se van analizando en el algoritmo principal, evitando asi el paso por caminos ya recorridos.
  • $mapaOri : Matriz donde se encuentra la configuracion original del laberinto a analizar.
Una vez que ya tenemos inicializadas las principales variables, seguimos con la carga del laberinto. Para este caso he utilizado un archivo ".txt" externo para guardar el laberinto que vamos a analizar. Esta archivo lo podeis ver en este enlace.

A continuacion defino dos funciones de apoyo a la fucnion principal :
  • function alternativas : Funcion encargada de verificar los posibles movimientos a realizar, segun la direccion y los obstculos que se encuentran al rededor de la posicion analizada. Esta funcion es invocada con los siguientes parametros :

    $direccion : La orientacion del movimiento actual.
    $posY : Posicion en el eje Y
    $posX : Posicion en el eje X
    $pasos : Registro con la trayectoria que ha seguido el movimiento actual, para evitar asi el paso por zonas ya comprobadas.
  • function cerrarCamino : Esta funcion se encarga de desactivar aquellos caminos que lleven a una zona sin salida. Esta pensada para acortar las posibilidades a analizar ahorrando asi recursos al sistema.
Antes de pasar a la funcion principal solo un par de aclaraciones :
  • El eje de cordenadas utilizado se toma como punto de origen la esquina superior izquierda.
  • La direccion viene dada por la siguientes valores :

    1 : Derecha
    2 : Inquierda
    3 : Arriba
    4 : Abajo
A continuacion por fin voy a analizar la funcion principal. Esta funcion se invoca con el paso de los siguientes parametros ( paso por valor ) :
  • $direccion : la orientacion del movimiento inicial
  • $posY : posicion inicial para el eje Y
  • $posX : posicion inicial para el eje X
  • $tot : numero de movimientos, la primera vez logicamente sera 0
  • $pasos : los movimientos que se iran ejecutando, necesario para evitar el paso por zons ya comprobas
Una vez que ya conocemos los parametros intentare explicar la logica que he seguido para la construccion de la funcion.

Esta es una funcion recursiva que finalizara su ejecucion al darse alguno de estos casos :
  • El numero de movimientos supera al minimo de pasos realizado por algun caso anterior que haya encontrado la salida. Devuelvo el valor -1 para que no tome en cuenta este caso.
  • Se haya encontrdo la salida con lo que devuelvo el numero de pasos o movimientos relizados que se han utilizado para llegar a la misma.
  • Se ha llegado a un camino sin salida por lo que devuelvo el valor -1. Ademas si se da este caso invoco la funcion "cerrarCamino" para cerrar este paso para evitar evaluar de nuevo esta opcion en otros cosos que esten pendientes de ejecucion.
En caso de no darse ninguno de las condiciones de finalizacion la funcion continuara su ejecucion, buscando la salida. Destacar que a cada ciclo de ejecucion la funcion comprueba los posibles movimientos que puede realizar con lo que abrira una nueva ejecucion para cadea posibilidad. Segun terminan las ejecuciones se tomaran los valores retornados,

La funcion solo tomara aquellos valores que sean correctos, distintos de -1 y que ademas mejoren el  posible resultado obtenido previamente. Se registraran el numero total de movimientos y los pasos realizados.

Pues hemos llegado al final del articulo, solo recordar que podeis ver el resultado en ejecucion de esta solucion en el siguiente enlace. Espero que os haya resultado de utilidad y si alguien quiere dar su aportacion que no dude a publicarla o hacermelo saber.

Gracias a tod@s por vuestro tiempo nos vemos en futuras publicaciones.

Ultimas noticias

Crea tu propio framework en javascript

Recopilacion de articulos donde mostrare paso a paso como podemos crear nuestro propio framework en javascript, totalmente funcional y listo para ser utilizado en nuestros futuros proyectos.

Para mas informacion :

Tutorial para crear tu propio FrameWork en JavaSript

Más información
13/12/2013 11:42:57

Como crear una DLL en delphi?

En esta serie de 2 capitulos veremos como crear y utilizar una DLL en Delphi.

Abajo os dejo los enlaces a estos 2 capitulos que componen este mini tutorial, espero que sea de vuestro agrado :

Capitulo 1 : Creacion y utilizacion de una DLL

Capitulo 2 : Creacion de un formulario dinamico utilizando una DLL
Más información
19/09/2013 17:35:59

Ya puedes publicar tu opinion

A partir de ahora ya puedes comentar todas las publicaciones que encuentres en el portal.

Podras opinar tanto si algo te gusta como si no, o si crees que es conveniente completar alguna publicacion, ya que la encuentras incompleta o erronea.

O simplemente por si nos quieres felictar por algo bien hecho :-).

Valoraremos cualquier critica que nos puedas hacer.
Más información
20/05/2013 15:30:10

Tutorial PHP5

Fundamentos de la programacion orientada a objetos
Un interesante tutorial repartido en una serie de capitulos donde se tratan los conocimientos basicos de la programacion orientada a objetos (POO) en PHP5.

Para mayor informacion siga el siguiente enlace :

Tutorial POO en PHP

Más información
04/09/2013 15:44:29
Publica tu opinión
1
Proyectos Indie
©2021 www.codigo-facil.com