Laberintos (Parte 4)

(A la parte 3 - A la parte 5)

Laberintos físicos y laberintos virtuales

Existen laberintos físicos, pero también existen laberintos virtuales que recorremos con más frecuencia de la que creemos. Por ejemplo, la resolución de muchos problemas de ingenio equivale a recorrer un grafo. Pensemos en un solitario de fichas, es decir un tipo de problema de ingenio en el que se pide llevar fichas desde cierta configuración inicial hasta otra configuración final siguiendo en el proceso determinadas reglas específicas (véase aquí un ejemplo). Resolver un problema de esta clase equivale a recorrer un grafo o un laberinto, en este grafo cada nodo representa una configuración posible de las fichas, la entrada es la configuración inicial, la salida es la configuración final buscada y dos nodos están conectados si y sólo si es posible pasar de la configuración representada por uno de ellos a la configuración del otro en un único movimiento (1).

Otro ejemplo estaría dado por el tan popular Sudoku. Resolver uno de estos problemas equivale a recorrer un grafo en el que la entrada es el enunciado del problema y la salida es la solución buscada. Por lo tanto nuestra teoría para medir la dificultad de un laberinto permitirá al mismo tiempo medir la dificultad de un problema, al menos, la dificultad de ciertos problemas de ingenio.

Una observación sobre laberintos físicos: Observemos el siguiente grafo e imaginemos que representa un laberinto físico (recuérdese que el nodo rojo es la entrada y el verde es la salida):
Algunos ejes se cortan en puntos que no son nodos, por lo tanto en esos puntos Teseo no puede cambiar de dirección. Para entender físicamente esos cruces debemos imaginar que en esos puntos que no son nodos los caminos no se cortan realmente, sino que uno pasa por encima del otro:
Nota:

(1) Debo hacer aquí dos aclaraciones importantes. Muchas veces los problemas de movimientos de fichas piden hallar el camino más corto que vaya de la configuración inicial a la final. La teoría que expondremos permitirá medir la dificultad de hallar algún camino, pero no la dificultad de hallar el más corto. Por otra parte, en alguno de estos problemas puede suceder que el hecho de que sea posible pasar de la configuración A a la B, pero no de la B a la A. En ese caso, el problema quedaría representado por un grafo dirigido, es decir un grafo en el que los ejes tienen un sentido permitido de tránsito. Nuestra teoría de medición de dificultad será enunciada para grafos no dirigidos, pero podría extenderse sin dificultad a grafos dirigidos.

A la parte 3 - A la parte 5)