Liste sortieren: Summe der Entfernungen aller Elemente soll minimal sein
-
Ich möchte eine std::list sortieren. Das ist kein Problem, wenn man das nach einer einzigen Größe der Elemente macht. Ich möchte jedoch so sortieren, dass die Summe der Entfernungen zwischen den Elementen in einer Ebene minimal ist. Jedes Element hat eine Ortsinfo p(x,y). Wie gehe ich so etwas an? Beispiel-Link?
Als Anfang könnte man das Element suchen, das am nächsten an (0,0), das ist die linke obere Ecke, ist.
Weiter: Liste durchgehen und prüfen, welches Element am nächsten dran ist. Dieses Element aus der Liste entfernen und an die aktuelle Position sortieren? splice?
-
Ist NP schwer.
https://en.wikipedia.org/wiki/Travelling_salesman_problem
-
echt heiße kiste:
vorher/nachher:
dist before: 7334.2
dist after: 7334.2dist before: 5951.29
dist after: 8908.69dist before: 8829.55
dist after: 4854.32Gibt es einen Ansatz, das Feld so zu ordnen/sortieren, dass Elemente mit ähnlicher Region (entsprechend x,y) zusammen kommen?
-
Guggsdu Wiki Seite Abschnitt "Heuristic and approximation algorithms".
-
Wozu verwendest du std::list?
-
hustbaer schrieb:
Guggsdu Wiki Seite Abschnitt "Heuristic and approximation algorithms".
Ich würde vor allem 2-Opt empfehlen. Leicht zu implementieren und die Ergebnisse in der Praxis waren bei uns immer extrem gut (ungefähr 1% bis zum Optimum).
-
std__wtf schrieb:
Wozu verwendest du std::list?
Das ist aus anderen Gründen gewählt. Welche Vorteile bieten andere Container bez. der Fragestellung?
-
m.e. schrieb:
hustbaer schrieb:
Guggsdu Wiki Seite Abschnitt "Heuristic and approximation algorithms".
Ich würde vor allem 2-Opt empfehlen. Leicht zu implementieren und die Ergebnisse in der Praxis waren bei uns immer extrem gut (ungefähr 1% bis zum Optimum).
Danke für den Hinweis. 2-Opt habe ich bisher nicht gekannt.