LABERINTO
Un laberinto es un problema gráfico que consiste en unir la entrada con la salida mediante uno o varios caminos respetando la estructura topológica.
ENTRADA
Lugar donde inicia el recorrido o los recorridos de la solución.
SALIDA
Lugar donde termina el recorrido o los recorridos de la solución.
CORREDOR
Espacio en el que se puede transitar o trazar la solución.
PARED
Línea que divide el laberinto.
MURO
Pared que se encuentra al final de un corredor.
UNIÓN
Punto donde se interceptan líneas.
CERCO
Especio cerrado por paredes inaccesibles.
CORTINA
Pared que se puede rodear
CUARTO
Espacio cerrado al cual se puede acceder por una puerta.
SIMPLIFICACIÓN DE UN LABERINTO
Solucionar un laberinto consiste en buscar todas las soluciones o conexiones entre la entrada y la salida, para seleccionar la más óptima de acuerdo a criterios como tiempo, costo, distancia, seguridad, etc.
A continuación se describe el proceso por medio del cual se simplifica al máximo un laberinto:
Inicialmente se identifica un muro y se desplaza a la entrada del corredor, es decir correr el muro lo más adelante posible a través del corredor así:
La parte comprendida entre el muro inicial y el final se rellena de concreto artificial, convirtiendo este espacio en un cerco por el cual no pasará la solución.
Este proceso continúa:
Los cercos se rellenan de concreto artificial
Las cortinas se adelgazan y generalmente se rodean al ser recorridas en la solución.
Finalmente se puede trazar la solución
Ahora vamos a modelar un laberinto matemáticamente de la siguiente manera:
El supuesto básico que se ha desarrollado para generar el modelo de laberintos consiste en que todo laberinto se puede dividir en pequeños cuartos mediante puertas artificiales de este modo:
Un cuarto que tenga una única puerta es una opción que no se puede tomar porque se puede entrar pero no salir, este cuarto se debe sellar, convirtiéndose en un cerco y rellenar con concreto artificial.
Un cuarto con cero puertas es un cerco, se debe llenar de concreto artificial, es una opción que no se debe tomar.
Cuartos de dos o más puertas permiten pasar de un cuarto a otro. De este modo, el cuarto que tenga a "la entrada" como una de sus puertas se comunicará con otros cuartos y se podrá pasar de un cuarto a otro abriendo y cerrando puertas que comunican cuartos entre sí hasta llegar al cuarto final que contiene en una de sus puertas la "la salida".
Los cuartos que sean sellados se convertirán en cercos rellenados con concreto artificial, esto hará que cualquier otro cuarto que se comunique con el cuarto sellado pierda la puerta que lo comunica con éste último. De este modo habrán nuevos cuarto que tengan solo una puerta y deben ser cerrados, es decir se repite el proceso.
Como resultado final se espera que se hayan cancelado una gran cantidad de cuartos. La solución indicará porqué cuartos podemos transitar y como debemos pasar de uno a otro hasta llegar de la entrada a la salida.
La forma como se dividan los cuartos es independiente de la solución del problema, sin embargo se debe buscar dividir el laberinto en la menor cantidad de cuartos posibles.
Este método permite trabajar incluso con laberintos tridimensionales o multidimensionales.
Se puede proyectar la dirección de las cortinas para hacer una primera división del laberinto en cuartos. Un cuarto es un espacio cerrado que se comunica con otros mediante una puerta.
| Página siguiente |