← Volver a los ejercicios

Grafo de estados

En UVa 321 The New Villa no hay un grafo dado: los vértices se construyen. Un estado es el par (habitación, máscara de luces) y de cada estado salen aristas de peso 1: pasar a una habitación vecina cuya luz esté prendida, o cambiar con un interruptor la luz de otra habitación. Aquí se ejecuta la función solve de 321-new-villa.cpp sobre una villa pequeña, línea por línea, hasta ver cómo la búsqueda en amplitud descubre los estados y cómo la meta trae consigo la lista de pasos. Se empieza en la habitación 1 con solo su luz prendida y se quiere terminar en la última habitación con solo su luz prendida.

1. La villa y la predicción

Villa:

Interruptores: No se cambia la luz de la habitación donde se está.

Se dibuja el estado que acaba de salir de la cola: contorno azul en la habitación actual y relleno amarillo en las que tienen la luz prendida.
¿Cuántos estados hay en dist cuando termina el ciclo?

2. Ejecute solve

cola q, de la salida a la entrada: [ ]
Lo que ha impreso el programa:
–
Paso 0 de 0
El número de cada línea es el de 321-new-villa.cpp. Un estado se escribe (habitación, {luces prendidas}) y la máscara va en decimal y en binario, con la luz 1 a la derecha. Las dos líneas for cuentan una vez por cada valor de i.

3. El mapa dist

EstadoMáscaradiststeps que trae
Cada estado se guarda con la lista completa de pasos que lo alcanzó; no hay vector de predecesores. Las filas están en el orden en que entran a dist, que es el orden en que salen de la cola.

4. Los pasos de la solución

Al sacar la meta de la cola, res la guarda y el ciclo termina. La respuesta se imprime recorriendo res.steps de principio a fin: no hay que reconstruir nada hacia atrás.

5. Para llevarse

En la villa sin solución, diga cuál es el último estado que se descubre y por qué no se puede llegar a la meta. Después compare los estados en dist de las dos villas en fila: una se detiene antes de explorar todo lo alcanzable y la otra no. Por último, diga qué cambiaría en los resultados si el ciclo de puertas se escribiera después del de interruptores.