Algoritmo para atravesar un laberinto condicional

Question

Imagina un laberinto donde hay habitaciones y puertas. Usted sólo puede ir en una dirección a través de una puerta. Algunas puertas están cerradas. Algunas de ellas contienen claves para ciertas puertas. En efecto, cada vez que encuentra una clave, el laberinto de los cambios.

En la imagen de abajo, las puertas abiertas se muestran como los contornos de las puertas que se muestra lleno de color gris. Las flechas muestran las direcciones que usted puede ir. Las teclas se muestran como sectores (como el movimiento de una abertura de la puerta). El azul pálido de la puerta de la habitación de D para la sala de C no existe.

Sala B contiene la clave para la sala D sala D contiene la clave de la sala de Correo, y la sala E, contiene la clave de la sala de F. es posible llegar a la habitación D siguiendo el camino a>B>C>A>D. por lo tanto, puede obtener la clave de la sala E.

Sin embargo, si la puerta azul no existe, ahora no hay forma de volver a la sala a abrir la puerta de la habitación de E. Porque no se puede llegar a la sala de Correo, usted no puede conseguir la llave para abrir la puerta de la sala de F, por lo que no se puede llegar a la sala de F cualquiera.

En este caso, está claro que nunca se puede llegar a las salas E y F, a menos que una nueva puerta que se crea.

Mi problema es: imaginar cualquier laberinto, de cualquier nivel de complejidad. Hay un algoritmo que va a mostrar si es posible llegar a todas las habitaciones?

Asumiendo un punto de vista externo del laberinto, es fácil de encontrar si:

• Hay una puerta abierta a cualquier habitación
• Hay una clave, en alguna parte, por cualquier puerta

Los principales problemas son:

• Se puede llegar hasta la llave para cada puerta?
• Cuando usted tiene la llave para una puerta, se puede llegar a esa puerta?
• Si una habitación no puede ser alcanzado, ¿cuál es el cambio más pequeño que se podría hacer para resolver esto?

Answer 1

Con finito de puertas y llaves, es posible enumerar todas las rutas.

Recorrer el gráfico de amplitud primer seguimiento de los nodos que se han visitado. Al entrar en una habitación con llave, calcular el cierre transitivo de ese nodo con la nueva puerta abierta. Agregar cada uno de los miembros de la clausura transitiva como una ventaja para el nodo actual (después de este borde debe añadir el necesario tránsito de habitaciones para los visitó lista), y visitar sólo los nodos en esta lista que no han sido visitados previamente. El algoritmo siempre va a detener.

Utilizando el conjunto de todos los conjuntos de nodos visitados usted puede contestar las siguientes:

• Se puede llegar hasta la llave para cada puerta? Hay una serie en la recogida de datos que contiene todos los nodos que contienen llaves?
• Cuando usted tiene la llave para una puerta, se puede llegar a esa puerta? Hay una serie en la recogida de datos que contiene el nodo con la clave y el nodo de la puerta que la llave abre?
• Si una habitación no puede ser alcanzado, ¿cuál es el cambio más pequeño que se podría hacer para resolver esto? Usted puede agregar un borde desde el inicio de esta sala, y técnicamente hemos terminado.

Si de verdad quieres decir que para determinar el cambio más pequeño que permite que todo el laberinto para ser atravesado, usted podría intentar todo lo posible adición de un borde, y luego cada posible adición de dos filos, luego cada posible adición de tres bordes, etc, hasta que tenga un grafo completo. En algún lugar a lo largo de la manera en que el laberinto tiene cada nodo visitable.