Das Flaggenproblem

Letztmalig dran rumgefummelt: 22.12.14 12:06:21

	Das Flaggenproblem ist eine aus der Informatik stammende Problemstellung, die der niederländische Wissenschaftler E. W. Dijkstra entwickelte. Es ist auch unter dem Namen "3 - Farben - Problem" bekannt. Ursprünglich formulierte Dijkstra das Flaggenproblem folgendermaßen: "Ein Roboter erhält die Aufgabe, eine Anzahl von gefärbten Kieselsteinen, die in einer Reihe von Eimern liegen, zu sortieren. Die Eimer stehen vor dem Roboter und jeder von den Eimern enthält genau einen Kieselstein, der entweder rot, weiß oder blau ist. Der Roboter besitzt zwei Arme, die an den Enden jeweils ein Auge haben. Mit diesen Augen kann der Roboter die Farbe des Kieselsteines bestimmen, mit den Armen kann er die Inhalte zweier Eimer vertauschen."
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	und nun haben wir hier das Flaggenproblem mal für Dich zum Lösen ;-)        - viel Spaß, aber nicht schummeln, immer nur zwei Kästchen austauschen! hier mal eine nicht ganz kleine Reihe von Kästchen ;-) hier das Projekt im CorelDraw 11-Format ;-)
	Probleme & Problemlösungsverfahren Edsger W. Dijkstra   Logo für das Flaggenproblem begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

	Für praktische Lösungsvarianten mit effizienten Algorithmen ist es nicht ganz unwesentlich, ob die Anzahl der "Ausgangs-Flaggen" gerade oder ungerade ist. Entscheidend ist, wo dann das Feld jeweils geteilt werden muss und mit welcher Farbe begonnen wird!
	Nun, diese recht praxisnahe Problemstellung läst sich folgendermaßen kurz umschreiben:  Gegeben ist eine Folge von n Fächern, jedes Fach enthält ein Steinchen. Folge von n Fächern
	Die Steinchen bekommen die Farben rot, weiß oder blau. Dabei werden die Steinchen immer wieder in gleicher Reihenfolge angeordnet. Regelmäßige Anordnung der hier 33 Farbenfelder
	Die Anordnung ist immer ein rotes Steinchen, rechts daneben ein weißes und rechts neben einem weißen Steinchen ein blaues Anfangssituation beim Flaggenproblem
	Nun wird ein Roboter vor die Fächerreihe gestellt und der Roboter soll so programmiert werden, die Steinchen in den einzelnen Fächern so umzuordnen, dass zuerst (ganz links) alle roten, dann alle weißen und dann alle blauen Steinchen (rechts) in den Fächern liegen Endsituation beim Flaggenproblem
	Nun ist auch logisch woher der Name "Flaggenproblem" rührt, nämlich davon, dass die Farbenfolge der Steinchen im geordneten Zustand (von links gesehen) der niederländischen Nationalflagge entspricht. Man kann aber die Problematik der niederländischen Nationalflagge auf jede andere Flagge, die ebenfalls 3 Farben hat, übertragen.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	effiziente Lösung nur als rekursiver Algorithmus
	gegenseitige Rekursion - die Funktionen für größer 100 und kleiner 100 für die Zwischenwerte rufen sich gegenseitig auf
	Das Flaggen-Problem wird in abgewandelter Form auf jedem Rangierbahnhof, in jedem Warenliefersystem, in der Postzustellung usw. praktisch gelöst

