Descargar

Modelo de Laberintos


Partes: 1, 2

  1. Definiciones
  2. Simplificación de un laberinto

DEFINICIONES

edu.red

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

edu.red

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í:

edu.red

edu.red

edu.red

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.

edu.red

Este proceso continúa:

edu.red

edu.red

edu.red

edu.red

edu.red

edu.red

edu.red

edu.red

edu.red

Los cercos se rellenan de concreto artificial

edu.red

edu.red

Las cortinas se adelgazan y generalmente se rodean al ser recorridas en la solución.

edu.red

Finalmente se puede trazar la solución

edu.red

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.

Partes: 1, 2
Página siguiente