Lineare Optimierung beim TSP

[Uwe Raabe]

Zitat von Nikolas:

Zitat:

Ich würde gerne mit Verfahren beginnen, die zumindest ermöglichen eine gefundene Lösung abzuschätzen, also eine untere Schranke für die Zeit die für die benötigt wird zu finden.

Was verstehst du unter einer "unteren Schranke"? Ich denke dabei an die kürzeste Strecke und du wirst keinen Algorithmus finden, der dir diese Information schnell geben wird, da das ja die Lösung von TSP wäre.

Das ist nicht ganz richtig: Die "untere Schranke" ist eine Zahl, die garantiert nicht unterschritten wird, unabhängig davon, ob sie tatsächlich erreicht werden kann. Insofern ist die Lösung des TSP die "größte untere Schranke".

Eine untere Schranke wird als Ausschlußkriterium für einen zu untersuchenden Unterraum der Lösungen verwendet. Wenn der aktuelle Weg plus der unteren Schranke der Restwege größer als meine aktuell beste Lösung ist, kann ich den gesamten Unterraum weglassen.

Ein Beispiel (wenn auch kaum brauchbar) für eine untere Schranke beim TSP ist die Summe der N kürzesten Strecken aus dem Pool der Strecken, die nur Punkte miteinander verbinden, die ich noch nicht besucht habe plus dem aktuellen Punkt.