Hallo dort Ich arbeite an einem Projekt, das das TSP-Problem lösen muss. Was ich hier brauche ist, dass ich die Hamilton-Schaltungen in der Grafik finden kann. Tatsächlich weiß ich, wie man das in der realen Welt macht. Aber in der Implementierung und im Quellcode weiß ich nicht, wie das gemacht werden kann. Ich habe Artikel im Internet gelesen, die einige verschachtelte Loops verwenden, aber ich habe nicht verstanden, wofür jeder einzelne Code verwendet wird und wie die ganze Geschichte weitergeht. Ich würde es schätzen, wenn mir jemand dabei helfen kann. Und geben Sie mir ein einfaches Beispiel, wie Sie das umsetzen können. Ich brauche kein Arbeitsmodell. Nehmen wir an, wir haben ein Array von Scheitelpunkten und ein Array von Pfaden (mit Pfad meine ich die Anfangs- und Endscheitelpunkte des Pfades). Wie können wir dieses Problem lösen?Problem beim Auffinden der Hamilton-Schaltung für TSP-Problem
Antwort
Eine der effizienteren Möglichkeiten, eine genaue Lösung für TSP zu finden, ist die Verwendung eines dynamischen Programmieralgorithmus, der in O (n^2 * 2^n) läuft. Es ist ziemlich einfach im Vergleich zu einigen der linearen Programmieralternativen. Suchen Sie nach "TSP Dynamic Programming" und Sie werden sicherlich viele Beispiele finden.
Es gibt mehr naive Ansätze, wie Brute Force, die in O (n!) Laufen. Wenn Sie viele for-Schleifen gesehen haben (dh mehr als zwei), ist dies wahrscheinlich die Art von Algorithmus, die Sie zuvor gesehen haben. Diese werden die Arbeit erledigen (vielleicht nicht in dieser Lebenszeit, abhängig von der Größe Ihres Graphen).
Ich denke, etwas Nützliches sollte nicht mehr sein als O (n³) – Pietro
@Pietro Er versucht, (möglicherweise das berühmteste) NP-schweres Problem in der Informatik zu lösen. Ich bin daran interessiert, wie Sie denken, dass es nicht mehr als O (n^3) laufen sollte. –
@Ian Bischof. DP kann eine Möglichkeit sein, den TSP zu lösen (ein NP-Hard-Problem). Ich bezweifle, dass Forschung betrieben wurde, um seine "beste (effizienteste)" gegenüber anderen Ansätzen zu etablieren ... Ich bin ziemlich sicher, dass die Branch-and-bound/cut-Generierung für die Subtour-Eliminierung wahrscheinlich wettbewerbsfähig sein wird. – Tryer
Ich bin nicht sicher, zu verstehen, was Sie wollen, aber die TSP auf die schnellste Weise zu lösen, müssen Sie verschiedene Algorithmen kombinieren wie: nächster Nachbar, 2-opt, 3-opt, ant-Algorithmus, ... Das Problem ist um sie besser als Programmierung zu kombinieren. – Pietro
Nein, mein Problem ist nicht, den schnellen Weg zu finden, es geht nur um die Implementierung davon. Ich meine, mit welchen Schritten kann ich einen Zyklus in einem Graphen finden? Dann möchte ich die Zyklen vergleichen und sehen, welche alle Knoten besucht und dann möchte ich die minimale Tour finden. Ich weiß, dass es kein guter Algorithmus ist, aber ich möchte genau das umsetzen. Und ich weiß nicht, wie der Programmieralgorithmus zum Finden eines Zyklus im Graphen ist. – user435245
Sie könnten feststellen, dass eine Graphenbibliothek die Dinge etwas einfacher macht, so dass Sie sich nicht selbst mit rohen Vertex-/Kanten-/Subgraph-/Pfaddarstellungen herumschlagen müssen. Ich benutze http://jgrapht.org/ – andersoj