A Star in Python

Gepostet: , Zuletzt aktualisiert:

def a_star(graph, heuristic, start, goal):
    """
    Finds the shortest distance between two nodes using the A-star (A*) algorithm
    :param graph: an adjacency-matrix-representation of the graph where (x,y) is the weight of the edge or 0 if there is no edge.
    :param heuristic: an estimation of distance from node x to y that is guaranteed to be lower than the actual distance. E.g. straight-line distance
    :param start: the node to start from.
    :param goal: the node we're searching for
    :return: The shortest distance to the goal node. Can be easily modified to return the path.
    """

    # This contains the distances from the start node to all other nodes, initialized with a distance of "Infinity"
    distances = [float("inf")] * len(graph)

    # The distance from the start node to itself is of course 0
    distances[start] = 0

    # This contains the priorities with which to visit the nodes, calculated using the heuristic.
    priorities = [float("inf")] * len(graph)

    # start node has a priority equal to straight line distance to goal. It will be the first to be expanded.
    priorities[start] = heuristic[start][goal]

    # This contains whether a node was already visited
    visited = [False] * len(graph)

    # While there are nodes left to visit...
    while True:
        # ... find the node with the currently lowest priority...
        lowest_priority = float("inf")
        lowest_priority_index = -1
        for i in range(len(priorities)):
            # ... by going through all nodes that haven't been visited yet
            if priorities[i] < lowest_priority and not visited[i]:
                lowest_priority = priorities[i]
                lowest_priority_index = i

        if lowest_priority_index == -1:
            # There was no node not yet visited --> Node not found
            return -1

        elif lowest_priority_index == goal:
            # Goal node found
            # print("Goal node found!")
            return distances[lowest_priority_index]

        # print("Visiting node " + lowestPriorityIndex + " with currently lowest priority of " + lowestPriority)

        # ...then, for all neighboring nodes that haven't been visited yet....
        for i in range(len(graph[lowest_priority_index])):
            if graph[lowest_priority_index][i] != 0 and not visited[i]:
                # ...if the path over this edge is shorter...
                if distances[lowest_priority_index] + graph[lowest_priority_index][i] < distances[i]:
                    # ...save this path as new shortest path
                    distances[i] = distances[lowest_priority_index] + graph[lowest_priority_index][i]
                    # ...and set the priority with which we should continue with this node
                    priorities[i] = distances[i] + heuristic[i][goal]
                    # print("Updating distance of node " + i + " to " + distances[i] + " and priority to " + priorities[i])

                # Lastly, note that we are finished with this node.
                visited[lowest_priority_index] = True
                # print("Visited nodes: " + visited)
                # print("Currently lowest distances: " + distances)

Über den Algorithmus und die Programmiersprache in diesem Snippet:

A Star

Der A-Stern-Algorithmus (A & ast;) ist ein Algorithmus, der verwendet wird, um das Problem des kürzesten Pfades in einem Graphen zu lösen. Dies bedeutet, dass bei einer Anzahl von Knoten und den Kanten zwischen ihnen sowie der “Länge” der Kanten (als “Gewicht” bezeichnet) und einer Heuristik (dazu später mehr) die A & ast; Der Algorithmus findet den kürzesten Weg vom angegebenen Startknoten zu allen anderen Knoten.

Beschreibung des Algorithmus

Das Grundprinzip des A-Stern-Algorithmus (A & ast;) besteht darin, den Knoten mit der aktuell kleinsten Priorität (der kürzesten Entfernung vom Start plus der Heuristik zum Ziel) iterativ zu betrachten und alle noch nicht besuchten Nachbarn zu aktualisieren, wenn der Pfad dazu über ist der aktuelle Knoten kürzer. Dies ist dem Dijkstra-Algorithmus sehr ähnlich, mit dem Unterschied, dass der Knoten mit der niedrigsten Priorität als nächstes besucht wird und nicht der Knoten mit der kürzesten Entfernung. Im Wesentlichen verwendet Dijkstra die Entfernung als Priorität, während A & ast; verwendet den Abstand plus der Heuristik.

Warum ist das Hinzufügen der Heuristik sinnvoll? Ohne sie hat der Algorithmus keine Ahnung, ob er in die richtige Richtung geht. Bei der manuellen Suche nach dem kürzesten Pfad in diesem Beispiel haben Sie wahrscheinlich Pfade nach rechts gegenüber Pfaden nach oben oder unten priorisiert. Dies liegt daran, dass sich der Zielknoten rechts vom Startknoten befindet, sodass das Gehen nach rechts zumindest im Allgemeinen die richtige Richtung ist. Die Heuristik gibt dem Algorithmus diese räumlichen Informationen.

Wenn also ein Knoten die derzeit kürzeste Entfernung hat, aber im Allgemeinen in die falsche Richtung geht, während Dijkstra diesen Knoten als nächstes besucht hätte, wird A Star dies nicht tun. Damit dies funktioniert, muss die Heuristik zulässig sein, was bedeutet, dass sie die tatsächlichen Kosten (d. H. Die Entfernung) niemals überschätzen darf - was beispielsweise für die geradlinige Entfernung in Straßennetzen der Fall ist. Intuitiv übersieht der Algorithmus auf diese Weise niemals einen kürzeren Pfad, da die Priorität immer niedriger als die tatsächliche Entfernung ist (Wenn der aktuell kürzeste Pfad A ist, wird Pfad B untersucht, wenn er auf irgendeine Weise kürzer sein könnte.) Eine einfache Heuristik, die diese Eigenschaft erfüllt, ist die geradlinige Entfernung (z. B. in einem Straßennetz).

Im Einzelnen führt dies zu den folgenden Schritten:

  1. Initialisieren Sie den Abstand zum Startknoten als 0 und den Abstand zu allen anderen Knoten als unendlich
  2. Initialisieren Sie die Priorität zum Startknoten als geradlinigen Abstand zum Ziel und die Prioritäten aller anderen Knoten als unendlich
  3. Setzen Sie alle Knoten auf “nicht besucht”.
  4. Während wir nicht alle Knoten besucht und den Zielknoten nicht gefunden haben:     1. Suchen Sie den Knoten mit der aktuell niedrigsten Priorität (beim ersten Durchgang ist dies der Quellknoten selbst).     1. Wenn es sich um den Zielknoten handelt, geben Sie dessen Entfernung zurück     1. Überprüfen Sie für alle Knoten daneben, die wir noch nicht besucht haben, ob die derzeit kleinste Entfernung zu diesem Nachbarn größer ist, als wenn wir über den aktuellen Knoten gehen würden     1. Wenn dies der Fall ist, aktualisieren Sie die kleinste Entfernung dieses Nachbarn auf die Entfernung von der Quelle zum aktuellen Knoten plus die Entfernung vom aktuellen Knoten zu diesem Nachbarn und aktualisieren Sie die Priorität auf die Entfernung plus die geradlinige Entfernung zu der Zielknoten

Beispiel des Algorithmus

Betrachten Sie das folgende Diagramm: Grafik für den A-Star-Algorithmus (A & ast;) für kürzeste Wege

Die Schritte, die der Algorithmus in diesem Diagramm ausführt, wenn Knoten 0 als Startpunkt und Knoten 5 als Ziel in der angegebenen Reihenfolge angegeben werden, sind:

  1. Besuch des Knotens 0 mit der derzeit niedrigsten Priorität von 8,0
  2. Aktualisieren der Entfernung von Knoten 1 bis 3 und der Priorität auf 9.32455532033676
  3. Aktualisieren der Entfernung von Knoten 2 bis 4 und der Priorität auf 10.32455532033676
  4. Besuch von Knoten 1 mit der derzeit niedrigsten Priorität von 9.32455532033676
  5. Aktualisieren der Entfernung von Knoten 3 auf 9 und der Priorität auf 11.82842712474619
  6. Aktualisieren der Entfernung von Knoten 4 auf 13 und der Priorität auf 15.82842712474619
  7. Besuch von Knoten 2 mit der derzeit niedrigsten Priorität von 10.32455532033676
  8. Besuch von Knoten 3 mit der derzeit niedrigsten Priorität von 11.82842712474619
  9. Aktualisieren der Entfernung von Knoten 5 auf 12 und der Priorität auf 12.0
  10. Zielknoten gefunden!

Endgültig niedrigster Abstand von Knoten 0 zu Knoten 5: 12

Laufzeit des Algorithmus

Die Laufzeitkomplexität von A Star hängt davon ab, wie es implementiert wird. Wenn ein Min-Heap verwendet wird, um den nächsten zu besuchenden Knoten zu bestimmen, und die Adjazenz unter Verwendung von Adjazenzlisten implementiert wird, ist die Laufzeit O(| E | + | V | log | V|) (|V| = Nummer Anzahl der Knoten, |E| = Anzahl der Kanten). Wenn wir einfach alle Entfernungen durchsuchen, um den Knoten mit der niedrigsten Entfernung in jedem Schritt zu finden, und mithilfe einer Matrix nachsehen, ob zwei Knoten benachbart sind, steigt die Laufzeitkomplexität auf O(| V | ^ 2).

Beachten Sie, dass dies dasselbe ist wie bei Dijkstra. In der Praxis können jedoch bei Auswahl einer guten Heuristik viele der Pfade eliminiert werden, bevor sie untersucht werden, was zu einer signifikanten Zeitverbesserung führt.

Weitere Informationen darüber, wie die Heuristik die Komplexität beeinflusst, finden Sie im Wikipedia-Artikel.

Speicherkomplexität des Algorithmus

Die Speicherplatzkomplexität von A Star hängt davon ab, wie es ebenfalls implementiert ist, und entspricht der Laufzeitkomplexität sowie dem für die Heuristik erforderlichen Speicherplatz.

Python

Das Python-Logo

Python™ ist eine interpretierte Sprache, die für viele Zwecke verwendet wird, von der eingebetteten Programmierung bis zur Webentwicklung, wobei einer der größten Anwendungsfälle die Datenwissenschaft ist.

In Python zu “Hello World”

Das Wichtigste zuerst - so können Sie Ihre erste Codezeile in Python ausführen:

  1. Laden Sie die neueste Version von Python von python.org herunter und installieren Sie sie. Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert. Viele Technologien erfordern dies aufgrund der mit Python 3 eingeführten Änderungen weiterhin.
  2. Öffnen Sie ein Terminal, stellen Sie sicher, dass der Befehl “python” oder “python3” funktioniert und dass der Befehl, den Sie verwenden, sich auf die Version bezieht, die Sie gerade installiert haben, indem Sie “python3 —version” oder “python —version” ausführen. Wenn der Fehler “Befehl nicht gefunden” (oder ähnliches) angezeigt wird, starten Sie die Befehlszeile, und, falls dies nicht hilft, Ihren Computer neu. Wenn das Problem weiterhin besteht, finden Sie hier einige hilfreiche Fragen zu StackOverflow für Windows, Mac und Linux.
  3. Sobald dies funktioniert, können Sie das folgende Snippet ausführen: print("Hello World"). Sie haben zwei Möglichkeiten, dies auszuführen: 3.1 Führen Sie “python” in der Befehlszeile aus, fügen Sie einfach das Code-Snippet ein und drücken Sie die Eingabetaste (Drücken Sie “STRG + D” oder schreiben Sie “exit ()” und drücken Sie die Eingabetaste, um das Programm zu beenden). 3.2 Speichern Sie das Snippet in einer Datei und nennen Sie es etwas, das mit “.py” endet, z.B. hello_world.py und führepython path / to / hello_world.py aus. Tipp: Verwenden Sie den Befehl ls (dir in Windows), um herauszufinden, welche Dateien sich in dem Ordner befinden, in dem sich Ihre Befehlszeile gerade befindet.

Das wars schon! Beachten Sie, dass das Drucken von etwas auf die Konsole in Python nur eine einzige Zeile ist - diese niedrige Eintrittsbarriere und das Fehlen von erforderlichem Boilerplate-Code machen einen großen Teil der Attraktivität von Python aus.

Grundlagen in Python

Um in Python implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen.

