Verzweigungs- und gebundene Erklärung

Ich habe einen Test über den Verzweigungs- und gebundenen Algorithmus. Ich verstehe theoretisch, wie dieser Algorithmus funktioniert, konnte aber keine Beispiele finden, die veranschaulichen, wie dieser Algorithmus praktisch implementiert werden kann.

Ich habe einige Beispiele wie dieses gefunden , bin aber immer noch verwirrt. Ich suchte auch nach einem Problem mit reisenden Verkäufern und konnte es nicht verstehen.

Was ich brauche, sind einige Probleme und wie können diese Probleme mithilfe von branch and bound gelöst werden.

Wenden wir Branch and Bound auf Knapsack an . Hoffentlich wird Ihnen dies das Konzept klar machen.

Wir haben Artikel mit den Bezeichnungen 1 bis n . v i ist der Wert des i- ten Elements und w i sein Gewicht. Wir versuchen, sie in einen Rucksack zu passen, der insgesamt bis zu T Gewicht enthalten kann , und wir versuchen, die Summe der Werte des Gegenstands, den wir in den Rucksack legen, zu maximieren.$n$$1$$n$$v_i$$i$$w_i$$T$

Der gewöhnliche Backtrack-Ansatz ist unsere Basis. Wir legen zuerst in die Packung und lösen dann das Problem für die verbleibenden n - 1 Elemente mit Rekursion. Wir entfernen dann v 1 aus dem Paket und lösen das Problem für die verbleibenden n - 1 Elemente erneut und geben die beste Konfiguration zurück, die wir gefunden haben.$v_1$$n-1$$v_1$$n-1$

Dieses Backtracking ist der 'Branch'-Teil von Branch and Bound. Sie verzweigen sich (im Fall von Knapsack) in zwei Fällen: "Element ist Teil der Lösung" und "Element i ist nicht Teil der Lösung". Sie können dies als binären Baum visualisieren, wobei das linke Kind ein Fall und das rechte Kind der andere Fall ist. Dieser Baum ist der Suchbaum$i$$i$ (oder Suchraum ): Seine Tiefe beträgt , und er hat daher O ( 2 n ) Knoten. Der Algorithmus hat daher eine exponentielle Laufzeit in der Anzahl der Elemente.$n$$O(2^n)$

Jetzt kommen wir zum Teil 'Gebunden': Wir versuchen, Kriterien zu finden, bei denen wir sagen können, dass diese Konfiguration niemals funktioniert, also könnten wir uns genauso gut nicht die Mühe machen, dies zu berechnen. Ein Beispiel für ein solches Kriterium ist "das Gewicht der Gegenstände, die wir bereits in den Rucksack gelegt haben, überschreitet ": Wenn wir beispielsweise die ersten n / 2 Gegenstände zum Rucksack hinzugefügt haben und dieser daher bereits voll ist, gibt es Es macht keinen Sinn, zu versuchen, die Gegenstände n / 2 + 1 bis n im Rucksack zu platzieren, aber es macht auch keinen Sinn, zu versuchen, eine Teilmenge von n / 2 + 1 bis n zu passen$T$$n/2$$n/2+1$$n$$n/2+1$$n$im Rucksack, da er bereits voll ist, sparen wir also ca. Fälle. Ein anderes Beispiel ist " Selbst wenn ich alle verbleibenden Elemente eingebe, überschreitet der Wert der Elemente, die ich eingegeben habe, nicht die beste Konfiguration, die ich bisher gefunden habe ".$2^{n/2}$

Diese Kriterien schneiden im Wesentlichen Teile des Suchbaums ab: An einem Knoten sagen Sie beispielsweise "Der linke Teilbaum gibt mir keine bessere Konfiguration, weil X", sodass Sie diesen Teilbaum vergessen und ihn nicht untersuchen. Ein Teilbaum der Tiefe , den Sie auf diese Weise ausschneiden, spart Ihnen O ( 2 d ) Knoten, was mit etwas Glück eine ziemliche Geschwindigkeitssteigerung bedeuten kann.$d$$O(2^d)$

