Der Dijkstra-Algorithmus

Letztmalig dran rumgefummelt: 27.02.24 17:22:37

	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 - die Sache mit den Dijkstra-Ameisen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösunsverfahren Edsger W. Dijkstra Logo für den Dijkstra-Algorithmus begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Abenteuer Informatik - Informatik zum Anfassen von Routenplaner bis bis Online-Banking  Seite 1 ff.
	... die nächsten Verwandten ... sowie nun die Wuzel des "Übels" die nächste Verwandschaft - Adjatzenmatrizen Allgemeines Netzwerk - so verwendet von vielen naturwissenschaftlichen sowie technischen Disziplinen

1. Problembeschreibung

	Karte Sachsens zur Problemerarbeitung - wir werden uns immer auf genau diese Karte beziehen

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

	Routenplaner gehören heute schon fast zum Alltag: Viele Autos haben sie bereits eingebaut, wer keinen im Fahrzeug hat, lässt sich den günstigsten Weg zu seinem Ziel oft auf dem heimischen PC ermitteln und druckt ihn aus.
	Versuchen wir es doch gleich: Nehmen Sie einen großen Straßenatlas und ermitteln Sie die günstigste Strecke von Stockheim nach Weilheim! Zu viel Arbeit? Kein Atlas? Also gut - ich hatte in der Einleitung ja versprochen, dass alle notwendigen Materialien hier im Buch seien. Daher arbeiten wir erst einmal mit der folgenden kleinen Welt nach Abbildung 1.1.
	Die Karte zeigt Orte, zwei Autobahnen, größere und kleinere Landstraßen. Die roten und blauen Zahlen geben dabei immer die Länge der Straße an, wenn man sie mit dem Auto fährt. Man kann sehen, dass kleine Straßen meistens viel länger sind, als sie scheinen, weil die vielen Kurven und Berge nicht eingezeichnet sind. Welches ist denn nun der günstigste Weg von Imstadt nach Oppenheim? Erster Ansatz wäre, zur nächsten Autobahn zu fahren. Aber geht das am besten über Pappstadt oder die Auffahrt Budingen? Außerdem führt ja von Pappstadt aus auch eine direkte Landstraße zum Ziel. Die ist aber wohl gewunden und ziemlich lang. Oder doch lieber die gelbe Straße zum Flughafen und von dort die Autobahn nach Oppenheim nehmen?
	Versuchen Sie, die Lösung selbst herauszufinden. Hinweis: Sie müssen 123 Kilometer zurücklegen! Geschafft? Gut! Dann lehnen Sie sich zurück und genießen Sie den Erfolg. Wie sind Sie vorgegangen? Sie haben wahrscheinlich alle möglichen Wege durchprobiert und die Entfernung zum Ziel ermittelt. Dann haben Sie sich für den günstigsten Weg entschieden. Dieses Verfahren gibt es auch bei Computern - es hat sogar einen Namen: die Brute-Force-Methode, also etwa „Brutale Macht". Warum? Weil auf diese Weise etwas größere Probleme nur mit extrem großer Rechenkraft gelöst werden können. Überlegen Sie einmal, wie viele verschiedene Wege Sie schon bei der kleinen Problemgröße durchspielen mussten. Stellen Sie sich nun vor, wie das bei Karten mit 1000 und mehr Städten ist - hier wären normale Rechner gar nicht mehr zur Lösung fähig. Außerdem besitzt ein Rechner keine Intelligenz: Während Sie beim Durchprobieren unbewusst alle absurden und unwahrscheinlichen Möglichkeiten verwerfen, muss er diese durchrechnen.   Brute-Force-Angriffe ... verwendete Realkarte
	Vorüberlegungen Wie kommt ein Informatiker nun zu einer besseren Lösung? Zunächst sollte man mit der Methode der Abstraktion arbeiten! Die Methode der Abstraktion In zur Verfügung stehender Information stecken sowohl relevante als auch unwesentliche Anteile. Durch Abstraktion reduzieren Sie die Information auf das für die aktuelle Problemlösung Wesentliche: Dadurch können Sie sich besser auf Ihre Aufgabe konzentrieren. Man könnte auch sagen: Werfen Sie alles Überflüssige über Bord und konzentrieren Sie sich auf das Wesentliche. Was ist aber bei der gestellten Aufgabe wesentlich? Alle gegebenen Informationen stecken in vier Karte. welche Typen von Informationen kann man erkennen? Erstellen Sie eine Liste, bevor Sie weiter lesen. Die Informationen der Karte sind in folgender Tabelle zusammengefasst.   sehr wichtig ... könnte interessieren nicht wichtig Namen der Städte    Position der Städte    Größe der Städte    Verlauf der Straßen    Länge der Straßen    Namen und Nummern der Straßen    Straßentyp    Straße führt von ... nach ...    Landschaftliche Information    Überlegen Sie weiter, welche Informationen wir benötigen, um den kürzesten Weg zwischen zwei Städten zu suchen. Markieren Sie für jede Information, ob diese im Zusammenhang für Sie wichtig ist, oder eben nicht wichtig ist. Der kürzeste Weg soll sich in unserem Beispiel auf den Weg und nicht auf die Zeit beziehen. Mein Ergebnis ist folgendes: Namen der Städte Position der Städte Größe der Städte Verlauf der Straßen Länge der Straßen Namen und Nummern der Straßen Straßentyp Straße führt von ... nach ... Landschaftliche Information Nun kann die Karte neu gezeichnet werden und zwar so, dass möglichst alle irrelevanten und damit störenden Informationen fehlen. Versuchen Sie es einmal selbst, bevor Sie weiter lesen: Basis-Information sehr wichtig ... könnte interessieren nicht wichtig Namen der Städte WICHTIG! Wenn man nicht weiß, welche Stadt wie heißt, kann auch nicht der kürzeste Weg zwischen Imstadt und Oppenheim bestimmt werden     Position der Städte     NICHTWICHTIG! Es ist uns egal, wo sich die Städte genau befinden. Relevant sind nur die Straßen zwischen den Städten. Größe der Städte     NICHT WICHTIG! Kommt in unserer Aufgabenstellung nirgendwo vor. Verlauf der Straßen     NICHT WICHTIG! Es kommt nur auf die Strecke an, nicht auf den Verlauf. Länge der Straßen WICHTIG! Um die Reisestrecke zu bestimmen, brauchen wir die einzelnen Strecken zwischen den Orten.     Namen und Nummern der Straßen     NICHT WICHTIG! Zumindest zur Bestimmung der kürzesten Strecke irrelevant. Straßentyp     NICHT WICHTIG! Da es nur auf die Entfernungen, nicht auf Zeit ankommt, ist egal, ob Autobahn oder Feldweg gefahren wird. Straße führt von ... nach ... WICHTIG! Wir benötigen die Information, von welcher Stadt zu welcher anderen eine Straße führt.     Landschaftliche Information   VIELLEICHT WICHTIG - für die Sightseeing-Tour
	Aus Gründen der Übersichtlichkeit habe ich hier in Abbildung rechts die Städte auf ihren ersten Buchstaben reduziert. Das ist jedoch nicht unbedingt notwendig und wenn Ihre Lösung die ausgeschriebenen Namen enthält, können Sie auch damit weiterarbeiten. Man sieht, dass es noch ein paar Spezialitäten gibt: An drei Stellen kreuzen sich zwei Straßen, ohne dass es Auf- oder Abfahrten von einer zur anderen gäbe (z. B. eine Autobahnbrücke über einer Landstraße). Dies ist mit einem Bogen dargestellt. Außerdem gibt es weitere drei Stellen, an denen sich zwei Straßen schneiden und es Auf- und Abfahrten gibt - gekennzeichnet mit einem Punkt. Informatiker sind jedoch prinzipiell faul und lieben es übersichtlich: Zu viele spezielle Fälle und Unterscheidungen machen das Denken schwierig. Wie bei Mathematikern, die einen Bruch erst einmal auf den gleichen Nenner bringen, wird hier auch versucht, ein Problem möglichst gleichförmig darzustellen. Abstraktion begegnet uns ständig! Wegweiser, Straßenschilder, Fahrpläne, Infobroschüren und viele andere Dinge des Alltags sind so aufbereitet, dass die nötigen Informationen möglichst offen und gut erkennbar dargestellt sind. abstrakte Kartenform, welche jeder kennt ... verwendete idealisierte Karte