Variablen und Arithmetik

Variablen in Python sind wirklich einfach. Sie müssen weder einen Datentyp deklarieren noch deklarieren, dass Sie eine Variable definieren. Python weiß das implizit.

a = 1
b = {'c':2}

print(a + b['c']) # prints 3

Arrays

Das Arbeiten mit Arrays ist in Python ähnlich einfach:

arr = ["Hello", "World"]

print(arr[0]) # Hello
print(arr[1]) # World
# print(arr[2]) # IndexError

arr.append("!")

print(arr[2]) # !

Wie diejenigen von Ihnen, die mit anderen Programmiersprachen wie Java vertraut sind, möglicherweise bereits bemerkt haben, handelt es sich nicht um native Arrays, sondern um Listen, die wie Arrays gekleidet sind. Dies wird durch die Tatsache deutlich, dass keine Größe angegeben werden muss und Elemente nach Belieben angehängt werden können. Tatsächlich druckt print (type (arr)) <class ‘list’> `. Dies bedeutet, dass Arrays in Python erheblich langsamer sind als in Programmiersprachen niedrigerer Ebene. Es gibt jedoch Pakete wie numpy, die echte Arrays implementieren, die erheblich schneller sind.

Bedingungen

Wie die meisten Programmiersprachen kann Python “if-else”-Anweisungen ausführen:

value = 1
if value==1:
    print("Value is 1")
elif value==2:
    print("Value is 2")
else:
    print("Value is something else")

Python hat jedoch keine “case”-Anweisungen, die andere Sprachen wie Java haben. Meiner Meinung nach kann dies durch die Einfachheit der “if”-Anweisungen entschuldigt werden, die den “syntaktischen Zucker” von “case” -Anweisungen überflüssig machen.

Schleifen

Python unterstützt sowohl “for” - als auch “while” -Schleifen sowie “break” - und “continue” -Anweisungen. Es gibt zwar keine “do-while” -Schleifen, aber eine Reihe von integrierten Funktionen, die das Schleifen sehr bequem machen, wie “enumerate” oder “range”. Hier sind einige Beispiele:

value = 10
while value > 0:
    print(value)
    value -= 1

for index, character in enumerate("banana"):
    print("The %d-th letter is a %s" % (index + 1, character))

Beachten Sie, dass Python nicht die gemeinsame Iteratorvariablensyntax anderer Sprachen verwendet (z. B. for (int i = 0; i <arr.length; i ++) in Java) - hierfür kann die Funktion enumerate verwendet werden.

Funktionen

Funktionen in Python sind einfach zu definieren und erfordern zum Guten oder Schlechten keine Angabe von Rückgabe- oder Argumenttypen. Optional kann ein Standardwert für Argumente angegeben werden:

def print_something(something="Hello World"):
    print(something)
    return "Success"

print_something()
print(print_something("banana"))

 (Dies druckt “Hallo Welt”, “Banane” und dann “Erfolg”)

Syntax

Sie haben vielleicht bemerkt, dass Python keine geschweiften Klammern ({}) verwendet, um Codeblöcke in Bedingungen, Schleifen, Funktionen usw. zu umgeben. Dies liegt daran, dass Python als Teil seiner Syntax von Einrückungen (Leerzeichen) abhängt. Während Sie in Java beliebig viele Leerzeichen (Leerzeichen, Tabulatoren, Zeilenumbrüche) hinzufügen und löschen können, ohne das Programm zu ändern, wird die Syntax in Python dadurch unterbrochen. Dies bedeutet auch, dass keine Semikolons erforderlich sind, was in anderen Sprachen ein häufiger Syntaxfehler ist.

Fortgeschrittene Kenntnisse in Python

Python wurde erstmals 1990 veröffentlicht und ist ein Multi-Paradigma. Das bedeutet, dass es in erster Linie zwingend und funktional ist, aber auch objektorientierte und reflektierende Elemente enthält. Es ist dynamisch typisiert, bietet jedoch seit Version 3.5 Syntax für die schrittweise Eingabe. Für weitere Informationen hat Python einen großartigen Artikel Wikipedia.