Implementierung des Dijkstra-Algorithmus in Python
Ich habe Dijkstra's algorithmfür meine Forschung ein Wirtschaftsmodell mit Python implementiert . In meiner Forschung untersuche ich zwei Funktionen und die Unterschiede zwischen ihnen. Jede Funktion verwendet zwei Parameter als Eingabe: F(a,b)und Z(a,b).
Jede Zelle der Matrix ist definiert als: $$M[a][b]=|F(a,b)-Z(a,b)|$$
Der Zweck davon ist es, den Pfad der minimalen Differenz zwischen den Gleichungen zu finden, der für jede Eingabe korrekt ist a
Online-Implementierungen des Dijkstra-Algorithmus verwendeten alle gewichtete Kanten, während ich Scheitelpunkte gewichtet habe.
Pseudocode:
function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u: // only v that are still in Q
alt ← dist[u] + length(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]
Eingang:
- 2d Array, bei dem jeder Zellenwert sein Gewicht ist
- Quellentupel (x, y)
Ausgabe:
Abstandsmatrix, in der jede Zelle den Abstand von der Quelle zum Scheitelpunkt enthält (i, j)
prev-Matrix, in der jede Zelle ihre Eltern enthält. Durch Rückverfolgung von (98,98) kann ich den kürzesten Weg finden.
Implementierung:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
def dijkstra_get_min(Q, dist):
min = MAX_DISTANCE + 1
u = None
for vertex in Q:
if dist[vertex[0], vertex[1]] <= min:
min = dist[vertex[0], vertex[1]]
u = vertex
return u
def dijkstra(graph, src=(0, 0)):
dist = np.array([np.array([0 for x in RANGE_ARR], dtype=float) for y in RANGE_ARR])
prev = np.array([np.array([(0, 0) for x in RANGE_ARR], dtype='i,i') for y in RANGE_ARR])
Q = []
for i in RANGE_ARR_0:
for j in RANGE_ARR_0:
dist[i, j] = MAX_DISTANCE
prev[i, j] = (0, 0)
Q.append((i, j))
dist[0][0] = 0
while Q:
u = dijkstra_get_min(Q, dist)
Q.remove(u)
moves = [x for x in ( (u[0], u[1] + 1), (u[0] + 1, u[1]), (u[0] + 1, u[1] + 1) ) if x in Q]
for v in moves:
alt = dist[u[0]][u[1]] + graph[v[0]][v[1]]
if alt < dist[v[0]][v[1]]:
dist[v[0], v[1]] = alt
prev[v[0], v[1]] = u
return dist, prev
Irgendwelche Meinungen über seine Richtigkeit?
Antworten
Ihr Code sieht im Allgemeinen korrekt aus, ignoriert ihn jedoch srcund sucht nur in positiver Richtung. Darüber hinaus kann es erheblich bereinigt und optimiert werden.
Einige allgemeine Kommentare zuerst:
- Verwenden Sie vollständige Variablennamen im Code, die Bedeutung / Zweck ausdrücken. Die Verwendung aussagekräftiger Namen ist nicht mit erheblichen Kosten verbunden, kann jedoch die Verdauung von Code erheblich erleichtern.
- Beachten Sie die Funktionen und Standards der Host-Sprache. Vermeiden Sie die erneute Verwendung der Namen von Builtins (z. B.
min) und versuchen Sie, die Codierungsstilstandards einzuhalten . - Vermeiden Sie es, es
numpysei denn, Sie verwenden die integrierten Funktionen tatsächlich. Die Verwendungnumpy.arrayfür den direkten Zugriff ist normalerweise langsamer alslist/set/ ..., da Werte bei jedem Zugriff in vollständige Python-Objekte konvertiert werden.
Machen Sie keine Annahmen über die Funktionen Ihrer Daten. Vermeiden Sie insbesondere Folgendes:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Diese schlagen bei Diagrammen mit einem Abstand> 99999 oder mehr als 1000 Elementen fehl. Berechnen Sie sie entweder für Ihre Eingabe oder verwenden Sie echte Obergrenzen.
Da Zahlen ein genau definiertes "Maximum" haben, können wir dies sicher verwenden:
INFINITY = float('int')
Da die Eingabe grapheine nxn-Matrix ist, können wir nur ihre Größe abfragen.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Beginnen wir mit vertex in Q with min dist[u]/ dijkstra_get_min. Ihr Algorithmus ist korrekt, aber wir können ausnutzen, dass das in Python integrierte System minbereits benutzerdefinierte Gewichte zulässt. Das for vertex in Q:wird zum Hauptargument min, das if dist[vertex[0], vertex[1]] <= min:wird zum Gewicht key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
Der DijkstraAlgorithmus besteht aus zwei Teilen - Initialisierung und Suche. Ihr Code wird klarer, wenn wir diese beiden Teile teilen - Ihre Linie dist[0][0] = 0ist der Übergang von einem zum anderen.
def dijkstra(graph, src=(0, 0)):
# dist, prev, Q
distances, prev_nodes, unvisited = dijkstra_initial(len(graph))
# set starting point
distances[src[0]][src[1]] = 0
dijkstra_search(graph, distances, prev_nodes, unvisited)
return distances, prev_nodes
Der Zweck der Initialisierung besteht darin, dass jeder Punkt den gleichen Wert hat. Dies bedeutet, dass wir die Matrizen direkt mit ihrem Endwert erstellen können. Da der Algorithmus den "vorherigen Knoten" nicht verwendet , können wir ihn auch mit einem billigen Platzhalter initialisieren.
def dijkstra_initial(size):
distances = [[INFINITY] * size for _ in range(size)]
prev_nodes = [[None] * size for _ in range(size)]
unvisited = {(x, y) for x in range(size) for y in range(size)}
# dist, prev, Q
return distances, prev_nodes, unvisited
Anstatt besuchte Knoten als Liste ( [..., ...]) zu verfolgen, verwenden wir eine Menge ( {..., ...}). Ein Satz ist ungeordnet und unterstützt O (1) -Mitgliedschaftstests im Vergleich zu O (n) -Mitgliedschaftstests. Dies macht es besser geeignet für die Buchhaltung von besuchten / nicht besuchten Knoten.
Um die Grafik zu durchsuchen, werden wir die Nachbarn wiederholt besuchen. Dies ist ein wichtiger Teil, der leicht falsch gemacht werden kann. Wenn die Graph-Implementierung dies nicht bereitstellt, kann es sich lohnen, ihn explizit zu implementieren.
def neighbours(node):
x, y = node
return [
(x + x_offset, y + y_offset)
for x_offset in (-1, 0, 1)
for y_offset in (-1, 0, 1)
if not (x_offset == y_offset == 0) # reject node itself
]
Der Kern des Algorithmus bleibt logisch derselbe: Wir passen einige Namen an, um mehr zu sprechen (z. B. u-> node, v-> neighbour). Wir verwenden den vorbereiteten neighboursanstelle des langen Ausdrucks.
def dijkstra_search(graph, distances, prev_nodes, unvisited):
while unvisited:
node = dijkstra_get_min(unvisited, dist)
unvisited.remove(node)
for neighbour in neighbours(node):
if neighbour not in unvisited:
continue
alt = distances[node[0]][node[1]] + graph[neighbour[0]][neighbour[1]]
if alt < distances[neighbour[0]][neighbour[1]]:
distances[neighbour[0]][neighbour[1]] = alt
prev_nodes[neighbour[0]][neighbour[1]] = node
Zu diesem Zeitpunkt sollte der Code sowohl schneller als auch einfacher zu warten sein. Der auffälligste Fehler, den wir noch haben, ist der explizite Umgang mit Dimensionen. Anstatt manuell auf jede Dimension zuzugreifen, wäre es besser, wenn wir direkt auf Punkte zugreifen könnten.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Dies kann "behoben" werden, indem Wörterbücher ( {point: value, ...}) anstelle von verschachtelten Listen ( [[value, ...], ...]) verwendet werden. Ein unmittelbarer Nachteil ist, dass dies der Einfachheit halber den Speicher austauscht.
Es kann jedoch verwendet werden, um die Speichernutzung tatsächlich zu reduzieren - Wörterbücher können von Natur aus spärlich sein, sodass wir einfach keine unbestimmten Felder speichern können. Da jeder besuchte Knoten für Entfernungen irrelevant wird, können wir sogar distancesKnoten entfernen, die bereits verarbeitet wurden.
[x for x in range(1, 1001)]kann als gerecht geschrieben werden list(range(1, 1001)).
Es wäre gut, dem auch 1001einen Namen zu geben.
Ebenso [0 for x in RANGE_ARR]kann geschrieben werden als [0] * len(RANGE_ARR). Durch Multiplizieren eines beliebigen Sequenztyps mit einer Ganzzahl werden die Elemente innerhalb der Sequenz wiederholt. Als Bonus ist es nach einem schnellen Benchmarking, das ich gerade durchgeführt habe, auch mehr als zehnmal schneller:
from timeit import timeit
N = int(1e6)
TRIALS = int(1e3)
print(timeit(lambda: [0] * N, number=TRIALS), "seconds")
print(timeit(lambda: [0 for x in range(N)], number=TRIALS), "seconds")
2.9889957 seconds
38.1463017 seconds
Beachten Sie jedoch, dass Sie dies nicht verwenden sollten, wenn der Elementtyp veränderbar ist (wie [[0]] * 5). Durch Multiplizieren einer Sequenz werden mehrere Verweise auf dasselbe Objekt erstellt. Es werden keine Kopien erstellt.
Es sieht so aus, als Qsollte es ein Set sein. Die Reihenfolge ist Ihnen egal, und Sie verwenden sie nur, um die Mitgliedschaft in einem Set zu verfolgen. Sets werden hier deutlich schneller sein. Die einzigen zwei erforderlichen Änderungen sind:
Q = set()
. . .
Q.add((i, j))
Die einzige Änderung, die ich sehen kann, hängt dijkstra_get_mintechnisch von der Reihenfolge ab Q. Wenn sich zwei Elemente mit denselben Mindestwerten in Q befinden, wählt Ihr Algorithmus die letzte Instanz aus. Da Mengen möglicherweise eine andere Reihenfolge verwenden, kann dies die Rückgabe des Scheitelpunkts ändern.
Es sieht so aus, als ob MAX_DISTANCEes sich um eine beliebig große Zahl handeln soll, bei der alles andere kleiner sein wird. Vielleicht möchten Sie es dafür versuchen np.inf. Wenn Sie die Obergrenze fest codieren, riskieren Sie, dass das Problem später "wächst" und möglicherweise dieses Maximum überschreitet. fehlerhaftes Verhalten verursachen.