|
|||||
  2.
Bisherige kombinatorische Lösungsansätze |
|
2.1 Optimallösung durch vollständige
Enumeration
Die Lösung des Rundreiseproblems aus mathematischer Sicht ist einfach: Man berechnet alle möglichen Rundreisen. Die Rundreise mit der kürzesten Entfernung ist die gesuchte Lösung. Die Schwierigkeit, die kürzeste Rundreise zu ermitteln, liegt nicht in der Berechnung der einzelnen Rundreise selbst sondern daran, dass die Anzahl der Lösungen in Fakultät zu der Anzahl der aufzusuchenden n Orte ansteigt. Aufgrund der (n-1)! Lösungen ist eine vollständige Enumeration nur für Rundreisen mit wenigen Orten möglich. Auch mit schnellsten Rechnern wird sich die Anzahl der Orte nicht wesentlich erhöhen lassen. Bei symmetrischen Rundreisen verringert sich zwar die Anzahl der Lösungen auf die Hälfte, weil jede Rundreise auch entgegengesetzt durchgeführt werden kann. Am Problem selbst ändert sich dadurch jedoch wenig, zumal oft die Symmetrie nicht genutzt wird, und so doch wieder alle Rundreisen berücksichtigt werden müssen. 2.2 Optimallösung durch begrenzte Enumeration Ein möglicher Weg, bei einer größeren Anzahl von Orten zu Optimallösungen zu gelangen, ist die begrenzte Enumeration. Dabei wird beim Berechnen einer Rundreise das Ergebnis jedes Zwischenschrittes mit der bereits früher gefundenen Minimallösung einer Rundreise verglichen. Ist das Ergebnis des Zwischenschrittes größer als die Minimallösung, so wird die Berechnung der Rundreise abgebrochen, weil kein besseres Ergebnis mehr zu erzielen ist (Backtracking). Des weiteren gibt es andere kombinatorische Verfahren, Optimallösungen zu erhalten. Bei allen Lösungen allgemeiner Art bleibt jedoch die Anzahl der aufzusuchenden Orte sehr begrenzt (s.auch 3.5 - Eine Klassifizierung von optimalen TSP-Lösungen). 2.3 Suboptimale Lösungen Neben diesen o.a. Verfahren sind eine Vielzahl von sehr
leistungsfähigen Verfahren entwickelt worden, die zwar nur zu
suboptimalen Lösungen führen, die aber den Anforderungen der
Praxis völlig genügen.
|