Original source: https://www.cs.cmu.edu/~bryant/boolean/maps.html
Don Knuth está trabajando en el Volumen 4 de El arte de la programación informática . Uno de los capítulos es sobre Diagramas de Decisión Binaria y sus aplicaciones, tema que me parece muy interesante. Knuth muestra que se pueden codificar una variedad de problemas gráficos interesantes como fórmulas booleanas, y el BDD derivado representa todas las soluciones posibles al problema. A menudo existe algún tipo de criterio de optimización y es bastante fácil extraer la “mejor” solución del BDD mediante un simple algoritmo de programación dinámica.
Aquí mostramos algunos ejemplos, utilizando el gráfico que representa los 48 estados contiguos, con un nodo para cada estado y un borde entre dos estados si comparten un borde. Para cada uno de los mapas, si haces clic en la imagen llegarás al documento fuente en formato SVG . Aquí está el gráfico, ubicando los nodos en las capitales de los estados:
Tours por las capitales
Suponga que desea visitar las capitales de los 48 estados con el requisito de pasar por cada estado solo una vez. (En otras palabras, desea encontrar una ruta hamiltoniana en el gráfico). Como puede ver en el mapa anterior, si sigue la ruta más directa entre las capitales de los estados, a menudo pasará por otro estado o, en el caso de Desde Lansing, Michigan hasta Madison, Wisconsin, cruzará el lago Michigan. En su lugar, debe tomar la ruta de conducción más corta que permanezca dentro de los dos estados para cada tramo del viaje. Llamemos a esta ruta Tour por la Capital. Aquí hay un diagrama de las rutas permitidas entre los estados:
Basándonos en un simple análisis, más los esfuerzos de Knuth, podemos decir lo siguiente:
- Todos los recorridos deben comenzar o terminar en Maine, ya que Maine tiene un solo vecino. Usaremos Maine como punto de partida.
- Todos los recorridos deben terminar más allá de Nueva York, ya que es un punto de articulación.
- En total, hay 68.656.026 recorridos por la capital diferentes.
Aquí está el recorrido más corto por la capital, con un total de 11,698 millas:
Aquí está el recorrido más largo por la capital, con un total de 18,040 millas:
Coloración de gráficos
Otra clase interesante de problemas implica colorear el mapa. La regla es que dos estados adyacentes no pueden tener el mismo color. El famoso teorema de los cuatro colores establece que cualquier gráfico plano se puede colorear con un máximo de cuatro colores.
Dado que un BDD codifica todas las soluciones posibles a una fórmula booleana, podemos calcular fácilmente cuántas soluciones hay. Para colorear gráficos, ajustamos nuestros recuentos para eliminar simetrías debido a la asignación arbitraria de valores de color (¡4! casos simétricos para 4 colores).
Para colorear los 48 estados contiguos, hay 533.816.322.048 coloraciones posibles. (Esto es la mitad del número reportado por Knuth, ya que su mapa incluye a Washington, DC como el “estado” número 49, y se le puede asignar cualquiera de los dos colores que no se usan para Maryland y Virginia). Ejemplos de colorantes especiales:
- Una coloración equilibrada, en la que cada color se utiliza exactamente para 12 estados. Hay 12.554.677.864 colorantes de este tipo, lo que supone un sorprendente 2,4% de todos los colorantes posibles.
- Una coloración desequilibrada, en la que uno de los colores (verde) se utiliza lo menos posible (2 estados). Sólo hay 288 formas de colorear el mapa, de modo que un color se utilice sólo dos veces.
- Una coloración desequilibrada, en la que se utiliza en la mayor medida posible uno de los colores (amarillo) (18 estados). Hay 71.002.368 formas de colorear el mapa de modo que un color se utilice 18 veces.
- Combinando ambos. Coloraciones usando los colores 2, 13, 15 y 18 veces. Esta secuencia 1) de izquierda a derecha, usa cada color en sucesión la menor cantidad de veces posible, y 2) de derecha a izquierda, usa cada color en sucesión la mayor cantidad de veces posible. Hay 24 soluciones de este tipo.
Desde la perspectiva de los programas para colorear gráficos, el mapa de los 48 estados de EE. UU. es bastante simple. Para obtener un mapa más desafiante, consulte la página web sobre McGregor Graph .
I’ve always been captivated by the wonders of science, particularly the intricate workings of the human mind. With a degree in psychology under my belt, I’ve delved deep into the realms of cognition, behavior, and everything in between. Pouring over academic papers and research studies has become somewhat of a passion of mine – there’s just something exhilarating about uncovering new insights and perspectives.