Wir wollen versuchen, die 3 erarbeiteten Algorithmen mit Python umzusetzen und auf zwei verschiedene Graphen anzuwenden, um Wege zwischen zwei Knoten zu finden.

Die Struktur des Graphen, sowie Daten der Knoten und Funktionen um die Wegfindung zu visualisieren sind in der Datei graph.py zusammengefasst. Wir können die Klasse Graph in unserem eigenen Skript importieren und verwenden.

# Die Klasse Graph

# Eigenschaften von Graph

openList
list von Node – Werte mit append hinzufügen, mit remove entfernen oder mit [] direkt auf einen bestimmten Eintrag zugreifen
Hier werden alle «entdeckten» Knoten gespeichert. Zu Beginn ist dies nur der Startknoten. Einer dieser Knoten wird für den nächsten Schritt besucht.
Knoten auf dieser Liste werden Gelb gezeichnet
closedList
list von Node – Werte mit append hinzufügen, mit remove entfernen oder mit [] direkt auf einen bestimmten Eintrag zugreifen
Hier werden alle «besuchten», resp. «definitiv abgeschlossenen» Knoten aufgelistet. Zu Beginn ist diese Liste leer
Knoten auf dieser Liste werden Rot gezeichnet
peers
dictionary: (key: Node, value: list von Node) – zugreifen mit graph.peers[node]
Hier werden die Kanten des Graphen gespeichert. Man kann für einen Knoten eine Liste aller mit ihm verbundenen Knoten abrufen.
startNode
Node – Dies ist der Startknoten der Suche
targetNode
Node – Dies ist der Endknoten der Suche
dist
list von list von int – abrufen mit graph.dist[node1][node2]
Stellt die Distanztabelle dar. Man kann die Distanz zwischen zwei Knoten abrufen, sofern diese durch eine Kante miteinander verbunden sind.
running
boolean – Standardmässig True, graph.running = False
Wenn das Ziel gefunden wurde, dann kann man den Wert auf False stellen
Wenn der Wert False ist, wird versucht ausgehend vom Zielknoten den gefundenen Weg grün darzustellen. Dazu muss aber Node.parent korrekt gesetzt sein

# Konstruktor von Graph

Graph(step)
erzeugt einen neuen Graph, registriert die übergebene Step-Funktion

# Methoden von Graph

loadGallenbach()
lädt Daten für den Graph dem Buch von Jens Gallenbach
loadDeutschland()
lädt Daten für den Graph um Würzburg herum
init()
fügt den Startknoten auf die openList
run()
startet das Programm: bei jedem Tastendruck wird step()aufgerufen und der Graph neu gezeichnet

# die Klasse Node

# Eigenschaften von Node

g
int – Distanz zum Startknoten, muss berechnet werden: z.B. node.g = node.g + dist[node][othernode]
h
int – Distanz Luftlinie zu Würzburg (fix eingetragen)
parent
Node – Vorgänger-Knoten, muss gesetzt werden. Wird verwendet um Weg zurück zu Startknoten zu finden: z.B. node.peer = parent

# Beispiel

  1. Graph importieren
  2. step() definieren
  3. Graph erzeugen
  4. Daten laden
  5. Graph initialisieren
  6. Programm starten
"""
Name: S. Forster
Datum: 21.2.2019
Beschreibung: Demo von Graph
"""

from graph import Graph


def step():
    """
        Schrittfunktion: Stellt ein einzelner Suchschritt dar.
        Muss beim Erzeugen des Graph-Objektes registriert werden.
        Wird dann bei jedem Tastendruck aufgerufen. 
    """
    print(str(graph.openList))
    node = graph.openList[0]
    for peer in graph.peers[node]:
        graph.openList.append(peer)
        dist = graph.dist[node][peer]
        peer.parent = node
        print(str(peer) + " hat eine Distanz von " + str(dist) + " von " + str(node))


graph = Graph(step)          # graph erzeugen und Schrittfunktion registrieren
graph.loadGallenbach()       # Daten laden. Alternative: graph.loadDeutschland()
#graph.startNode  = graph.w   # Startknoten vorbereiten
#graph.targetNode = graph.s   # Zielknotens vorbereiten
graph.init()                 # Startknoten auf openList
graph.run()                  # Loop starten
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Breitensuche

In jedem Schritt werden alle Nachbarknoten auf die Open-List gefügt, sofern sie nicht schon dort sind.

# Dijkstra

Der Dijkstra-Algorithmus kann als Verfeinerung der Breitensuche angeschaut werden. Wir müssen die folgenden Punkte umsetzen:

  1. Wir nehmen nicht einfach den ersten Knoten auf der Open-List, sondern den Knoten mit der kürzeren Distanz zum Startknoten
  2. Für jeden Peer müssen wir den Weg zum Startknoten berechnen.
  3. Ev. gibt es bereits einen Weg zum Peer. Dann müssen wir überprüfen, ob der neue Weg besser ist.
  4. Abbrechen dürfen wir erst, wenn wir sicher sind, dass es keinen schnelleren Weg zum Zielknoten gibt. Dies ist dann der Fall, wenn der nächst-beste Kandidat auf der openListe der Zielknoten ist.

# A-Stern

Der A-Stern unterscheidet sich vom Dijkstra nur noch durch die Heuristik, welche bei der Auswahl des nächstbesten Knotens berücksichtigt wird. Hier muss also nur eine klitzekleine Änderung geschehen: Der beste Knoten auf der Open-List ist nicht mehr derjenige mit dem besten g, sondern der mit dem besten f, wobei f = g + h.

Letzte Änderung: 12.1.2022, 14:23:45