Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
| talit:algorithmen [2025-03-02 19:33] – [Dijkstra - Kürzeste Pfade] hof | talit:algorithmen [2025-03-03 21:01] (aktuell) – [Aufgabe 4 - Graph Walk] hof | ||
|---|---|---|---|
| Zeile 16: | Zeile 16: | ||
| Wie könnten wir das Weg-Problem (von der KSR an den Bahnhof) abstrakt erfassen? Wir könnten die verschiedenen Wege zum Beispiel so erfassen: | Wie könnten wir das Weg-Problem (von der KSR an den Bahnhof) abstrakt erfassen? Wir könnten die verschiedenen Wege zum Beispiel so erfassen: | ||
| + | <figure graph_romis> | ||
| {{: | {{: | ||
| + | < | ||
| + | </ | ||
| Aus was besteht ein Graph? Aus **Knoten** (en. _nodes_ oder _vertices_) und **Kanten** (_edges_). In unserem Fall haben die Kanten **Gewichte**, | Aus was besteht ein Graph? Aus **Knoten** (en. _nodes_ oder _vertices_) und **Kanten** (_edges_). In unserem Fall haben die Kanten **Gewichte**, | ||
| - | Wie könnten wir diesen Graphen in Python repräsentieren | + | Wie könnten wir diesen Graphen in Python repräsentieren? |
| - | ? | + | |
| #### Adjazenzmatrix | #### Adjazenzmatrix | ||
| Zeile 110: | Zeile 113: | ||
| </ | </ | ||
| ++++ | ++++ | ||
| - | |||
| ### Tiefensuche | ### Tiefensuche | ||
| Bevor wir den schnellsten Weg an den Bahnhof zu finden versuchen, wären wir schon mal nur froh, überhaupt einen Weg zu finden. Es könnte ja auch sein, dass wir uns in die Turnhalle begeben, von wo kein Weg zum Bahnhof führt. Oder dass wir von der Bahnhofstrasse zurück zur KSR gelangen: | Bevor wir den schnellsten Weg an den Bahnhof zu finden versuchen, wären wir schon mal nur froh, überhaupt einen Weg zu finden. Es könnte ja auch sein, dass wir uns in die Turnhalle begeben, von wo kein Weg zum Bahnhof führt. Oder dass wir von der Bahnhofstrasse zurück zur KSR gelangen: | ||
| + | |||
| + | <figure graph_romis2> | ||
| + | [[http:// | ||
| + | < | ||
| + | </ | ||
| - | [[http:// | ||
| #### Aufgabe 2 | #### Aufgabe 2 | ||
| Zeile 254: | Zeile 260: | ||
| ++++ | ++++ | ||
| </ | </ | ||
| - | |||
| #### Aufgabe 4 - Graph Walk | #### Aufgabe 4 - Graph Walk | ||
| Zeile 261: | Zeile 266: | ||
| **Aufgabe**: | **Aufgabe**: | ||
| * Die Ausgabe kann mit `print()` erfolgen oder eine Liste zurückgeben. | * Die Ausgabe kann mit `print()` erfolgen oder eine Liste zurückgeben. | ||
| - | * Herausforderung: | + | * Herausforderung: |
| <nodisp 1> | <nodisp 1> | ||
| Zeile 469: | Zeile 474: | ||
| - Was hat es mit der Rekursionstiefe auf sich? | - Was hat es mit der Rekursionstiefe auf sich? | ||
| - Der BFS-Pfad ist deutlich besser - BFS findet nämlich den Pfad mit den wenigsten Segmenten. Aber ist das bereits der schnellste Pfad? | - Der BFS-Pfad ist deutlich besser - BFS findet nämlich den Pfad mit den wenigsten Segmenten. Aber ist das bereits der schnellste Pfad? | ||
| + | |||
| ### Dijkstra - Kürzeste Pfade | ### Dijkstra - Kürzeste Pfade | ||
| Zeile 576: | Zeile 582: | ||
| ++++ | ++++ | ||
| </ | </ | ||
| - | + | ### Visualisierung | |
| - | #### Visualisierung | + | |
| Mit Folium lassen sich die gefundenen Pfade hübsch visualiseren. Der Code für untenstehende Grafik findet sich auf [[https:// | Mit Folium lassen sich die gefundenen Pfade hübsch visualiseren. Der Code für untenstehende Grafik findet sich auf [[https:// | ||
| <figure shortest_path> | <figure shortest_path> | ||
| - | {{: | + | {{: |
| </ | </ | ||
hof