Resolviendo laberintos utilizando el programa Paint

Dibujo20130318 maze to be solved

Trata de resolver este laberinto (la entrada está en el lateral derecho, en la parte de arriba, y la salida en el lateral inferior, a la derecha). Imagina que copias esta figura en un programa de dibujo (como Paint de Windows). ¿Cómo podrías resolver este laberinto utilizando dicho programa? Piensa un poco, porque es muy fácil. Si al final no logras resolverlo, sigue este enlace para ver la solución. Por supuesto, este método gráfico es muy viejo, fue publicado por E. W. Dijkstra, «A note on two problems in connexion with graphs,» Numerische Mathematik 1: 269-271, 1959 [copias gratis en pdf]. Quien prefiera una explicación for dummies (de donde he sacado este ejemplo) y una implementación en Matlab preferirá leer a Cris Luengo, «Solving mazes using image analysis,» Cris’s Image Analysis Blog, April 17, 2010.

PS: Quien quiera probar que el método funciona, en lugar de usar el laberinto en JPG como aparece en la entrada, debería utilizar la versión en PNG (sigue este enlace) [solución en PNG].



6 Comentarios

  1. Sin hacer trampas, se me ocurre aprovechar la capacidad del programa para manchar áreas delimitadas por frontera de otro color. Derramaría la tinta en el blanco de la entrada, y eso me delimitará la zona que conecta con la salida.

    1. ¡Uy! Ahora que he mirado la solución, parece que se tiñen los muros del laberinto desde la entrada. No sé si mi idea funcionaría igualmente, aunque ahora que lo pienso mejor, igual acabo inundando todo el laberinto, pues puede que existan zonas con puerta de entrada sin otra de salida. Lástima, de repente pensé que era yo uno de esos chicos listos.

      1. Tu estrategia sirve para acotar una solución, por ejemplo, supongamos que las paredes del laberinto son de diferentes colores, pero el suelo es siempre del mismo color, entonces no se puede usar la estrategia del post, pero sí una variante de la tuya.

        La variante es la siguiente: si te encuentras con una bifurcación, estarás en duda de si ir por una bifurcación o por la otra, tapas una de ellas y rellenas la otra, si el relleno llega al destino has tapado bien, sino, deshaz porque es el otro camino.

        Repite el proceso hasta llegar a la salida.

        El proceso «sólo» hay que hacerlo tantas veces como bifurcaciones no triviales tenga la ruta final de salida.

  2. Yo le enseñe a mi hijo Guillermo cuando tenia 3 años con un sistema -no sé si es o no conocido- y se hizo un gran experto: Ibamos coloreando los callejones sin salida hasta llegar a una bifurcacion. Repitiendo hasta que no hayan callejones sin salida, queda todo negro menos el camino correcto.

    Ahora tiene 10, y este fin de semana me construyo uno con arena en la playa de los dificiles, y me reto a resolverlo con solo con la inteligencia artificial en la que trabajo… estoy en ello.

Deja un comentario

Por Francisco R. Villatoro
Publicado el ⌚ 18 marzo, 2013
Categoría(s): ✓ Ciencia • Informática • Recomendación • Science
Etiqueta(s): ,