Minimierung der gewichteten Summe

Es gibt eine sehr wichtige Tatsache, die zu einem Polynomialzeitalgorithmus führt:

Da sich die Punkte auf einer Achse befinden, erzeugen sie ein Pfaddiagramm, was bedeutet, dass für jeweils 3 Ecken v1,v2,v3 , wenn v2 zwischen v1 und v3 steht, dann die Entfernung zwischen v1 und v3 entspricht der Entfernung zwischen v1 und v2 plus dem Abstand zwischen v2 und v3 . Wenn wir zum Beispiel bei v1 anfangen, wird das obj. Funktionswert eines Pfades, der zuerst nach v2 und dann nach v3 geht, ist immer kleiner als der Wert des Pfades, der zuerst nach v3 und dann zurück nach v2 geht, weil:

value of the first path = w[2]*D(v1,v2)+W[3]*(D(v1,v2)+D(v2,v3))

value of the second path = w[3]*D(v1,v3)+W[2]*((v1,v3)+D(v3,v2)) = w[3]*D(v1,v2)+w[3]*D(v2,v3)+w[2]*(D(v1,v2)+2*D(v3,v2))

Wenn wir den ersten Pfadwert von dem zweiten subtrahieren, bleibt w[2]*2*D(v3,v2) gleich oder größer als 0, es sei denn, Sie berücksichtigen negative Gewichtungen.

All dies bedeutet, dass, wenn wir uns an einem bestimmten Punkt befinden, es immer nur zwei Möglichkeiten gibt, die wir in Betracht ziehen sollten: zum nächsten unbesuchten Punkt auf der linken Seite oder zum nächsten nicht besuchten Punkt auf der rechten Seite zu gehen.

Dies ist sehr bedeutsam, da es uns 2^n mögliche Pfade gibt und nicht n! mögliche Pfade (wie im Problem des Traveling Salesman).

Wenn Sie den TSP / minimalen Hamilton-Pfad auf Pfaddiagrammen in polynomieller Zeit mit dynamischer Programmierung lösen, sollten Sie genau die gleiche Methode anwenden, aber die Art der Berechnung der Zielfunktion ändern.

Da Sie den Anfangsscheitel nicht kennen, müssen Sie diesen Algorithmus n time ausführen, wobei jedes Mal von einem anderen Scheitelpunkt aus begonnen wird, was bedeutet, dass die Laufzeit mit n multipliziert wird.

Vielleicht sollten Sie erläutern, was Sie meinen, dass der Algorithmus "nicht funktioniert" . Die Grundidee des gierigen Ansatzes, den Sie beschrieben haben, erscheint mir machbar. Meinst du, dass der gierige Ansatz nicht unbedingt die optimale Lösung findet? Wie in den Kommentaren darauf hingewiesen wurde, könnte dieses ein NP-vollständiges Problem sein - obwohl man es natürlich weiter analysieren müsste: Etwas dynamische Programmierung und vielleicht einige Präfix-Summen für die Abstandsberechnungen könnten auch zu einer polynomialen Zeitlösung führen.

Ich habe schnell die gierige Lösung in Java implementiert (hoffentlich habe ich alles richtig verstanden ...)

Die Reihenfolge der Indizes, die Sie im Beispiel beschrieben haben, ergibt die Lösung

Der gierige Ansatz, den Sie beschrieben haben, gibt

Die beste Lösung ist

was ich gefunden habe, indem ich alle Permutationen der Indizes überprüft habe (dies ist natürlich nicht für größere n möglich)

