Clase 14. Grafos de estado · AyG C14¶
Viernes 23 de octubre de 2026, de 7:00 a 9:00, grupo B.
En The New Villa, UVa 321, la entrada trae habitaciones y puertas, y una
búsqueda en amplitud sobre ellas responde que el dormitorio está a un paso del
hall. La respuesta es falsa, porque el dormitorio empieza a oscuras. Lo que se
puede hacer en cada momento depende de dónde está el señor Black y de qué
luces están prendidas, y ese par es el vértice del grafo que hay que recorrer.
La sesión dibuja ese grafo por capas sobre la villa del enunciado, guarda el
conjunto de luces en un entero con 1 << i, & y ^, y sigue en una tabla
la búsqueda en amplitud de una implementación en C++, hasta la solución de
\(6\) pasos.
-
Grafos de estado
Estados y transiciones de UVa 321, el grafo de la villa 1 capa por capa, las máscaras de bits con sus tablas, el código C++ línea por línea, la traza de la búsqueda, los errores comunes y seis ejercicios con pistas.
-
Diapositivas
El deck de la sesión, con la villa del enunciado dibujada y su grafo de estados construido capa por capa, primero con conjuntos de luces y después con máscaras.
Apuntes de la sesión¶
- En C++ la resta se evalúa antes que el desplazamiento, de modo que
1 << r-1y1 << (r-1)son lo mismo. Compilar las dos formas da el mismo valor, y escribir los paréntesis sale más barato que recordar la tabla de precedencias. - El grafo de estados tiene ciclos: prender una luz y apagarla devuelve al
vértice de partida. La amplitud sigue dando el camino más corto porque
distmarca lo ya descubierto y ningún estado se expande dos veces. - El estado es una estructura y no un entero, y por eso la tabla de lo
visitado pide algo más:
mapnecesita un comparador, yunordered_mapnecesitahashyoperator==. Las dos versiones pasan el juez. Codificar la pareja en un solo entero, \(h \cdot 2^R + L\), ahorra las dos cosas.
Ejercicios¶
Las actividades interactivas del tema están en la página de ejercicios. Los seis ejercicios de las diapositivas, con sus pistas, están al final de la nota. Van desde dibujar las primeras capas de otra villa hasta demostrar que la luz de la habitación donde se está siempre queda prendida.
Antes de entrar¶
Conviene repasar la sección de grafos de estado de la nota de Bellman-Ford-Moore, que presenta el mismo problema y el mismo código, y los grafos implícitos, donde los vecinos de un vértice se calculan con una regla en lugar de leerse de una lista.