Con este modelo un laberinto queda totalmente descrito 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 evita realizar gráficos en cada simplificación.
En el ejemplo siguiente se trabajará la simplificación de la tabla de cuartos activos acompañada de una gráfica para verificar la efectividad del modelo.
Los cuartos de deben nombrar con números.
Problema inicial:
Se proyectan las cortinas para formar los cuartos y se los numera:
Se numera cada cuarto en el orden en que se quiera, pero el cuarto de la entrada tomará el número 1 y el de la salida el mayor número que se use para los cuartos. El exterior se lo puede denotar con el número cero para la entrada y con el número más alto para la salida.
Este laberinto se lo puede trabajar con la siguiente tabla:
TABLA DE CUARTOS ACTIVOS
Cuarto | Comunicación | Cantidad de Puertas | Peso Distancia mts | ||
1 | 0 – 2 | 2 | 17 | ||
2 | 1 – 5 | 2 | 14 | ||
3 | 6 | 1 | 10 | ||
4 | – | 0 | 10 | ||
5 | 2 – 6 | 2 | 8 | ||
6 | 3 – 5 – 8 | 3 | 8 | ||
7 | 10 | 1 | 20 | ||
8 | 9 – 6 | 2 | 14 | ||
9 | 8 – 10 | 2 | 14 | ||
10 | 7 – 9 – 11 | 3 | 17 | ||
En la columna "cuarto" se escribe el número del cuarto.
En la columna "Comunicación" se escribe los números de los cuartos con los que el cuarto analizado se comunica.
En la columna puertas se coloca el número de cuartos con los que el cuarto analizado se comunica, esto es equivalente al número de puertas. En la gráfica las puertas están coloreadas de rojo.
En la columna peso, se relaciona ya sea el área del cuarto, la distancia (largo), el tiempo, el costo, la seguridad (un número) que existe al transitar por esa zona, etc. Esta información es útil en el caso de tener que escoger entre varias opciones de solución, ya que así se puede escoger la solución más rápida, más corta, más segura, más barata, etc. Sumando los puntos de esta casilla para cada solución.
Los cuartos que se deben clausurar, sellar o cancelar son los que tienen solo una puerta o ninguna. Esto implica en la tabla borrar las filas que contengan estos cuadros y luego en la columna comunicación borrar los números de los cuartos sellados y en la columna puertas modificar el número de puertas actualizando la información. En la gráfica esto implica rellenar de concreto artificial los cuartos sellados:
Cuarto | Comunicación | Puertas | Peso Distancia mts | ||
1 | 0 – 2 | 2 | 17 | ||
2 | 1 – 5 | 2 | 14 | ||
5 | 2 – 6 | 2 | 8 | ||
6 | 3 – 5 – 8 | 3 | 8 | ||
8 | 9 – 6 | 2 | 14 | ||
9 | 8 – 10 | 2 | 14 | ||
10 | 7 – 9 – 11 | 3 | 17 | ||
Cuarto | Comunicación | Puertas | Peso Distancia mts | ||
1 | 0 – 2 | 2 | 17 | ||
2 | 1 – 5 | 2 | 14 | ||
5 | 2 – 6 | 2 | 8 | ||
6 | 5 – 8 | 2 | 8 | ||
8 | 9 – 6 | 2 | 14 | ||
9 | 8 – 10 | 2 | 14 | ||
10 | 9 – 11 | 2 | 17 | ||
En la última tabla vemos que todos los cuartos tienen dos puertas, esto significa que ya no se puede simplificar más el problema.
El problema se sigue simplificando cuando hay cuartos con una o ninguna puerta.
La solución es única porque cada cuarto solo tiene dos puertas, si un cuarto tuviese más de dos puertas y el problema no permite más simplificación entonces el problema tiene varias soluciones y se puede escoger la más óptima teniendo en cuenta la suma de los valores de los pesos de los cuartos que intervengan en cada solución.
La solución es una cadena de números (no necesariamente en orden) que comienza con el menor número (qué representa la entrada) y termina con el mayor (que representa la salida). Esta cadena de números indica el camino a seguir para llegar a la salida, cuarto por cuarto.
Para encontrar la solución se eliminan las dos últimas columnas de la tabla final:
Cuarto | Comunicación | |
1 | 0 – 2 | |
2 | 1 – 5 | |
5 | 2 – 6 | |
6 | 5 – 8 | |
8 | 9 – 6 | |
9 | 8 – 10 | |
10 | 9 – 11 | |
Se ordena de menor a mayor los números de la segunda columna:
Cuarto | Comunicación | |
1 | 0 – 2 | |
2 | 1 – 5 | |
5 | 2 – 6 | |
6 | 5 – 8 | |
8 | 6 – 9 | |
9 | 8 – 10 | |
10 | 9 – 11 | |
Ahora se forman secuencias de números colocando el número de la primera columna en medio de los números de la segunda columna. En estas secuencias el número del centro significa que este cuarto sirve de puente entre los cuartos que están en los extremos de la secuencia.
Secuencias |
0 – 1 – 2 |
1 – 2 – 5 |
2 – 5 – 6 |
5 – 6 – 8 |
6 – 8 – 9 |
8 – 9 – 10 |
9 – 10 – 11 |
Estas secuencias se sobreponen para formar una secuencia más extensa, Dos secuencias se sobreponen si los números iniciales de una coinciden con los números finales de la otra:
Por ejemplo las dos primeras secuencias se pueden unir así:
0 – 1 – 2 – 5
De esta manera se pueden unir todas las secuencias así:
0 – 1 – 2 – 5 – 6 – 8 – 9 – 10 – 11
Quitando los valores de entrada ( 0 ) y salida ( 11 ) se obtiene la solución final:
1 – 2 – 5 – 6 – 8 – 9 – 10
Para encontrar la solución final, borramos las puertas:
Trazamos la solución siguiendo la secuencia final de los cuartos:
Finalmente borramos los números de los cuartos:
Sumando los pesos correspondientes a estos cuartos dados en distancias obtenemos la distancia total de la solución:
17 + 14 + 8 + 8 + 14 +14 +17 = 92
Como vemos, el modelo de laberintos aquí descrito nos permite encontrar la solución a un laberinto sin cambiar su estructura.
Si hay varias alternativas de solución, estas se analizan con los pesos y así se puede determinar la mejor, si dos soluciones son equivalentes en costo por ejemplo, se puede entrar a analizar un segundo peso, por ejemplo el tiempo y así podemos determinar cual es la mejor solución de las dos teniendo en cuenta un primer criterio y un segundo criterio en caso de empate.
Mediante este modelo se puede desarrollar un sistema que controle los semáforos en una ciudad y permita descongestionar el tráfico de acuerdo a la situación que se presente momento a momento, para ello se puede desarrollar un semáforo con tres luces azules en forma horizontal, cuando la luz azul central se encienda significará que hay un trancón hacia delante, si la luz azul de la izquierda se enciende significará que hay un trancón si gira hacia la izquierda y si se enciende la luz azul de la derecha indicará que si gira hacia la derecha encontrará un trancón, esto permitiría descongestionar el tráfico de una ciudad y evitar que el trancón crezca. Dos luces azules encendidas indicarán que en las dos direcciones indicadas hay un trancón.
Cuando este modelo alcance un mayor grado de desarrollo el modelo también puede permitir organizar una búsqueda de rescate o de exploración, de la misma manera se puede determinar mediante este modelo en que lugares se puede perforar el laberinto para encontrar una mejor solución para conectar dos lugares.
Autor:
Serafín Ortega Moreano
| Página siguiente |