Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_dijkstra:start [23.11.2022 19:37] – [Lösungsansatz mit Pfiff] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_dijkstra:start [19.09.2024 07:46] (aktuell) – Marco Kuemmel
@@ Zeile 43: / Zeile 43: @@
 === (A1) ===
-  * Schaue dir den Film an, der den Vorgang zeigt und stelle anhand der Bewegung der Centstücke die Reihenfolge der Knotenentfernungen im Beispielgraphen auf. Überprüfe die so gefundene Reihenfolge anhand der Kantengewichte.
+  * Schaue dir den Film an, der den Vorgang zeigt und stelle anhand der Bewegung der Centstücke die Reihenfolge der Knotenentfernungen im Beispielgraphen auf (Anmerkung: Der Film ist in Zeitlupe aufgenommen, das kann man gut in doppelter Geschwindigkeit anschauen).
 <html>
 <iframe title="Dijkstra-Algorithmus. Veranschaulichung mit Fadennetz." src="https://tube.schule.social/videos/embed/faa8235b-7b95-43b0-b155-8be6ce718f26" allowfullscreen="" sandbox="allow-same-origin allow-scripts allow-popups" width="560" height="315" frameborder="0"></iframe>
@@ Zeile 53: / Zeile 52: @@
 ===== Der Computer zieht die Fäden =====
-Möchte man dieses Trickreiche Vorgehen in einem Algorithmus implementieren, muss man anstelle der Fäden andere Kriterien finden. Der Schlüssel zum Ersatz der Fäden ist die Antwort auf folgenden Frage:
+Möchte man dieses trickreiche Vorgehen in einem Algorithmus implementieren, muss man anstelle der Fäden andere Kriterien finden. Der Schlüssel zum Ersatz der Fäden ist die Antwort auf folgenden Frage:
 Welcher Knoten ist stets der nächste, der von der Unterlage abgehoben wird?
@@ Zeile 61: / Zeile 60: @@
 ++++
-Wir benötigen also **zwei Markierungen**: Knoten die in der Liste sind und als nächstes bearbeitet werden können, weil sie Nachbarknoten von Knoten sind, die bereits von der Unterlage abgehoben wurden und die Knoten die sich bereits in den Luft befinden. Im Graphentester kann man z.B, folgende Vereinbarung treffen:
+Wir benötigen also **zwei Markierungen**: Knoten die in der Liste sind und als nächstes bearbeitet werden können, weil sie Nachbarknoten von Knoten sind, die bereits von der Unterlage abgehoben wurden und die Knoten die sich bereits in der Luft befinden. Im Graphentester kann man z.B, folgende Vereinbarung treffen:
-  * Knoten **Besucht**: In der ToDo-Liste, mit einem Entfernungswert versehen.
+  * Knoten **Markiert**: In der ToDo-Liste, mit einem Entfernungswert versehen.
-  * Knoten **Markiert**: In der Luft, Wert entspricht der kürzesten Entfernung vom Startknoten
+  * Knoten **Besucht**: In der Luft, Wert entspricht der kürzesten Entfernung vom Startknoten
-Damit sieht ein Lückenhafter Pseudocode so aus:
+Damit sieht ein lückenhafter Pseudocode so aus:
 <code>
-hole den startknoten, markiere in als besucht, füge ihn in die ToDo-liste ein.
+hole den startknoten, markiere ihn als markiert, füge ihn in die ToDo-liste ein.
 solange die ToDo-liste nicht leer ist:
@@ Zeile 80: / Zeile 79: @@
     wenn d < wert von n ODER n nicht in der ToDo-liste
-      // was muss dann geschehen
+      // was muss dann geschehen?
     wenn n nicht in der ToDo-Liste:
@@ Zeile 96: / Zeile 95: @@
 ++++ Lösungsvorschlag |
 <code>
-hole den startknoten, markiere in als besucht, füge ihn in die ToDo-liste ein.
+hole den startknoten, markiere in als markiert, trage als Entfernung 0 ein, füge ihn in die ToDo-liste ein.
 solange die ToDo-liste nicht leer ist:
   sortiere die ToDo-liste aufsteigend
   hole das kleinste element _aktuell_ aus der ToDo-liste
-  setze aktuell auf markiert
+  setze aktuell auf besucht
-  für alle nachbarn n von _aktuell_, die nicht markiert sind, wiederhole:
+  für alle nachbarn n von _aktuell_, die nicht besucht sind, wiederhole:
     berechne die entfernung d des knotens n vom startknoten aus über den knoten _aktuell_ // wert von aktuell + abstand zum nachbarn
@@ Zeile 110: / Zeile 109: @@
     wenn n nicht in der ToDo-Liste:
-      markiere n als besucht
+      markiere n als markiert
       fuege n der ToDo-liste hinzu
 </code>
+Tipp:
+  * Die Entfernung zwischen zwei Knoten ist das Gewicht der Kante. Du musst also zuerst die entsprechende Kante bekommen und kannst darauf die Methode ''getGewicht()'' aufrufen.
 ++++
 ----
@@ Zeile 120: / Zeile 123: @@
 === (A3) ===
-Implementiere den Dijkstra Algorithmus im Graphentester, so dass in jedem Knoten die Entfernung des kürzesten Wegs vom Startknoten zu allen anderen Knoten des Graphen steht.
+Implementiere den Dijkstra Algorithmus im Graphentester, so dass in jedem Knoten die Entfernung des kürzesten Wegs vom Startknoten zu allen anderen Knoten des Graphen steht. Beachte den Abschnitt zum Sortieren von Knoten/Kanten in der Hilfe zum Graphentester!
+<btn type="info">[[faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start|Hilfe Grafentester]]</btn>
 ----
@@ Zeile 126: / Zeile 131: @@
 === (A4) ===
-Erweitere deinen Algorithmus so, dass die kürzesten Pfade farblich hervorgehoben werden.((kante.setFarbe() ))
+Erweitere deinen Algorithmus so, dass die kürzesten Pfade farblich hervorgehoben werden.((kante.setMarkiert(true) ))
+__Achtung:__ Denke daran, dass die Distanzen mehrfach aktualisiert werden können und ein vorab "kürzester Weg" später vielleicht revidiert werden muss.
 ----
 {{:aufgabe.png?nolink  |}}
@@ Zeile 133: / Zeile 139: @@
 Passe den Algorithmus so an, dass man im Quelltext die Knotennummer des Zielknotens angeben kann, um eine Route vom gewählten Startknoten zum Zielknoten zu berechnen. Gib die Stationen der kürzesten Route aus. Das Bild unten zeigt die Nummerierung der Knoten im Beispiel.
+__Tipp:__ Eine //HashMap// kann sinnvoll sein, um einen Knoten und seinen Vorgänger-Knoten zu speichern. Mach dich kurz schlau im Internet, wie man diese nutzen kann. Alternativ geht z. B. auch ein zweidimensionales Knoten-Array...
 {{ :faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_dijkstra:knotennummern.png?500 |}}