Interessante Kartenprobleme

Originaldokument (Englisch): http://www.cs.cmu.edu/~bryant/boolean/maps.html

Don Knuth arbeitet an Band 4 der Kunst der Computerprogrammierung. Eines der Kapitel befasst sich mit binären Entscheidungsdiagrammen und deren Anwendungen, ein Thema, das ich sehr interessant finde. Knuth zeigt, dass eine Vielzahl von interessanten Grafikproblemen als Boolesche Formeln kodiert werden können, und das abgeleitete BDD repräsentiert alle möglichen Lösungen für das Problem. Oft gibt es eine Art Optimierungskriterium, und es ist ziemlich einfach, die “beste” Lösung aus dem BDD mit einem einfachen dynamischen Programmieralgorithmus zu extrahieren.

Hier zeigen wir einige Beispiele anhand der Grafik, die die 48 zusammenhängenden Zustände darstellt, mit einem Knoten für jeden Zustand und einer Kante zwischen zwei Zuständen, wenn sie eine Grenze teilen. Für jede der Karten gelangen Sie durch Anklicken des Bildes zum Quelldokument im SVG-Format. Hier ist der Graph, der die Knoten in den Hauptstädten der Staaten lokalisiert:

Hauptstadt-Touren

Angenommen, Sie wollen die 48 Landeshauptstädte besuchen mit der Anforderung, dass Sie jeden Staat nur einmal durchlaufen. (Mit anderen Worten, Sie wollen einen Hamiltonianischen Pfad in der Grafik finden.) Wie Sie aus der obigen Karte ersehen können, werden Sie, wenn Sie dem direktesten Weg zwischen den Hauptstädten folgen, oft durch einen anderen Staat fahren, oder wenn Sie von Lansing, Michigan nach Madison, Wisconsin, gehen, werden Sie über den Lake Michigan fahren. Stattdessen sollten Sie für jede Etappe der Reise die kürzeste Fahrtroute nehmen, die innerhalb der beiden Staaten liegt. Nennen wir eine solche Route eine Capital Tour. Hier ist ein Diagramm der zulässigen Routen zwischen den Zuständen:

Basierend auf einer einfachen Analyse und Knuths Bemühungen können wir folgendes sagen:

  • Alle Touren müssen in Maine beginnen oder enden, da Maine nur einen einzigen Nachbarn hat. Wir werden Maine als Ausgangspunkt nehmen.
  • Alle Touren müssen jenseits von New York enden, da es sich um einen Artikulationspunkt handelt.
  • Insgesamt gibt es 68.656.026 verschiedene Kapitalreisen.

Hier ist die kürzeste Hauptstadttour mit insgesamt 11.698 Meilen:

Hier ist die längste Hauptstadt-Tour mit insgesamt 18.040 Meilen:

Grafik-Färbung

Eine weitere interessante Klasse von Problemen ist das Einfärben der Karte. Die Regel ist, dass keine zwei benachbarten Staaten die gleiche Farbe haben dürfen. Das berühmte Four Color Theorem besagt, dass jedes planare Diagramm mit maximal vier Farben eingefärbt werden kann.
Da ein BDD alle möglichen Lösungen zu einer Booleschen Formel kodiert, können wir leicht berechnen, wie viele Lösungen es gibt. Für die Grafikfärbung passen wir unsere Zählungen an, um Symmetrien aufgrund der beliebigen Zuordnung von Farbwerten zu eliminieren (4! symmetrische Fälle für 4-Farben).

Für die Einfärbung der angrenzenden 48 Zustände gibt es 533.816.322.048 mögliche Farbgebungen. (Dies ist die Hälfte der von Knuth gemeldeten Zahl, da seine Karte Washington, DC als 49. “Staat” beinhaltet und ihr eine der beiden nicht für Maryland und Virginia verwendeten Farben zugewiesen werden kann.) Hier sind einige interessante Beispiele für Sonderfarben:

  • Eine ausgewogene Farbgebung, bei der jede Farbe für genau 12 Zustände verwendet wird. Es gibt 12.554.677.864 solcher Färbungen, das sind überraschend hohe 2,4% aller möglichen Färbungen.
  • Eine unausgewogene Färbung, bei der eine der Farben (grün) so wenig wie möglich verwendet wird (2 Zustände). Es gibt nur 288 Möglichkeiten, die Karte so einzufärben, dass eine Farbe nur zweimal verwendet wird.
  • Eine unausgewogene Färbung, bei der eine der Farben (gelb) so weit wie möglich verwendet wird (18 Zustände). Es gibt 71.002.368 Möglichkeiten, die Karte so einzufärben, dass eine Farbe 18 Mal verwendet wird.
  • Beides kombiniert. Färbungen mit den Farben 2, 13, 15 und 18 mal. Diese Sequenz 1) von links nach rechts, verwendet jede Farbe nacheinander für die geringstmögliche Anzahl von Malen, und 2) von rechts nach links, verwendet jede Farbe nacheinander für die größtmögliche Anzahl von Malen. Es gibt 24 solcher Lösungen.

Aus der Sicht von Grafikfärbeprogrammen ist die Karte der US 48 Staaten recht einfach. Eine anspruchsvollere Karte finden Sie auf der Webseite des McGregor Graphen.