853 Branch & Bound fuer TSP

Dr Franke Ghostwriter
Auf Seite 40 unten werden fuer P1, P2 und P3 die untereren Schranken z1, z2 und z3 berechnet.

Da ich bei z1 4 als untere Schranke berechne, bin ich mir nicht sicher, ob ich nicht einen Denkfehler habe. Wie berechnet man z1 im Detail?

Mein Ansatz:
z1 = min{4, 7, 3} + min{2, 4, 9, 3, 6, 1, 4}
z1 = 3 + 1 = 4

In Worten: Minimum der ersten Zeile ohne c12 und c13, da unendlich, + das Minimun von Spalten 2 und 3 ohne c12 und c13.

Haut fuer z2 und z3 sowie fuer B0201 auch so hin, aber irgendwie scheints fuer z1 nicht zu stimmen.

Wer kann mir helfen? Danke schon mal!
 
Du betrachtest laut 2.14 beim 2. Term nur die Spalte mit dem Index Bild von i - also phi(i).

Im Beispiel gibt es einen Teilzyklus (1,2,3), d.h. es gilt:
i = 1 => phi(i) = 2
i = 2 => phi(i) = 3
i = 3 => phi(i) = 1

Somit betrachtest Du also für z1 laut Formel 2.14 - 2. Term nur das Minimum der Elemente in der 2. Spalte.

Also:
z1 = min{4, 7, 3} + min{2, 4, 9, 3} = 5

O.K.?

Gruß Franz
 
Du betrachtest laut 2.14 beim 2. Term nur die Spalte mit dem Index Bild von i - also phi(i).

Im Beispiel gibt es einen Teilzyklus (1,2,3), d.h. es gilt:
i = 1 => phi(i) = 2
i = 2 => phi(i) = 3
i = 3 => phi(i) = 1

Somit betrachtest Du also für z1 laut Formel 2.14 - 2. Term nur das Minimum der Elemente in der 2. Spalte.
...

Hallo Franz,

ja, phi(1)=2, daher die zweite Spalte, aber ich dachte, da fuer P1 nicht nur c12=unendlich, sondern auch c13=unendlich ist, nehme ich beide Spalten, denn schliesslich kann die untere Schranke auch durch Wege nach 3 erhoeht werden, denn die schliesse ich von 1 mit c13=unendlich aus.

Ich sollte vielleicht besser nach (2.13) und (2.14) rechnen, ohne eigene Ueberlegungen anzustellen 😉

Danke nochmal.
Gruss,
Juergen.
 
Juergen,
Ich sollte vielleicht besser nach (2.13) und (2.14) rechnen, ohne eigene Ueberlegungen anzustellen 😉
Im Zweifelsfall einfach stur die Formeln anwenden 😀 Allerdings ist der Formalismus im Skript doch etwas gewöhnungsbedürftig und führt leicht zu Kopfschmerzen 🙄

Ich habe mir angewöhnt, Formeln und Algorithmen doppelt "verstehen" zu wollen:
1. Formale Berechnung/Anwendung des Algorithmus
2. Was macht die Formel bzw. der Algorithmus eigentlich? Mittels Skizze oder Notiz...

Aber so eine Aufgabe "Branch and Bound für TSP" in der Klausur wäre doch nett :dafuer:

Gruß Franz
 
Oben