Saltar a contenido

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.

    Entrar

  • 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.

    Abrir

Apuntes de la sesión

  • En C++ la resta se evalúa antes que el desplazamiento, de modo que 1 << r-1 y 1 << (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 dist marca 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: map necesita un comparador, y unordered_map necesita hash y operator==. 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.