Branch-and-Bound
Results 1 to 4 of 4
  1. #1

    Title
    Hero
    Join Date
    Feb 2002
    Posts
    178
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Branch-and-Bound

    Hallo!

    Kennst sich von euch jemand beim Bsp. Branch-and-Bound für das assymmetrische TSP im Skriptum aus?

    lg

  2. #2

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Ich weisz nicht genau, wo die Probleme sind, also fange ich einfach
    mal irgendwo an.

    Distanzmatrix:
    In der i-ten Zeile sind die Werte wieviel es kostet, vom Knoten
    j (spalte) _zum_ Knoten i zu kommen und in der i-ten Spalte stehen
    die Kosten um _vom_ Knoten i zum Knoten j zu kommen. Oder auch
    umgekehrt ;-p (Definitionssache).

    Bounding:

    (a) Zeilenreduktion
    Hierbei wird fuer jeden Knoten ermittelt zu welchem anderen Knoten
    man am guenstigsten hinkommt. Man sucht sich den kleinsten Wert in
    der Zeile und zieht diesen dann von allen Werten in der Zeile ab.
    Dann steht bei den billigsten Kanten (zum Knoten i) jeweils 0. Diese
    Kanten moechten wir in diesem Schritt auf jeden Fall benutzen,
    deshalb zaehlen wir den Wert zur unteren Schranke L fuer das
    Teilproblem dazu.

    (b) Spaltenreduktion
    Eigentlich das gleiche wie bei der Zeilenreduktion, jetzt suchen
    wir alle Kanten mit denen man am billigsten von den Knoten wegkommt.
    Auch diese Knoten wollen wir auf jeden Fall benutzen, also wird
    der Wert der billigsten Kante zu L addiert.

    Wir haben jetzt also jeweils die biligsten Kanten hinzugefuegt.
    Wenn nun die untere Schranke L nicht kleiner ist, als die globale
    obere Schranke U, koennen wie die Loesung sofort verwerfen, weil
    es ja schon eine gueltige, mindestens so gute Loesung gibt.

    Wenn das Gesamtgewicht passt, muss noch geprueft werden, ob die
    gewaehlten Kanten (vereinigt mit den Kanten in "EINS", also den
    Kanten die auf jeden Fall in die Loesung kommen muessen) ueberhaupt
    eine gueltige Loesung ergeben, also ob schon eine Rundtour existiert.

    Wenn eine existiert, dann ist das in diesem Schritt berechnete L
    besser als das globale Optimum U (sonst haetten wir es ja
    verworfen) und deswegen koennen wir U = L setzten und alle
    Teilprobleme aus der Liste entfernen deren untere Schranke groeszer
    ist als L. Diese Loesung merken wir uns als vorlaeufig beste Loesung.

    Branching:

    Wenn keine Rundtour existiert, erstellt man zwei neue Teilprobleme.
    Das eine indem man eine Kante fix dazunimmt (in "EINS" aufnimmt, und
    aus den Mengen der verfuegbaren Zeilen und Spalten entfernt), und das
    andere in dem man die Kante fix nicht dazunimmt (in "NULL" aufnehmen
    und den Wert c_ij in der matrix auf unendlich setzten (dann kann sie
    nie eine minimale Kante werden)). Dann beginnt man wieder von vorne.
    Sobald keine ungeloesten Teilprobleme mehr in der Queue sind ist man
    fertig.

    Zum Plausibilitaetskriterium:
    Eigentlich kann man eine beliebige Kante nehmen, die nicht in "EINS"
    und die minimal ist (der Eintrag c_ij in der Distanzmatrix C ist 0).

    Wenn man aber "geschickt" Kanten auswaehlt kommt man frueher zu
    einer hoeheren globalen Oberschranke -> es fallen mehr ungeeignete
    Loesungen weg. Das Plausibilitaetskriterium im Skriptum sucht immer
    je zwei Knoten, bei denen man einen groszen Umweg machen muss wenn
    man nicht die Kante nimmt die sie direkt verbindet.

    Ich weisz nicht, ob ich jetzt das abgedeckt habe was dir unklar war, aber
    das Thema ist schriftlich etwas muehsam zu behandeln. Vielleicht treffen
    sich noch ein paar Leute vor der Pruefung.

  3. #3

    Title
    Hero
    Join Date
    Feb 2002
    Posts
    178
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi,

    danke für deine ausführliche Erklärung. Ein Treffen wäre nicht schlecht.

    Eine Frage hätte ich noch, könntest du das mit der Kante (4,2)
    so erklären, wie im Buch mit der Kante (2,6)?

    Danke, nochmals für die Hilfe.

    lg

  4. #4

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts
    so weit so gut, aber was ich nicht verstehe is woher man das U bekommt...

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •