Modelo de laberintos
Páginas: 8 (1860 palabras)
Publicado: 20 de enero de 2011
MODELO DE LABERINTOS
DEFINICIONES
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 puedetransitar 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 enbuscar 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 atravé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ónAhora 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 debesellar, 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 otroabriendo 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 quetengan 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 buscardividir 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.
Con este modelo un laberinto queda totalmentedescrito mediante una tabla que indica los cuartos activos y cómo cada uno de ellos se comunica con otros. Esta tabla sufre modificaciones, es decir simplificaciones que consisten en anular los cuartos que no tienen puertas o que tienen una, a su vez, esto representa en el laberinto la clausura de un cuarto. El mejor método para simplificar un laberinto es trabajar la tabla de cuartos activos, esto...
DEFINICIONES
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 puedetransitar 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 enbuscar 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 atravé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ónAhora 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 debesellar, 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 otroabriendo 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 quetengan 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 buscardividir 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.
Con este modelo un laberinto queda totalmentedescrito mediante una tabla que indica los cuartos activos y cómo cada uno de ellos se comunica con otros. Esta tabla sufre modificaciones, es decir simplificaciones que consisten en anular los cuartos que no tienen puertas o que tienen una, a su vez, esto representa en el laberinto la clausura de un cuarto. El mejor método para simplificar un laberinto es trabajar la tabla de cuartos activos, esto...
Leer documento completo
Regístrate para leer el documento completo.