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.

"""
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]     # bester Knoten suchen auf openlist
    for candidate in graph.openList:
        if node.g + node.h > candidate.g + candidate.h:
            node = candidate

    if node == graph.targetNode:
        graph.running = False
    else:
        for peer in graph.peers[node]:
            if peer not in graph.closedList:
                g = node.g + graph.dist[node][peer]
                if peer in graph.openList:
                    if g < peer.g:
                        peer.parent = node
                        peer.g = g
                else:
                    graph.openList.append(peer)        
                    peer.parent = node
                    peer.g = g

        graph.closedList.append(node)
        graph.openList.remove(node)

graph = Graph(step)          # graph erzeugen und Schritt-funktion registrieren
graph.loadDeutschland()      # Daten laden. Alternative: graph.loadDeutschland()
graph.init()                 # startknoten auf openList
graph.run()                  # starten