Loest einen symmetrischen TSP auf Basis der Two-Tour-Theorie.
Ist eine Adjazenzmatrix symmetrisch und die Dreiecksungleichung gegeben,
so lassen sich die Bounds mittels
(Min1+Min2)/2
genauer
berechnen, was die Rechenzeit enorm verkuerzt.
Die Formel beruht dabei auf
diesem Code und dieser wiederum auf
diesem Beweis.
Ferner werden hier, anders als im Beispiel, die Bounds nur 1x berechnet anstatt diese
jedes Mal neu per Schleife zu ermitteln, was die Rechenzeit um Faktor 10 verkuerzt.
Ferner mussten einige moegliche Fehlerquellen umgeschrieben werden.
- Original:
if (level==1) curr_bound -= ((firstMin(adj, curr_path[level - 1]) + firstMin(adj, i))/2);
else curr_bound -= ((secondMin(adj, curr_path[level - 1]) + firstMin(adj, i))/2);
Ein Kommentator bemerkt ebenfalls falsche Ergebnisse und schlaegt die folgende
Korrektur vor, die auch in dieser Klasse verwendet wird und eher richtig erscheint:
if (level==1) curr_bound -= (secondMin(adj, curr_path[level-1]) + secondMin(adj, i)) /2;
else curr_bound -= (firstMin(adj, curr_path[level-1]) + secondMin(adj, i)) /2;
-
Eine falsche Uebersetzung von C nach Java duerfte ebenfalls in Grenzfaellen falsch laufen:
curr_bound = (curr_bound==1)? curr_bound/2 + 1 : curr_bound/2;
In C ist dies curr_bound&1
, also eine Even-Odd-Pruefung.
Dies wurde fuer Java offensichtlich falsch uebersetzt.
Ueberhaupt: Integer-Rundungsprobleme sind ein entscheidendender Grund, warum manchmal zwar die
optimale Tour gefunden wird, die Rueckwaerts-Variante jedoch nicht. Ein symmetrisches System
hat IMMER eine gerade Anzahl von Loesungen.