Ich löse ein Problem mit der Optimierung der Diagrammsuche. Ich muss die k besten azyklischen kürzesten Wege durch einen gerichteten gewichteten Graphen finden.
Ich weiß, dass es eine Reihe von genauen und ungefähren k-best-Algorithmen gibt, aber die meisten neueren Untersuchungen scheinen sich an sehr großen, sehr spärlich verknüpften Graphen zu orientieren (z. B. Routenführung und Richtungen), und meine Grafik ist keine von beiden.
Unterscheidungsmerkmale meines Problems:
Das Diagramm besteht aus ungefähr 160 Scheitelpunkten.
Der Graph ist fast vollständig verbunden (bidirektional, also ~ 160 ^ 2 ~ = 25k Kanten)
k wird ziemlich klein sein (wahrscheinlich weniger als 10)
Die maximale Pfadlänge wird wahrscheinlich begrenzt und auch sehr klein sein (zB 3-5 Kanten)
Ich habe oben 'azyklisch' gesagt, aber nur um es noch einmal zu wiederholen - Lösungen dürfen keine Zyklen enthalten. Dies ist kein Problem für den 1-besten kürzesten Weg, aber es wird ein Problem für den k-besten Weg. Betrachten Sie beispielsweise eine Straßenführung eine kurze Reise um einen Block irgendwo. Das ist vielleicht mathematisch optimal, aber keine sehr nützliche Lösung. ;-)
Möglicherweise müssen wir die Kanten für jede Berechnung sofort neu gewichten. Ein Kantenkosten besteht aus einer gewichteten Summe mehrerer Faktoren, und die endgültigen Anforderungen (wann immer wir sie erhalten) können es einem Benutzer ermöglichen, seine eigene Priorisierung dieser Gewichtungsfaktoren festzulegen und die Kantengewichtung zu ändern. Dies ist ein relativ kleines Diagramm (wir sollten es in der Lage sein, es in ein paar hundert KB darzustellen). Es ist daher wahrscheinlich sinnvoll, das Diagramm im Speicher zu klonen, die Neugewichtung anzuwenden und dann die Suche im geklonten Diagramm auszuführen. Aber wenn es eine effektivere Methode gibt, um die Suche durchzuführen, während Gewichte on-the-fly berechnet werden, bin ich interessiert.
Ich beschäftige mich mit den in Santos (K-Algorithmen), Eppstein 1997 (Finding the k Shortest Paths) und anderen beschriebenen Algorithmen. Der Algorithmus von Yen ist vor allem aufgrund der vorhandenen Java- Implementierung von Interesse . Ich habe keine Angst davor, die Forschungsarbeiten zu lesen, aber ich dachte, es lohnt sich, die Details meines Problems zu besprechen und nach Hinweisen zu fragen, um etwas Lesezeit zu sparen.
Und wenn Sie Zeiger auf Java-Implementierungen haben, noch besser.
quelle
Antworten:
Um meine eigene Frage teilweise zu beantworten:
Seit dem Posten dieser Frage habe ich festgestellt, dass wir sowohl mit negativen als auch mit positiven Kantengewichten umgehen müssen (die Beschränkung auf azyklische / einfache / schleifenlose Pfade bedeutet, dass die beste Lösung definiert wird, während ohne diese Beschränkung der kürzeste Pfad durch einen Graphen mit negativem Wert definiert wird. Kostenzyklen ist undefiniert).
Der Algorithmus von Yen und die meisten anderen, die ich untersucht habe, hängen von einer Reihe von 1-besten Suchanfragen ab. Die meisten verwenden Dijkstra für diese Zwischensuchen. Dijkstra unterstützt keine negativen Kantengewichte, aber wir können stattdessen Bellman-Ford einsetzen (zumindest in Yen; vermutlich auch in Lawler oder Eppstein). Ich habe eine Modifikation von Bellman-Ford mit einer Pfadlängenbegrenzung (in Kanten) und einer expliziten Zyklusprüfung während der Suche (anstelle der Standard-Zykluserkennung nach der Suche) entwickelt. Die rechnerische Komplexität ist schlimmer, aber für meine Anforderungen noch nachvollziehbar. Ich bearbeite diese Antwort und verknüpfe sie mit einem technischen Bericht, wenn ich die Erlaubnis zum Posten erhalte.
quelle
Ich würde sagen, diese Frage kann leicht gegoogelt werden und ist auch ein Duplikat:
Davon abgesehen habe ich Eppstein bereits genutzt und implementiert und empfehle es weiter. Ich fand es ziemlich elegant. Wenn ich mich recht erinnere, kann es auch optimal sein, und das folgende Papier erklärt es sehr schön:
http://pdf.aminer.org/001/059/121/finding_the_k_shortest_paths.pdf
quelle