Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
| talit:algorithmen [2024-06-03 05:46] – [Aufgabe 6: Pfadsuche mit BFS] 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 219: | Zeile 225: | ||
| * Funktioniert der Code auch, wenn sich die Zyklen überschneiden? | * Funktioniert der Code auch, wenn sich die Zyklen überschneiden? | ||
| - | < | + | < |
| ++++Lösung: | ++++Lösung: | ||
| <code python> | <code python> | ||
| Zeile 260: | 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 323: | Zeile 329: | ||
| * Entdeckte, aber noch nicht besuchte Knoten in einer Liste: `candidates = [start]` | * Entdeckte, aber noch nicht besuchte Knoten in einer Liste: `candidates = [start]` | ||
| * Noch unbekannte Knoten (brauchen wir uns nicht zu merken). | * Noch unbekannte Knoten (brauchen wir uns nicht zu merken). | ||
| - | * Jeweils | + | * Solange `candidates` nicht leer ist, wird der vorderste Knoten `node` in `candidates` entfernt. |
| * Falls `node` bereits in `visited` ist, gehen wir zum nächsten (er wurde mehrfach entdeckt über verschiedene Pfade). | * Falls `node` bereits in `visited` ist, gehen wir zum nächsten (er wurde mehrfach entdeckt über verschiedene Pfade). | ||
| * Andernfalls: | * Andernfalls: | ||
| * Falls `node == end` sind wir fertig. | * Falls `node == end` sind wir fertig. | ||
| - | * Alle Nachbarknoten, | + | * Alle Nachbarknoten |
| - | * Wiederholen. | + | |
| <nodisp 1> | <nodisp 1> | ||
| Zeile 369: | Zeile 374: | ||
| ++++ | ++++ | ||
| </ | </ | ||
| + | |||
| + | |||
| #### Aufgabe 6: Pfadsuche mit BFS | #### Aufgabe 6: Pfadsuche mit BFS | ||
| Zeile 380: | Zeile 387: | ||
| * Zusätzlich merken wir uns: | * Zusätzlich merken wir uns: | ||
| * alle besuchten Knoten (`visited`) | * alle besuchten Knoten (`visited`) | ||
| - | | + | |
| + | * Wir merken uns für jeden Knoten dessen ersten Vorgängerknoten, | ||
| ++++ | ++++ | ||
| Zeile 405: | Zeile 413: | ||
| } | } | ||
| return result | return result | ||
| - | + | ||
| - | from collections import deque | + | |
| def find_path_bfs(graph, | def find_path_bfs(graph, | ||
| """ | """ | ||
| - | | + | candidates = [start] |
| - | | + | visited = {start: None} |
| - | candidates.append(start) | + | |
| - | visited = {start} | + | |
| - | parent = {} | + | |
| while candidates: | while candidates: | ||
| - | next = candidates.popleft() | + | next = candidates.pop(0) |
| for neighbor in graph[next]: | for neighbor in graph[next]: | ||
| if neighbor not in visited: | if neighbor not in visited: | ||
| - | visited.add(neighbor) | + | visited[neighbor] = next |
| candidates.append(neighbor) | candidates.append(neighbor) | ||
| - | parent[neighbor] = next | ||
| if neighbor == end: | if neighbor == end: | ||
| - | return build_path_from_parents(graph, | + | return build_path_from_parents(graph, |
| return None # No path found | return None # No path found | ||
| </ | </ | ||
| Zeile 440: | Zeile 443: | ||
| {' | {' | ||
| </ | </ | ||
| + | |||
| #### Aufgabe 7: Real-World Beispiel | #### Aufgabe 7: Real-World Beispiel | ||
| Zeile 481: | Zeile 485: | ||
| Der Algorithmus basiert auf dem folgenden Prinzip: | Der Algorithmus basiert auf dem folgenden Prinzip: | ||
| - | * Die Kandidaten sind nach aufsteigender Distanz zum Startknoten sortiert. Für die effiziente Sortierung der Kandidaten benützen wir eine `PriorityQueue`. | + | * Die Kandidaten sind nach aufsteigender Distanz zum Startknoten sortiert. |
| + | * Hier liegt der Unterschied zu BFS: statt die neu-entdeckten Kandidaten einfach hinten einzureihen, | ||
| + | * Für die effiziente Sortierung der Kandidaten benützen wir eine [[wpde> | ||
| * Der vorderste Kandidat ist immer der nächste Knoten in aufsteigender Distanz von `start` her. | * Der vorderste Kandidat ist immer der nächste Knoten in aufsteigender Distanz von `start` her. | ||
| - | | + | |
| - | * Achtung: für alle weiteren Kandidaten stimmt die Sortierung noch nicht definitiv: möglicherweise gibt es einen kürzeren Pfad als den bekannten via einen weiter vorne liegenden Kandidaten! | + | * Achtung: für alle weiteren Kandidaten stimmt die Sortierung noch nicht definitiv: möglicherweise gibt es einen kürzeren Pfad als den bekannten via einen weiter vorne liegenden Kandidaten, dessen Nachbarn noch nicht bekannt sind! |
| <code python> | <code python> | ||
| Zeile 576: | Zeile 582: | ||
| ++++ | ++++ | ||
| </ | </ | ||
| + | ### Visualisierung | ||
| + | Mit Folium lassen sich die gefundenen Pfade hübsch visualiseren. Der Code für untenstehende Grafik findet sich auf [[https:// | ||
| + | |||
| + | <figure shortest_path> | ||
| + | {{: | ||
| + | </ | ||
hof