Was ist der effizienteste Weg, einen Weg durch eine kleine Welt Graphen zu finden?

StackOverflow https://stackoverflow.com/questions/221311

Frage

Ich habe ein Meer von gewichteten Knoten mit Kanten zusammen Cluster von Knoten verbinden. Dieser Graph folgt das typische kleine Welt Layout.

Ich möchte einen Weg zu finden Algorithmus zu finden, die auf die Prozessorleistung nicht teuer ist, einen Weg entlang der bestmöglichen Weg zu finden, wo die Knoten der am günstigsten gewichtet, der schnellste Weg sind, ist nicht der wichtigste Faktor. Dieser Algorithmus berücksichtigt auch tragfähig und Verkehr Rerouting.

(Nebenbei bemerkt: könnten neuronale Netze verwendet werden)

Danke

Ich betrachte ACO . Gibt es etwas Schöneres als ACO für diese Art von Problem?

Rechts die A * Algorithmus findet die geringsten Kosten oder schnellste Route, ohne Lastausgleich.

Nehmen wir an, dass die schnellste oder kürzeste Route nicht der wichtigste Weg ist, was noch wichtiger ist, folgt einem Pfad, in dem die gewichteten Knoten einen bestimmten Wert haben. no1.

no2. Wenn A * mit dem Verkehr auf dieser Strecke dann überlastet wird plötzlich dieser Weg ist überflüssig. So so cool wie A * ist, tut es bestimmte Funktionen, die ACO dh inhärenter Lastausgleich.

- es sei denn, im Irrtum und A * mißverstanden

Was dann schlägt ACO?

Es sieht wirklich wie eine Show nach unten zwischen ACO und A *, gibt es so viele positive Diskussion über A * gewesen ist, ich tiefer sicherlich in sie aussehen werde.

Zum einen als Antwort auf David; Ich kann ACO Simulation im Hintergrund laufen und mit dem besten Weg kommen, also ja gibt es einen anfänglichen Startkosten, sondern der Start zum Glück ist nicht von wesentlicher Bedeutung. So kann ich leisten, eine Simulation mehrere Male ausführen. Das ein wirkliches Problem ist das Auffinden verbundenen Quell- und Zielknoten. Während es A * scheint wird dies leicht ganz die Lage zu tun. Nun, was passiert, wenn dieses Netzwerk fürchterlich groß wird wie in Millionen von Knoten. Wird A * in der Lage sein, leicht zu skalieren?

Ich will ein Forschungs * weiter. Aber ich lasse Sie mit einer letzten Frage!

Wird A * in der Lage sowie Antnet (ACO) zu skalieren?

War es hilfreich?

Lösung

Allgemeine Hinweise

Dijkstra-Algorithmus und optimierte Variante A * den Pfad mit „den“ minimal Kosten durch Ihr Diagramm finden. Die wichtigen Dinge sind a) Definieren Sie Ihre Graphen richtig und b), die eine entsprechende Kostenfunktion.

Angesichts einer sich verändernden Kostenfunktion Dijksta benötigt man die Lösung neu zu berechnen.

Für Lastenausgleich würde ich Dikstra verlängern, um nicht nur den optimalen Weg zu berechnen, aber eine Art von Hochwasser-fill Verhalten verwenden, um eine Reihe von möglichen Pfaden zu erstellen (nach Kosten sortierte) Alternativen zu finden. Nur das Wissen über das spezifische Problem und Kostenfunktion beantworten, ob und wie dies funktionieren könnte.

Ant Colony Optimization auf der anderen Seite scheint bei der Anpassung an ein sich veränderndes viel flexibler zu sein Kostenfunktion, durch die Iteration nach der Fortsetzung / während der Kostenfunktion ändert.

Effizienz

Das hängt sehr stark von Ihrer Problemdomäne. Wenn Sie eine gute Heuristik haben (siehe Komplexität Abschnitt des A * Artikel ) und selten Kostenänderungen dann A * 's Polynom Laufzeit begünstigen könnten Neuberechnungen wiederholt. ACO auf der anderen Seite hat immer und immer wieder zu wiederholen, bevor sie auf einer ungefähren Lösung konvergieren. Wenn Kostenänderungen sehr häufig auftreten, kann die Iteration mit einer konstanten Geschwindigkeit fort effizienter sein als die A * -Lösung aktualisieren, da Informationen im Zustand des Algorithmus beibehalten werden. ACO verspricht nicht die eine optimale Lösung, wenn und wahrscheinlich hat eine höhere Anlaufkosten, bevor sie auf eine „gute“ Lösung konvergieren. Auch hier, dass sehr viel von Ihrer spezifischen Domain abhängt, Graphen und Kostenfunktion sowie Ihre Anforderungen an die Optimalität.

Andere Tipps

Mit A *, die Pfadkosten muss nicht konstant sein, so können Sie mit der folgenden Grafik starten: 

A---1---B---1---C
|               |
\-------1-------/

