Laberintos (Parte 11)

(A la parte 10 - A la parte 12)

Un ejemplo

Tomemos a modo de ejemplo el siguiente laberinto, donde E es la entrada, S es la salida y P, Q, R, S y T son los otros nodos del grafo.
Vamos a mostrar un camino entre E y S que respeta las reglas básicas enunciadas en las dos partes previas. Conviene seguir la descripción mirando el dibujo.

Teseo comienza en E y avanza hacia el nodo P. La regla de no retroceso le impide volver a E y Teseo tiene entonces dos ejes para elegir. Elige al azar y, digamos, que va hacia R.

En R, la regla de no retroceso le impide volver a P y otra vez tiene dos ejes para elegir. Digamos que va hacia Q, donde tiene otra vez dos ejes para elegir.

Estamos suponiendo que Teseo sólo puede ver el nodo en el que se encuentra. Si también pudiera ver todos los nodos adyacentes a él, entonces a llegar a Q sabría que éste se conecta con la salida y la regla correspondiente lo obligará a ir en esa dirección. También sabría que el otro eje lo conduce a un nodo ya visitado. Tal como son las suposiciones que estamos haciendo, al estar en Q Teseo no tiene forma de saber que uno de los ejes va a la salida y que el otro va a un nodo ya visitado.

En Q Teseo elige un eje al azar y digamos que vuelve a P. Estando en P, el nodo E junto con el eje que lo conecta con P forma un subgrafo completamente recorrido, por lo que la regla del subgrafo lo obliga a ir a R. En R la regla de no repetición lo fuerza a ir hacia T. Vuelve de T a R, elige al azar y digamos que va otra vez hacia Q. Una vez en Q, la regla de no repetición (y también la regla del subgrafo) lo obliga a ir hacia S, donde termina.

En resumen, el camino fue: E, P, R, Q, P, R, T, R, Q, S.

En cada elección al azar Teseo tenía dos nodos para optar, por lo tanto la probabilidad de elegir este camino en concreto es de 1/32.

Observaciones: 1) La tercera vez que Teseo llega a R es obvio que es inútil volver a P, sin embargo las reglas básicas habrían permitido ese retroceso, se necesitarían reglas más sutiles que lo impidieran.

2) La regla de no repetición impide el ciclo infinito E, P, R, Q, P, R, Q, P, R, Q,... Dado un laberinto cualquiera ¿impiden siempre las reglas básicas la existencia de un ciclo infinito? Mi conjetura es que sí, pero si no fuera ése el caso habría que agregar reglas que lo garantizaran. Otra forma de formular la pregunta es: si Teseo respeta las reglas ¿es forzoso que llegue tarde o temprano a la salida?

(A la parte 10 - A la parte 12)