3. Lösungsalgorithmus - die Sache mit den Dijkstra-Ameisen

	Der Dijkstra-Algorithmus gehört zu den informatischen Problemen, welche, wie so viele für kleine n bequem auch mit Hand lösbar sind - und diese zeigen somit auf, das das alte Sprichwort von Dijkstra immer noch seine Gültigkeit hat: Informatik hat mit dem Computer so viel zu tun, wie Astronomie mit dem Fernrhr!
	Original-Karte Karte gestreckt ... ... und die Krümmungen entspannt ... ertse bezugspunkte mögliche Erweiterungen ... verwendete Realkarte ... Landkarte mit durch Orte ersetzten Knotenpunkten ... "entspannte" verwendete abstrahierte Karte ... erster Punkt auf der "entspannten" verwendeten abstrahierte Karte ... erster Punkt auf der "entspannten" verwendeten abstrahierte Karte
	Methode der Gleichformung Versuchen Sie, die verschiedenen Facetten eines Problems auf die gleichen Grundelemente zurückzuführen. Dadurch wird einerseits das Problem übersichtlicher und andererseits benötigt man weniger Lösungsansätze: Für gleichförmige Teilprobleme kann der gleiche Lösungsansatz verwendet werden. Können Sie die Karte auf diese Weise noch einfacher gestalten? Überlegen Sie, welches die Eigen,cimtten der „normalen" Elemente sind und ob man die speziellen Elemente nicht rauch als normale Elemente darstellen kann. Auf der Karte sind Städte als Kreise eingezeichnet. Ohne dass dies speziell vermerkt ist, kann man offenbar bei Städten problemlos von einer Straße auf eine angrenzende Straße wechseln. ... Landkarte mit durch Orte ersetzten Knotenpunkten ... "entspannte" verwendete abstrahierte Karte
	Genau das soll auch an den mit Punkt gekennzeichneten Stellen möglich sein. Also tun wir einfach so, als wenn sich dort Städte befinden. Um sie nicht mit den anderen Städten zu verwechseln, nennen wir sie ( X ), ( Y ) und ( Z ). Den fertigen Plan zeigt Abbildung unten An allen weiteren Kreuzungspunkten zwischen zwei Straßen ist jetzt kein Wechsel mehr möglich. Es ist daher auch keine Unterscheidung, also auch keine Kennzeichnung durch Bogen mehr notwendig. Die Städte sind immer noch auf ihrer geographischen Position eingezeichnet. Dadurch ergeben sich an manchen Stellen Ballungszentren. Die Straßenführung wird unübersichtlich. Die geographische Position der Städte haben wir jedoch weiter vorne als unrelevant deklariert. Um es Ihnen so einfach wie möglich zu machen, habe ich die Karte in Abbildung 1.4 etwas entzerrt. Bitte überprüfen Sie, dass die Inhalte immer noch übereinstimmen, also die Verbindungen zwischen den Städten gleich sind und die gleiche Längenangabe aufweisen. Lediglich die Darstellung hat sich geändert. Sie können auch überprüfen, dass es sich noch um die gleiche Karte handelt wie am Anfang des Kapitels - lediglich mit weniger Detailinformationen. Mit dieser Karte werden wir im Folgenden weiter arbeiten :-) Leonhard Euler (* 1707 t 1783) nach einem Pastell von Emanuel Handmann 1753: Euler hat schon 1736 als Erster Wegeprobleme durch abstrakte Darstellung vereinfacht, als er das Königsberger Brückenproblem löste: „Gibt es einen Rundweg, der alle sieben Brücken über den Fluss Pregel genau einmal überquert und wieder zum Ausgangspunkt führt?" Euler bewies, dass es keinen solchen Weg geben kann
	... bildliche Darstellung Aufgaben sowie Auswertung Komplett-Übersicht keine Geo-Caches - keine Sehenswürdigkeiten - keine Tankstellen - nur Orte Dijkstra-Ameisen-Konzept komplett am 23.2.2017 Dijkstra-Ameisen-Konzept komplett am 23.2.2017 Achtung!!! NEU Dijkstra-Ameisen-Konzept ohne Unwichtiges am 27.2.2024 Dijkstra-Ameisen-Konzept ohne Unwichtiges am 27.2.2024 Straßen-Übersicht Straßen-Übersicht - Sehenswürdigkeiten Dijkstra-Ameisen-Konzept Straßen am 23.2.2017 Dijkstra-Ameisen-Konzept komplett am 23.2.2017 Dijkstra-Ameisen-Konzept Sehenswürdigkeiten am 23.2.2017 Dijkstra-Ameisen-Konzept Sehenswürdigkeiten am 23.2.2017 Straßen-Übersicht - Tankstellen keine Geo-Caches- keine Sehenswürdigkeiten - keine Tankstellen Dijkstra-Ameisen-Konzept Tankstellen am 23.2.2017 Dijkstra-Ameisen-Konzept Tankstellen am 23.2.2017 Dijkstra-Ameisen-Konzept Geocaching am 23.2.2017 Dijkstra-Ameisen-Konzept Geocaching am 23.2.2017     Zeit-Umrechnung   ... Geschwindigkeit und Entfernung in Zeit umrechnen

