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

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.