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 13:18] – [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 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 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