[PYTHON] Dikstra-Algorithmus für Anfänger
Gibt es keinen Dyxtra-Algorithmus? Es ist schwer, sich an den Namen zu erinnern, und es ist unwahrscheinlich, dass Sie ihn in der Praxis implementieren, z. B. das Problem der kürzesten Route für gewichtete Diagramme, sodass Sie ihn sofort vergessen. .. ..
Was ist der Dyxtra-Algorithmus?
Der Dyxtra-Algorithmus ist ein Algorithmus, der den kürzesten Pfad eines Graphen findet. Ich denke, viele Leute haben nur den Namen gehört. Es ist leicht und einfach zu machen, aber es ist ein wenig schwer zu erreichen, aber es ist ein relativ leicht verständlicher Algorithmus, wenn Sie jeden einzelnen verstehen. Ungewichtete Labyrinthsuchen usw. können durch die Suche nach Breitenpriorität gelöst werden. Wenn jedoch jede Seite gewichtet ist, müssen Sie schließlich alle Straßen berechnen. Angenommen, alle Eckpunkte werden nur einmal übergeben, wenn es E-Seiten gibt, ist es O (E!) Und der Rechenaufwand explodiert. Es ist etwas schwierig, dies zu berechnen.
Der Dyxtra-Algorithmus ist ein Algorithmus, der solche Probleme effizient löst.
Übrigens müssen die Kosten jeder Seite ein nicht negativer Wert sein (0 oder mehr). Wenn eine negative Zahl enthalten ist, wird die Bellman-Ford-Methode usw. verwendet.
Verfahren
Das Verfahren für die Dyxtra-Methode ist ziemlich einfach.
- Stellen Sie den kürzesten Abstand 0 als Startpunkt ein
- Gehen Sie zu der kürzesten bekannten Entfernung von den Punkten, die Sie noch nicht verfolgt haben
- Stellen Sie den kürzesten Abstand zwischen den mit diesem Scheitelpunkt verbundenen Scheitelpunkten ein. Wenn zu diesem Zeitpunkt der kürzeste Abstand des Scheitelpunkts aktualisiert werden kann, aktualisieren Sie ihn.
- Tun Sie dies, bis Sie den kürzesten Abstand aller Scheitelpunkte kennen
Nun, ich denke, es ist etwas schwierig zu sagen, also lasst uns ein Beispiel sehen.
Beispiel
Es ist eine analoge Methode, aber ich konnte sie am meisten ausdrücken. .. ..
Betrachten Sie den kürzesten Weg in der folgenden Abbildung.
Grün ist der kürzeste Weg und wird die Spitze der Bewegung sein. Rot ist der Ausgangspunkt. Die Zahl an jedem Scheitelpunkt ist zu diesem Zeitpunkt der kürzeste Weg
Wie Sie sehen können, können Sie sehen, dass es sich an dieser Stelle vom Startpunkt zum kürzesten Scheitelpunkt bewegt und dann den kürzesten Pfad des benachbarten Scheitelpunkts berechnet.
Implementierung
Kommen wir nun zur Implementierung. Lassen Sie uns das obige Verfahren auf einfache Weise implementieren.
function main(nodes) {
const start = nodes[0]
//Nehmen Sie die besuchten Spitzen auf
const visited = new Set()
const routesFromStart = new Map()
//Notieren Sie die Entfernung vom Startpunkt
routesFromStart.set(start, {distance: 0})
for(const n of nodes) {
if(n != start) {
//Ersetzen Sie alle Eckpunkte mit Ausnahme von start durch unendlich
routesFromStart.set(n, {distance: Number.MAX_VALUE})
}
}
let current = start
let routes = new Map()
while(current != null) {
visited.add(current)
for(const edge of current.edges) {
//Berechnen Sie den kürzesten Abstand zwischen benachbarten Scheitelpunkten von diesem Scheitelpunkt und aktualisieren Sie ihn, wenn er niedriger als der berechnete Wert ist
if(edge.cost + routesFromStart.get(current).distance < routesFromStart.get(edge.to).distance) {
routesFromStart.set(edge.to, {distance: edge.cost + routesFromStart.get(current).distance})
routes.set(current, edge.to)
}
}
let cheapestNodeDistance = Number.MAX_VALUE
current = null
//Wählen Sie den kleinsten Scheitelpunkt aus den berechneten Scheitelpunkten für die kürzeste nicht besuchte Entfernung aus
for(const city of routesFromStart.keys()) {
if(!visited.has(city) && cheapestNodeDistance > routesFromStart.get(city).distance){
cheapestNodeDistance = routesFromStart.get(city).distance
current = city
}
}
}
return routesFromStart.get(nodes[nodes.length - 1]).distance
}
Unter der Annahme, dass jeder Scheitelpunkt V ist, dreht dieser Code eine Schleife zum Auswählen des kleinsten Scheitelpunkts in der Schleife, der maximal um die Anzahl jeder Seite verläuft, sodass der Berechnungsbetrag für jeden Speicher O (V ^ 2 + E) beträgt. Es ist O (V), weil die Peaks aufgezeichnet werden müssen.
Informationen zur Implementierung mithilfe der Prioritätswarteschlange
Wie Sie vielleicht bemerkt haben, können Sie mit diesem Code die Logik optimieren, die die kleinsten Eckpunkte bestimmt. Das ist die Prioritätswarteschlange. Prioritätswarteschlangen erfordern eine O (logN) -Berechnung zum Einfügen und Abrufen, aber die Berechnung zum Bestimmen der kleinsten Scheitelpunkte ist schneller als eine lineare Suche.
Die Prioritätswarteschlange ist in JavaScript nicht standardmäßig implementiert, daher ist sie in Python implementiert.
def dijkstra(nodes):
start_node = nodes[0]
routes_from_start = {n: math.inf for n in nodes}
#Setzen Sie Null auf den ersten Scheitelpunkt
routes_from_start[start_node] = 0
minHeap = []
#Fügen Sie den ersten Scheitelpunkt hinzu
heappush(minHeap, (0, start_node))
#Suchen Sie, bis der Heap leer ist
while minHeap:
(cost, current_node) = heappop(minHeap)
#Da der Prioritätsschlüssel doppelt vorhanden ist, überprüfen Sie dies hier
if cost > routes_from_start[current_node]:
continue
for node in current_node.routes:
price_info = current_node.routes[node]
if routes_from_start[node] > price_info + routes_from_start[current_node]:
routes_from_start[node] = price_info + routes_from_start[current_node]
#Mehrwert für die Priorität bei Aktualisierung
heappush(minHeap, (price_info + routes_from_start[current_node], node))
return routes_from_start[nodes[-1]]
Lassen Sie uns eine weitere Gelegenheit nutzen, um die Prioritätswarteschlange zu erläutern. Wenn die Berechnungseffizienz besser ist und jeder Scheitelpunkt V ist und jede Seite V ist, werden O (V), das V auf Abbildung und Heap setzt, für die Häufigkeit von E betrieben, also O (ElogE). Sie können sehen, dass es durch die Summe O (V + ElogE) von berechnet werden kann. Dies ist effizienter als der erste Algorithmus.
Erinnere dich an die Route
Jetzt kenne ich die kürzesten Kosten. Dieses Problem ist jedoch das Problem der "kürzesten Route". Wenn Sie die kürzesten Kosten finden, möchten Sie normalerweise die Route kennen. Lassen Sie uns den obigen Code verbessern.
def dijkstra(nodes):
start_node = nodes[0]
routes_from_start = {n: math.inf for n in nodes}
#Setzen Sie Null auf den ersten Scheitelpunkt
routes_from_start[start_node] = 0
minHeap = []
#Fügen Sie den ersten Scheitelpunkt hinzu
heappush(minHeap, (0, start_node))
path = collections.defaultdict(Node)
#Suchen Sie, bis der Heap leer ist
while minHeap:
(cost, current_node) = heappop(minHeap)
#Da der Prioritätsschlüssel doppelt vorhanden ist, überprüfen Sie dies hier
if cost > routes_from_start[current_node]:
continue
for node in current_node.routes:
price_info = current_node.routes[node]
if routes_from_start[node] > price_info + routes_from_start[current_node]:
routes_from_start[node] = price_info + routes_from_start[current_node]
#Notieren Sie den Knoten, der die kürzeste Entfernung aktualisiert
path[node.id] = current_node.id
#Mehrwert für die Priorität bei Aktualisierung
heappush(minHeap, (price_info + routes_from_start[current_node], node))
current_node = nodes[-1].id
path_array = []
#Folgen Sie dem Knoten, der die kürzeste Entfernung vom Ziel aufgezeichnet hat
while current_node:
path_array.append(current_node)
if current_node not in path:
break
current_node = path[current_node]
return routes_from_start[nodes[-1]], path_array[::-1]
Der Dyxtra-Algorithmus weiß, welcher Knoten die kürzeste Entfernung aktualisiert, sodass Sie sie aufzeichnen und zuletzt verfolgen können. Der Rechenaufwand erhöht sich um die Anzahl der Knoten mit der kürzesten Entfernung.
Warum ist das übrigens der kürzeste Weg?
Übrigens denke ich, dass viele Leute so gedacht haben, nachdem sie es bisher gesehen haben. Sicher, der Algorithmus ist einfach und nicht allzu schwer zu implementieren. Aber warum finden Sie die kürzeste Entfernung? Lassen Sie es uns leicht überprüfen
Unter der Annahme, dass die Eckpunkte in L die kürzeste Entfernung vom Start S sind, wäre es schön zu sagen, dass die kürzesten von dort verbundenen Eckpunkte auch die kürzeste Entfernung von S sind.
Nun, da es sich zu dem kürzesten in T enthaltenen Scheitelpunkt bewegt, wenn der kleinste Punkt i ist, dann ist d [i] = min (T), nicht wahr? Unter der Annahme, dass jeder Scheitelpunkt k ist, ist es sicher, dass der kürzeste Abstand d [k] d [k]> = d [i] ist. Weil d [i] der kleinste Punkt ist und jeder Scheitelpunkt nicht negativ ist. Sie können es rekursiv beweisen, indem Sie es nacheinander tun.
Nun, wenn Sie sorgfältig darüber nachdenken, ist es eine schrittweise Formel.
Der kürzeste Abstand zwischen den Eckpunkten von L neben d [i] = min (k ⊂ T) + i
Wenn es sich um eine schrittweise Formel handelt, die dynamische Planungsmethode
Die schrittweise Formel lautet DP, nicht wahr? Dieser Artikel ist sehr hilfreich für DP (https://qiita.com/drken/items/a5e6fe22863b7992efdb)
Wie wird der Wert mit DP aktualisiert?
Der Wert wird folgendermaßen aktualisiert. Die vertikale Achse ist die Anzahl der Versuche. Die horizontale Achse ist die Spitze.
Was der Dyxtra-Algorithmus war, war eine Art DP.
Zusammenfassung
Der Dyxtra-Algorithmus, den ich ausprobiert habe, aber sobald Sie ihn verstanden haben, ist er ziemlich einfach zu verstehen. Danach, als ich versuchte, es zu implementieren und auf ein ähnliches Problem aufgrund eines Algorithmusproblems stieß, war dies diese Zeit! !! Ich möchte es so lösen.
- Nebenbei möchte ich auch einen DP-Artikel schreiben
Klicken Sie hier, um den erklärten YouTube-Kanal aufzurufen https://youtu.be/jz8b0q5R1Ss
Referenz
http://www.lab2.kuis.kyoto-u.ac.jp/~shuichi/algintro/alg-6s.pdf https://www.youtube.com/watch?v=X1AsMlJdiok
Recommended Posts