, wo wir von A bis C. Zunächst gehen wollen, der Weg Algorithmus zu finden, wird den A-C-Pfad wählen, da A-B-C 2 ist, während A-C 1. ist können wir einen zusätzlichen Begriff zu den Pfaden hinzuzufügen: 

A---r---B---r---C
|               |
\-------r-------/

mit 

r(NM) = k(NM) + users(NM) / 10

Dabei steht 

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

Als Benutzer zu dem System hinzugefügt wird, werden die Strecke AC teurer als ABC zwanzig Benutzer (1 + 20/10) = 3, ABC 2. ist als Benutzer aus dem System entfernt wird, wird die AC Route wird worden die beste Option wieder.

Die wirkliche Macht der A * ist die Heuristik Sie die Kosten für jede Verbindung berechnen verwenden.

Die am häufigsten verwendeten Algorithmus für dieses Problem ist A * (A Star) , das ist eine verallgemeinerte Dijkstra-Algorithmus mit zusätzlichen Heuristiken suchen - der Zweck der Heuristik ist zu lenken die Suche auf die Suche Ziel, so dass typische Suchanfragen schneller zu beenden.

Dieser Algorithmus hat viele Varianten, abgeleitete Versionen und Verbesserungen, Google-Suche oder die Wikipedia-Seite sollte ein guter Ausgangspunkt sein.

Auf jeden Fall A *. A * wird entweder findet den besten Weg möglich oder keinen Weg überhaupt, wenn kein Pfad vorhanden ist. Z.B. der Weg dieses Bootes berechnet worden ist A * mit


(Quelle: cokeandcode.com )

Hier ist ein interaktive Java Demo rel="nofollow zu spielen. Bitte beachten Sie, dass dieser Algorithmus durch schläft verlangsamt wird, so dass Sie sehen es durchgeführt wird. Ohne diese langsam nach unten würde es den Weg in weniger als eine Sekunde finden.

Der Algorithmus ist einfach, aber mächtig. Jeder Knoten 3 Werte hat, g die Kosten bis zu diesem Knoten. h sind die geschätzten Kosten von diesem Knoten zu dem Ziel und f ist die Summe von beiden (es ist eine Vermutung für den vollständigen Pfad). A * verwaltet zwei Listen, die offene und die geschlossene Liste. Die Open-Liste enthält alle Knoten, die bisher nicht erforscht. Die Closed-Liste alle Knoten, die untersucht wurden. Ein Knoten gilt als erforscht, wenn der Algorithmus bereits jeden Knoten verbunden zu diesem Knoten (nur verbunden könnte bedeuten, horizontal und vertikal, sondern auch diagonal, wenn diagonal bewegt sich zwischen den Knoten erlaubt sind).

getestet

Der Algorithmus könnte als

beschrieben
  1. P sei der Ausgangspunkt
  2. Weisen g, h und f Werte P
  3. Fügen Sie P in der offenen Liste (an diesem Punkt P ist der einzige Knoten auf dieser Liste).
  4. B sei der beste Knoten aus der Liste Öffnen sein (am besten == niedrigsten Wert f)
    • Wenn B der Zielknoten ist -> beenden Sie den Pfad gefunden
    • Wenn die Öffnen Liste ist leer -> beenden, existiert kein Pfad
  5. C sei ein gültiger Knoten zu B verbunden sein
    • Zuweisen g, h und f C
    • Überprüfen Sie, ob C ist auf dem Open oder Closed-Liste
      • Wenn ja, prüfen, ob neue Wege am effizientesten ist (niedriger f-Wert)
        • Wenn ja, aktualisieren Sie den Pfad
      • Else hinzufügen C auf die Liste öffnen
    • Wiederholen Sie Schritt 5 für alle Knoten B verbunden
  6. Fügen Sie B in die geschlossene Liste (erkundeten wir alle Nachbarn)
  7. Wiederholen von Schritt 4.

Haben Sie auch einen Blick auf Wikipedia für Implementierungsdetails.

Ich habe von einer NN Implementierung gehört auch diese Art von Problem zu behandeln. Also, wenn Sie NNs verwenden möchten Sie schließlich Ihren Weg finden ;-) aber sie müssen im Vergleich zu „genetischen Algorithmen“ minderwertig sein.

Wenn die rechnerische / Zeitverbrauch ein Problem ist, würde ich sehr empfehlen die Verwendung von genetischen Algorithmen. Dies ist excactly die Art der Probleme, die sie in außergewöhnlich sind.

GAs auf einer Funktion basiert, die Ihre Zufriedenheit für jede gegebene Lösung beschreibt. Diese Funktion können Sie ändern Ihre Bedürfnisse anpassen (dh. Sie können nicht nur umfassen Pfadkosten, sondern jeden Faktor, den Sie möchten).

Wäre ein gemeinsamer Dijkstra ist nicht ausreichend?

http://improve.dk/generic-dijkstras-algorithm/

Dijkstras Algorithmus, kleines Beispiel für Sie 

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top