4. Programmvorschläge

	Zum Zweck der Programmierung muss die ganze Sache wesentlich vereinfacht - folgerichtig eine frühe Variante der Kartenentwicklung genutzt werden. Bevor alles diesbezüglich beginnt, versuche ich die derzeit bekannten "Entwicklungsmethoden" sowie Parameter zu umreißen.
	... bildliche Darstellung Software-Lösungen Dijkstra-Ameisen-Konzept am 8.2.2017 Dijkstra-Ameisen-Konzept am 8.2.2017

5. Aufgaben

	Jetzt machen wir Informatik. In allen Bereichen, welche uns bisher bekannt sind, suchen wir eine gerade aktuelle Geschwindigkeit. Steigern wir das, so suchen wir die gerade wirkende Beschleunigung - aber auch nicht gerade wirklich viel komplexer für erfahrene Physiker.
	... geltende Regeln: kürzestes Strecke - das ist einfach die Streckenführung mit den wenigsten Kilometern schnellste Strecke - einfach die Strecke mit der kürzesten Zeit effizienteste Strecke - umweltbewusste Streckenführung (eine Kombination aus Steigung, Kurven, Bremsvorgängen, Ampeln und weiteren objektiv verzögernden Hindernissen) Geological-Tour-Seeing-Tour (.. tangiere viele Seen, Berge) Sight-Seeing-Tour (.. tangiere viele Sehenswürdigkeiten in Orten sowie in der Natur) Tankstelle unter gegebenen Zusatzbedingungen (der Abstand zum konkreten Standort ist aus den Innenradien der jeweiligen Städte zu ermitteln)!
	... und ab der Fisch: ich möchte am schnellsten von AR nach CD  - berechnen Sie die Fahrzeit! wie viele Sehenswürdigkeiten finde ich in der Umgebung von CF in einem Radius von ca. 20 km Luftlinie? wie viele Sehenswürdigkeiten liegen weniger als einen Kilometer von Seen entfernt? ... auf der Fahrt von AF nach DC möchte ich Geocachen gehen - wie viele Caches finde ich bis jeweils maximal ca. 1 km von der Streckenführung aus entfernt?

6. Weiterführende Literatur

	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig

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 Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem 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
	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 am 18. Juli 2012 um 16.28 Uhr