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:51] – 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 308: | Zeile 313: | ||
| Mit der Tiefensuche finden wir Pfade von A nach B in einem Graphen, aber vielleicht nehmen wir dabei grosse Umwege in Kauf, weil wir zuerst weit von A entfernte Knoten besuchen, bevor wir alle Nachbarn von A untersuchen. Wir möchten aber eine Möglichkeit haben, den Graphen *der Nähe nach* zu besuchen, also die Knoten in aufsteigender Distanz von A zu besuchen. Dieses Verfahren heisst **Breitensuche** (*Breadth First Search* - BFS). | Mit der Tiefensuche finden wir Pfade von A nach B in einem Graphen, aber vielleicht nehmen wir dabei grosse Umwege in Kauf, weil wir zuerst weit von A entfernte Knoten besuchen, bevor wir alle Nachbarn von A untersuchen. Wir möchten aber eine Möglichkeit haben, den Graphen *der Nähe nach* zu besuchen, also die Knoten in aufsteigender Distanz von A zu besuchen. Dieses Verfahren heisst **Breitensuche** (*Breadth First Search* - BFS). | ||
| - | |||
| #### Aufgabe 5 | #### Aufgabe 5 | ||
| Überlege dir, wie du vorgehen könntest, um zuerst die unmittelbaren Knoten des Starts zu besuchen, und nur allmählich weitere Kanten zu traversieren. Ignoriere die Kantengewichte dabei erst mal - du kannst von einem ungewichteten Graphen ausgehen. | Überlege dir, wie du vorgehen könntest, um zuerst die unmittelbaren Knoten des Starts zu besuchen, und nur allmählich weitere Kanten zu traversieren. Ignoriere die Kantengewichte dabei erst mal - du kannst von einem ungewichteten Graphen ausgehen. | ||
| Zeile 325: | 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). | ||
| - | * Solange `candidates` nicht leer ist, wird der vorderste Knoten `node` in `candidates` | + | * 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: | ||
| Zeile 370: | Zeile 374: | ||
| ++++ | ++++ | ||
| </ | </ | ||
| + | |||
| #### Aufgabe 6: Pfadsuche mit BFS | #### Aufgabe 6: Pfadsuche mit BFS | ||
| Zeile 382: | 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 407: | 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 484: | 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 579: | 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