Der nächste Einfügungsalgorithmus
Der nächstgelegene Insertionsalgorithmus ist ein heuristischer Algorithmus, mit dem eine ungefähre Lösung für das reisende Verkäuferproblem (TSP) gefunden wird. Der TSP zielt darauf ab, die kürzeste Route zu finden, die jede Stadt (Knoten) genau einmal besucht und in die Startstadt zurückkehrt.
wie es funktioniert:
1. Initialisierung:
- Beginnen Sie mit einem willkürlichen Knoten als anfängliche Tour (z. B. eine einzelne Knotenschleife). Nennen wir diesen Knoten `start_node`.
- Sei `v` der Satz von Knoten, die der Tour noch nicht hinzugefügt wurden.
2. Iteration:
- den nächsten Knoten finden: Für jeden Knoten `I 'In der aktuellen Tour finden Sie den Knoten` J` in `v` (der Satz von nicht besuchten Knoten), der` i' am nächsten ist (d. H. Die kleinste Entfernung hat). Dieser "nächste" Knoten `J` ist derjenige, den wir einfügen möchten. Mathematisch finden wir:
`j =argmin_ {v ∈ V} min_ {i ∈ Tour} dist (i, v)`
- den nächsten Knoten einfügen: Finden Sie die Kante (i, k) in der aktuellen Tour, bei der das Einfügen des Knotens `j" zwischen Knoten `I und" K` führt zu einer geringsten Zunahme der Tourlänge. Das heißt, ich finde "Ich und K`, so dass:
`dist (i, j) + dist (j, k) - dist (i, k)` wird minimiert.
- Einfügen des Knotens `j` zwischen Knoten` i 'und `k`, was die Kante (i, k) effektiv durch zwei Kanten (i, j) und (j, k) ersetzt.
- Entfernen Sie den Knoten `J` aus dem Satz nicht besuchter Knoten` v`.
3. Beendigung:
- Wiederholen Sie Schritt 2, bis alle Knoten zur Tour hinzugefügt wurden (d. H. "V" ist leer).
4. die Schleife schließen:
- Schließen Sie den letzten Knoten an, der zur Tour zurück zum `start_node` hinzugefügt wurde, um den Zyklus zu vervollständigen.
Beispiel:
Nehmen wir an, wir haben Städte A, B, C, D und E mit den folgenden Entfernungen:
`` `
A b c d e
A 0 10 15 20 25
B 10 0 35 25 30
C 15 35 0 30 20
D 20 25 30 0 10 10
E 25 30 20 10 0
`` `
1. Start: Beginnen wir mit dem Knoten A als anfängliche Tour:`tour ={a}`
2. Iteration 1:
- Der nächste Knoten zu A ist B (Abstand 10).
-Einlegen Sie B in die Tour (a -> b -> a). `Tour ={a, b, a}`
3. Iteration 2:
- Finden Sie den nächsten nicht besuchten Knoten zu jedem Knoten in der aktuellen Tour:
- Nächst A:C (15), D (20), E (25)
- Nächst B:C (35), D (25), E (30)
- Das Minimum dieser Entfernungen beträgt 15 (a bis c).
- Finden Sie, wo C. einfügen soll.
- Einfügen C zwischen A und B:15 + 35 - 10 =40
- Einfügen C zwischen B und A:35 + 15 - 10 =40
- Fügen Sie C zwischen A und B (oder B und A) ein. `Tour ={a, c, b, a}`
4. Iteration 3:
- Finden Sie den nächsten nicht besuchten Knoten:
- Nächst A:D (20), E (25)
- Nächst C:D (30), E (20)
- Nächst B:D (25), E (30)
- Der Mindestabstand beträgt 20 (C bis E oder A bis D). Nehmen wir C nach E.
- Einfügen e:
- Einfügen von E zwischen A und C:25 + 20 - 15 =30
- Einfügen von E zwischen C und B:20 + 30 - 35 =15 (Minimum!)
- Einfügen von E zwischen B und A:30 + 25 - 10 =45
- Einfügen e zwischen C und B. `tour ={a, c, e, b, a}`
5. Iteration 4:
- Nur der Knoten D bleibt.
- Nächst A:D (20)
- Nächst C:D (30)
- Nächst E:D (10) (Minimum!)
- Nächst B:D (25)
- Einfügen D:
- Einfügen von D zwischen A und C:20 + 30 - 15 =35
- Einfügen von D zwischen C und E:30 + 10 - 20 =20
- Einfügen von D zwischen E und B:10 + 25 - 30 =5 (Minimum!)
- Einfügen von D zwischen B und A:25 + 20 - 10 =35
- Einfügen D zwischen E und B. `tour ={a, c, e, d, b, a}`
Optimierung (oder besser gesagt, Approximation) Aspekte:
Der nächstgelegene Insertionsalgorithmus optimiert, indem der Knoten iterativ hinzugefügt wird, der bei jedem Schritt den kleinsten Anstieg der Gesamttourenlänge einführt. Dies ist ein gieriger Ansatz, der in jeder Phase die beste Wahl ist, ohne die globalen Auswirkungen dieser Wahl zu berücksichtigen.
* Lokalität: Der Algorithmus konzentriert sich auf die Minimierung der lokalen Entfernungen. Es wählt den Knoten aus, der der aktuellen Tour am nächsten liegt, und zielt darauf ab, das zusätzliche Segment der Tour so kurz wie möglich zu halten.
* inkrementelles Wachstum: Die Tour wird schrittweise durch Hinzufügen eines Knotens gleichzeitig erstellt. Jede Einfügungsentscheidung basiert auf dem aktuellen Stand der Tour, sodass nicht vorangehen wird, wie sich das Hinzufügen eines bestimmten Knotens zukünftige Einfügungen auswirken kann.
Einschränkungen:
* Nicht optimal: Der nächstgelegene Einfügungsalgorithmus ist eine Heuristik, was bedeutet, dass er die absolut kürzeste Route nicht garantiert. Es kann in lokaler Optima stecken bleiben, wo eine etwas andere frühe Wahl zu einer deutlich besseren Gesamtlösung führen kann.
* gierige Natur: Die gierige Natur des Algorithmus kann zu suboptimalen Entscheidungen führen, insbesondere in Fällen, in denen die Entfernungen nicht einheitlich sind. Manchmal kann die Wahl eines etwas weiteren Knotens frühzeitig Möglichkeiten für kürzere Verbindungen eröffnen.
* Abhängigkeit vom Startknoten: Der Startknoten kann die letzte Tour beeinflussen. Unterschiedliche Startknoten können zu unterschiedlichen Routen führen.
Vorteile:
* einfach zu implementieren: Es ist relativ leicht zu verstehen und zu implementieren.
* schnell: Es ist im Allgemeinen schneller als Algorithmen, die optimale Lösungen garantieren (z. B. Brute-Force-Suche). Die zeitliche Komplexität beträgt typischerweise o (n^2), wobei n die Anzahl der Knoten ist.
* Angemessene Näherung: Es bietet normalerweise eine einigermaßen gute Annäherung an die optimale TSP -Tour, insbesondere wenn die Entfernungen die Dreieck -Ungleichheit erfüllen (d. H. Der direkte Abstand zwischen zwei Punkten ist immer geringer als oder gleich der Summe der Entfernungen entlang eines anderen Pfades).
Zusammenfassend:
Der nächstgelegene Einfügungsalgorithmus ist eine gierige Heuristik, die eine TSP -Tour baut, indem sie der vorhandenen Tour wiederholt den nächsten nicht besuchten Knoten hinzufügt. Obwohl dies nicht garantiert die optimale Lösung erzeugt, ist dies eine schnelle und einfache Möglichkeit, eine einigermaßen gute Annäherung zu finden. Es konzentriert sich auf die Minimierung der lokalen Entfernung bei jedem Schritt.
