24.2.07

Laberintos (Parte 3)

(A la parte 2 - A la parte 4)

Teseo en el laberinto

El laberinto es un edificio cerrado y oscuro. Una persona, digamos que se llama Teseo, lo recorre buscando desesperadamente la salida. Por toda iluminación Teseo lleva una vela que apenas alumbra algunos centímetros alrededor por lo que sólo sabrá que ha llegado a la salida exactamente cuando llegue a ella (no podrá verla desde lejos) y sólo sabrá que ha llegado a un callejón sin salida cuando se encuentre cara a cara con la pared que lo cierra. Teseo lleva también un papel en el que va registrando lo que ha recorrido hasta el momento y además una tiza con la que puede hacer marcas y así reconocer si ya ha pasado por el punto del laberinto en el que se encuentre. Intentamos medir objetivamente la dificultad que tendrá Teseo en hallar la salida del laberinto.

Decíamos antes que todo laberinto estará representado por un grafo. Muchas veces evitaremos intermediaciones innecesarias y diremos simplemente que el laberinto es el grafo que lo representa. Teseo está en realidad dibujando un camino en el grafo (suponemos que no se vuelve atrás en medio de un eje, es decir, cuando comienza a sale de un nodo no cambia de dirección antes de llegar al nodo siguiente). Hallar la salida del laberinto equivale a encontrar un camino que conecte la entrada con la salida.

(A la parte 2 - A la parte 4)

1 comentario:

Djalmago dijo...

A mi la ideal inicial al ver cual era el problema era un tipo más singular de grafo, que es el árbol.

Ya que usted ha definido el grafo, deduzco que habrá gente que no conozca estos términos, así que definiré brevemente el árbol.

Un árbol es un grafo pero que tiene unas restricciones especiales y podemos representar como un árbol con ramas invertido.
En un árbol, hay un nodo "inicial" (por decirlo de alguna manera) llamado raíz, del que salen varios nodos llamados hijos, siendo el raiz el padre de estos. A su vez, estos hijos tendrán otros hijos (o no), y así se va formando un árbol. Así, el árbol crece hacia abajo y no habrá conexiones o caminos más que del tipo padre-hijo. Los nodos que no tengan hijos, se llamarán nodos hoja.
(Espero haberme explicado bien, pero reconozco que no es lo mío el explicar cosas. Para los que no les quedó claro, tenemos la wikipedia: http://es.wikipedia.org/wiki/Árbol_(teoría_de_grafos) )

Así, mi idea para medir la dificultad de un laberinto sería la elaboracíon de un árbol. La salida, lógicamente, sería el nodo raíz. Mientras no haya más que un camino posible, el árbol no crecería. En el momento de llegar a una bifurcación, se crearáin tantos hijos como caminos posibles. Y así se iría elaborando el árbol.

Por supuesto, soy consciente de la limitación de que no haya posibilidad de lazos o bucles, pero supongo que se podría resolver estableciendo distintos tipos de nodos. Ya lo pensaré otro día que no son horas :P

Un saludo e interesante página.