Der Dijkstra-Algorithmus history menue Letztmalig dran rumgefummelt: 20.06.18 16:14:48

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:
... 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 history menue scroll up

 

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

 
   
 
 
 


2. Hintergründe, Zusammenhänge - Einordnung in Klassen history menue scroll up

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 history menue scroll up
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

Dijkstra-Ameisen-Konzept ohne Unwichtiges am 23.2.2017

Dijkstra-Ameisen-Konzept ohne Unwichtiges am 23.2.2017

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 history menue scroll up

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 history menue scroll up

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 history menue scroll up

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


7. Links zum Thema history menue scroll up

 
 


8. Verwandte Themen history menue scroll up

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

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)