Angenommen, Sie sind durch eine Lösung gegangen und haben die Entfernung D so weit zurückgelegt. Wenn Sie eine weitere Strecke x gehen und einen Punkt mit Gewicht w sehen, kostet es Sie (D + x) w. Wenn Sie eine weitere Strecke y gehen und einen Punkt mit dem Gewicht v sehen, kostet es Sie (D + x + y) v. Wenn Sie all dies zusammenrechnen, gibt es eine Komponente, die vom Pfad abhängt, den Sie nach dem Abstand D nehmen: xw + xv + yv + ..., und es gibt eine Komponente, die von der Entfernung D und der Summe der Gewichte der Punkte abhängt, die Sie tragen müssen: D (v + w + ...). Aber die Komponente, die von der Entfernung D abhängt, hängt nicht von etwas anderem ab als von der Summe der Gewichte der zu besuchenden Punkte, also ist sie festgelegt, in dem Sinne, dass sie unabhängig vom Weg, den sie nach der Entfernung nehmen, gleich ist D.

Es macht immer Sinn, Punkte zu besuchen, die wir passieren, wenn wir sie besuchen, also beginnt der beste Weg mit einem einzelnen Punkt (möglicherweise am Rand der zu besuchenden Punkte und möglicherweise in der Mitte) und erweitert sich dann dies zu einem Intervall von besuchten Punkten, und dann erweitern, um alle Punkte zu besuchen. Um die relativen Kosten für den Besuch aller Punkte außerhalb des Intervalls vorausberechnen zu können, müssen wir nur die aktuelle Position und die Größe des Intervalls kennen, nicht die bisher zurückgelegte Entfernung.

Ein teures, aber polynomiales dynamisches Programmierverfahren hat als den Zustand die aktuelle Position (die einer der Punkte sein muss) die Position des ersten, wenn überhaupt, nicht besuchten Punkts links von der aktuellen Position und der Position, falls vorhanden, des ersten nicht besuchten Punkts rechts vom aktuellen Punkt. Es gibt höchstens zwei Punkte, die wir als nächstes betrachten sollten - den Punkt rechts vom aktuellen Punkt und den Punkt links vom aktuellen Punkt. Wir können die Kosten dieser beiden Alternativen berechnen, indem wir die vorausberechneten Kosten für Staaten mit weniger verbleibenden Punkten betrachten und das beste Ergebnis ab diesem Zeitpunkt als die bestmöglichen Kosten speichern. Wir könnten diese Kosten unter der Fiktion berechnen, dass D = 0 ist, wenn wir den aktuellen Punkt erreichen. Wenn wir gespeicherte Kosten nachschlagen, werden sie auch unter dieser Annahme gespeichert (aber mit D = 0 an ihrem aktuellen Punkt, nicht unserem aktuellen Punkt), aber wir kennen die Summe der Gewichtungen von Punkten, die in diesem Stadium übrig sind, also können wir hinzufügen die gespeicherten Kosten, die die Summe der Gewichte mal die Entfernung zwischen unserem aktuellen Punkt und dem Punkt, den wir suchen, kosten, um dies zu kompensieren.

Das ergibt Kosten O (n ^ 3), weil Sie eine Tabelle mit O (n ^ 3) -Zellen erstellen, wobei jede Zelle das Produkt eines relativ einfachen Prozesses ist. Da es jedoch nie Sinn macht, Zellen zu übergeben, ohne sie zu besuchen, muss der aktuelle Punkt neben einem der beiden Punkte an jedem Ende des Intervalls liegen, sodass wir nur O (n ^ 2) -Möglichkeiten berücksichtigen müssen, was die Kosten senkt runter zu O (n ^ 2). Ein Zick-Zack-Pfad wie (0, 1, -1, 2, -2, 3, -3, 4, -4, ...) könnte die beste Lösung für angemessen bizarre Gewichte sein, aber es ist immer noch so, zum Beispiel, wenn man von -2 auf 3 geht, ist -2 zu den nächsten Punkten, die zwischen den beiden Punkten 3 und -3 noch nicht erreicht wurden.

Ich habe versucht, eine Java-Implementierung in Ссылка durchzuführen. Das Test-Kabelbündel überprüft diese DP-Version gegen eine (langsame) fast vollständige Version für eine Anzahl zufällig generierter Testfälle mit einer Länge von bis zu 12. Es ist zwar immer noch nicht vollständig fehlerfrei, aber hoffentlich wird es die Details ausfüllen.