Laufzeit von Nearest Insertion für TSP

06.12.2012, 14:12	Hobbes	Auf diesen Beitrag antworten »
Laufzeit von Nearest Insertion für TSP Meine Frage: Hallo Mahteboardler, mein Problem ist, dass folgende die Nearest-Insertion Heuristik hat (angeblich, Prof., Wikipedia..) quadratische Laufzeit. Dabei muss der Algorithmus in einer Phase zu einer bestehenden Tour, eine Stadt finden welche einer in der Tour befindlichen Stadt am nächsten ist (nearest-selection). Meine Ideen: Ich habe mir bei der Analyse, dass bisher so gedacht im i-ten Schritt muss für jede der (n-i) Städte die Distanz bestimmt werden, also muss in jedem Schritt i(n-i) Distanzen berechnet werden. Da in (n-1) Knoten eingefügt werden müssen, beträgt doch die Laufzeit somit $\begin{eqnarray} <br /> \sum\limits_{i=1}^{n-1} i(n-i) = n \sum\limits_{i=1}^{n-1} i - \sum\limits_{i=1}^{n-1} i^2=<br /> n \frac{n(n-1)}{2} - \frac{(n-1)n(2n-1)}{6}<br /> \end{eqnarray}$ diese Laufzeit ist jedoch kubisch. Was mache ich also falsch? Für Tipps, Tricks und Hinweise wäre ich sehr dankbar.
06.12.2012, 14:25	Hobbes	Auf diesen Beitrag antworten »
Ok, habs selber raus. Man darf natürlich nicht in jeder Runde alles neu berechnen sondern aktualisiert nur Distanz. Trotzdem danke

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »