Lineare Optimierung beim TSP

[Cyf]

Ich bin irgendwie auf die dumme Idee gekommen, mich mal mit etwas komplexeren Problemstellungen beschäftigen zu wollen.
Also habe ich mir das für Optimierungsprobleme typische TSP mal angesehen und mir verschiedene Lösungsansätze mal angesehen, leider ist mir derzeit die Funktionsweise von exakten Lösungsverfahren (außer praktisch laufzeitmäßig sinnlose Permutation) wie Branch-and-Cut noch nicht wirklich klar, laut Wiki besteht das ganze ja aus einer Kombination von Schnittebenenverfahren und Branch-and-Bound.
Daher mal ein paar Fragen in der Hoffnung jemand kann mir weiterhelfen
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. Leider habe ich in der Richtung überhaupt noch keine Erfahrung (aber durchaus den Willen mich mit ein wenig Mathe zu beschäftigen), mit welchem Verfahren beginne ich am besten?
Funktioniert sowas auch prinzipiell, wenn man das Problem verschärft z.B. wenn sich der Wert der Kanten mit jedem Zug ändern würden z.B. der Handlungsreisende wird müde pro Zug verlängern sich die Kanten um 1, oder die Städte können nur zu einer bestimmten Zeit betreten werden, weil sie zum Beispiel nachts absperren, und ggf. müsste der Reisende warten (es geht hier jetzt nicht darum, ob das realistisch ist), also sprich, wenn die Kantenlänge von einer sich ändernden Variable abhängt?

[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.
Wenn du dich bisher noch nicht mit solchen Problemen befasst hast, wird es keine gute Idee sein, von Anfang an mit zusätzlichen Problemen zu arbeiten, TSP ist schon (NP-)schwer genug.

[3_of_8]

Es ist noch nicht bewiesen, aber es wird vermutet, dass TSP NP-schwer ist und dass es deshalb eine exponentielle Laufzeitkomplexität hat. Du hast n! Möglichkeiten, deine Route zu wählen, und du musst alle durchprobieren und n! verhält sich asymptotisch wie sqrt(n)*n^n.

Also ich denke mal, deine untere und obere Schranke dafür, wie das ganze skaliert, ist sqrt(n)*n^n. Außer vielleicht in Sonderfällen, du könntest zum Beispiel erstmal schauen, wie die Kostenverteilung (also die Entfernung) ist und wenn sie überall gleich ist, sind alle Lösungen gleichwertig, wodurch du einen Algorithmus hast, der für n skaliert - aber Sonderfälle bei einer Laufzeitbetrachtung heranzuziehen ist eher ungewöhnlich. Bei einer Sortierung hat man sonst auch eine untere Grenze von O(n), wenn die Folge schon sortiert ist.

[Cyf]

Ich meinte damit, dass es mit Hilfe Branch-and-Cut offenbar möglich ist eine Zeit zu errechnen, die auf keinen Fall unterschritten werden kann, somit kann man die Qualität einer Lösung abschätzen, oder falls man diese Zeit mit Hilfe von Heuristiken erreicht, somit weiß, dass man die bestmögliche Route gefunden hat und man aufhören kann.
Die Frage nach den zusätzlichen Schwierigkeiten zielt vorallem darauf ab, welche Verfahren bei soetwas noch funktionieren, falls man es einbauen wollte, weil ich das Gefühl habe, dass es da Probleme geben könnte. Zur Lösung selbst halte ich derzeit ACO noch für das einfachste, wobei ich eben auch da nicht weiß, ob es sich umbauen ließe, weil sich hier ja der die Gewichtung der Kanten ständig ändert (aber ACO geht hier jetzt am Thema vorbei).

[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.