Beachten Sie, dass dies als " Begrenzung " bezeichnet wird, da es sich normalerweise um eine Art Unter- oder Obergrenze handelt: Für das Kriterium " Selbst wenn ich alle verbleibenden Elemente eingebe, überschreitet der Wert der Elemente, die ich eingegeben habe, nicht die beste Konfiguration." Ich habe bisher festgestellt , dass der Wert Ihrer besten Konfiguration bisher eine Untergrenze für die beste Konfiguration ist. Alles, was diese Untergrenze niemals überschreitet, ist zum Scheitern verurteilt.

Sie können den Teil "Bounding" so komplex gestalten, wie Sie möchten. Zum Beispiel werden ganzzahlige Programmierprobleme häufig durch Relaxationen gelöst: Sie entspannen Ihr Programm zu einem linearen Programm, das Sie in Polynomzeit lösen können, und dann können Sie viele Fälle für Ihre binären Variablen wegwerfen, die sowieso nie funktionieren. Anschließend verzweigen Sie in die verbleibenden Optionen.

Beachten Sie, dass Branch and Bound in der Praxis normalerweise nur zu einer Geschwindigkeitssteigerung führt, theoretisch jedoch nicht: Es ist schwer zu sagen, wie viel des Suchbaums mithilfe Ihrer Heuristiken ausgeschnitten wird. Dies wird durch die Anzahl der verschiedenen Heuristiken belegt, die in der Praxis für solche Probleme verwendet werden. Wenn Sie Pech haben, bleibt der verbleibende Suchbaum trotz vieler Einschränkungen riesig.

Betrachten Sie die Zeitplanung , die Aufgabe, Maschinen Jobs mit bestimmten Dauern und Fristen zuzuweisen. Wir nehmen diskrete Zeit an. Viele solcher Probleme sind NP (O) -hart.

$1 \mid r_i \mid L_\max$

• auf einer Maschine
• Probleme mit Veröffentlichungsterminen und wir
• Minimieren Sie die maximale Verspätung , dh die maximale Differenz zwischen Frist und Abschlusszeit für alle Jobs.$L_\max$

Die Entscheidungsversion dieses Problems ist NP-schwer; Dies kann durch Reduktion von 3PARTITION gesehen werden .

Interessanterweise kann das Problem in quadratischer Zeit durch die früheste Heuristik des ersten Fälligkeitsdatums (an geänderten Fälligkeitsterminen) gelöst werden , wenn wir die Vorauszahlung zulassen , dh aktive Jobs austauschen. Es ist leicht zu erkennen, dass die optimale Lösung dieser Variante nicht schlechter sein kann als die optimale Lösung des ursprünglichen Problems.

Um Branch & Bound auf dieses Problem anzuwenden, müssen wir einige Parameter korrigieren:

• Wir berechnen Untergrenzen, indem wir Preemption zulassen und EDD verwenden.
• Wir verzweigen uns, indem wir alle außerplanmäßigen Jobs als nächsten reparieren.
• Wir gehen zuerst mit kleinen Untergrenzen zu dem Kind.

Sie müssen dies für jede Anwendung von B & B tun.

Betrachten Sie als konkretes Beispiel diese Instanz von :$1 \mid r_i \mid L_\max$

$\qquad \displaystyle \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline p_i & 4 & 2 & 6 & 5 \\ r_i & 0 & 1 & 3 & 5 \\ d_i & 8 & 12 & 11 & 10 \end{array}$

mit die Bearbeitungszeiten der Jobs, die Veröffentlichungsdaten und die Fälligkeitstermine.r i d $p_i$$r_i$$d_i$

Wenn Sie B & B wie oben angegeben ausführen, geschieht Folgendes:

_{Dieses GIF wird nicht wiederholt. Laden Sie es in einer neuen Registerkarte neu, um es von Anfang an zu sehen.}
^{[ Quelle ] [ statische Version ]}

Beachten Sie, dass von 41 Knoten nur vier ordnungsgemäß besucht werden und nur für zehn untere Grenzen berechnet werden.