3. Lösungsalgorithmus

	Dies war die zweite Aufgabe des Flaggenproblems, nämlich nicht nur das Umsortieren der Steinchen, sondern auch das Umsortieren so effizient wie möglich zu machen. E. W. Dijkstra, der Entwickler des Flaggenproblems, ist dabei folgendermaßen vorgegangen. Er schrieb ein Programm in PASCAL in dem der gesuchte Algorithmus als Prozedur dargestellt wird. Hier eine vereinfachte Version seines entworfenen Algorithmus in PASCAL (blau sind die Erklärungen):
	Nun geht es darum das Flaggenproblem zu lösen, sprich alle Steinchen so umzuordnen, dass man als Ergebnis die niederländische Flagge erhält. Dabei wird folgendes vorausgesetzt: der Roboter verfügt über 2 Grundoperationen, die er von selbst beherrscht, das heißt die Grundoperationen sind in seinem Steuerungsmechanismus eingebaut die eine Operation weist den Roboter an, den Inhalt zweier bestimmter Fächer, die nicht nebeneinander liegen müssen, zu vertauschen. die andere Operation ist die Fähigkeit des Roboters ein bestimmtes Fach auszuwählen und die Farbe des sich drin befindenden Steinchens zu bestimmen und zu melden. Die Ausführung dieser zwei Operationen benötigt eine Menge Zeit, da der Roboter ein langsames mechanisches Gerät ist. Deswegen soll nun ein Algorithmus erstellt werden, der die beiden Grundoperationen so wenig wie möglich verwendet. Genauer gesagt bedeutet dass: die Operation "Vertauschen" soll im Durchschnitt so gering wie möglich durchgeführt werden. die Operation "Farbe bestimmen" soll für jedes Fach höchstens einmal angewendet werden. const     n = ...; {n ist die Anzahl aller Fächer} type     index = 1..n; {index ist der array, der die Fächerreihe darstellt}   farbe = (rot, weiss, blau); {es werden die drei Farben rot weiß und blau definiert} var     r, w, b : index; {r, w und b sind Markierungen in index, dazu komme ich später noch}     procedure vertausche (i, j, help : index); {erste Grundoperation, vertauscht zwei Steinchen} begin     help := i;     i := j;     j := help;   end;       function welchefarbe (i : index) : farbe; {zweite Grundoperation, bestimmt die Farbe eines Steinchens}     begin {Hauptprogramm (gesuchter Algorithmus}   r := 2; {setzt Marke r auf Fach Nr.2}   w := n - 2; {setzt Marke w auf das vorvorletzte Fach (von links)}   b := n - 1; {setzt Marke b auf das vorletzte Fach (von links)}   while w => r do {solange sich Marke w rechts von Marke r oder bei Marke r befindet, tue folgendes:}   begin       case welchefarbe (w) of {bestimme die Farbe des Steinchens bei Marke w}       rot: {ist das Steinchen rot, dann:}       begin           vertausche (w, r); {tausche das Steinchen bei Marke w mit dem Steinchen bei Marke r}         r := r + 1; {setzte Marke r anschließend eins nach rechts}       end;         weiss: {ist das Steinchen weiß, dann:}       begin           w := w - 1; {setzte Marke w anschließend eins nach links}       end;         blau: {ist das Steinchen blau, dann:}       begin           vertausche (w, b); {tausche das Steinchen bei Marke w mit dem Steinchen bei Marke b}         w := w - 1; {setzte Marke w anschließend eins nach links}         b := b - 1; {setzte Marke b anschließend eins nach links}       end;       end;     end;   end;
	Nun ist dieser Quelltext in PASCAL schlecht anschaulich, deswegen werde ich den gesuchten Algorithmus graphisch darstellen. Dazu muss aber folgendes klar sein: die Fächerreihe wird von rechts nach links bearbeitet: es wird immer nur die Farbe des Steinchens bestimmt, auf welches Marke w zeigt zeigt Marke w auf ein rotes Steinchen, dann wird das Steinchen bei Marke w mit dem Steinchen bei Marke r getauscht; als zweites wird Marke r eine Stelle nach rechts gerückt zeigt Marke w auf ein weißes Steinchen, dann wird nur Marke w eine Stelle nach links gerückt zeigt Marke w auf ein blaues Steinchen, dann wird das Steinchen bei Marke w mit dem Steinchen bei Marke b getauscht; als zweites werden Marke w und Marke b eine Stelle nach links gerückt
	Für die graphische Darstellung nehme ich, um die Komplexität zu vermindern, neun Steinchen - es folgt nun Schritt für Schritt die graphische Darstellung des von Dijkstra entworfenen Algorithmus: Abb. 1 zeigt die Ausgangssituation. Die Marken sind bereits gesetzt (die Position der Marken ist bei der Ausgangssituation immer gleich) In Abb. 2 zeigt Marke w ein weißes Steinchen, also wird Marke w eine Stelle nach links gerückt (siehe Abb. 3). In Abb. 3 zeigt Marke w nun auf ein blaues Steinchen, es werden also nun die Steinchen der Marken w und b vertauscht. Danach werden die Marken w und b noch jeweils eine Stelle nach links gerückt (siehe Abb. 4). In Abb. 4 zeigt Marke w auf ein weißes Steinchen, also wird Marke w eine Stelle nach links gerückt (siehe Abb. 5). In Abb. 5 zeigt Marke w wieder auf ein rotes Steinchen, also werden die Steinchen von Marken w und r vertauscht, anschließend wird Marke r noch eine Stelle nach rechts gerückt (siehe Abb. 6). In Abb. 6 zeigt Marke w nun auf ein blaues Steinchen, es werden die Steinchen der Marken w und b vertauscht. Danach werden die Marken w und b noch jeweils eine Stelle nach links gerückt (siehe Abb. 7). Abb. 7 zeigt nun die Endsituation beim Flaggenproblem: Alle roten Steinchen kommen zuerst, dann alle weißen und alle blauen Steinchen (von links gesehen). Außerdem ist Marke w nicht mehr rechts von oder bei Marke r, sondern links von Marke r und dies war auch Abbruchbedingung bei Dijkstras PASCAL - Programm. Berechnet man noch die Häufigkeit der Vertauschungen, so erhält man immer 2/3n Vertauschungen (im Beispiel sind es also 6 Tauschoperationen). Im Vergleich zu einem normalen Bubblesort ist der Sortieralgorithmus beim Flaggenproblem effizienter.

4. Programmvorschläge

	Im Folgenden einige Möglichkreiten
	Testdatei mit 2 Flaggen Downlod im CorelDraw 11.0-Format Testdatei mit 3 Flaggen Downlod im CorelDraw 11.0-Format Testdatei mit 8 Flaggen Downlod im CorelDraw 11.0-Format Testdatei mit 9 Flaggen Downlod im CorelDraw 11.0-Format Testdatei mit 49 Flaggen Downlod im CorelDraw 11.0-Format

5. Zusammenfassung

6. Weiterführende Literatur

	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
	es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

7. Links zum Thema

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem Dijkstra-Algorithmus
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im April 2003