Verzweigen und Begrenzen

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Loading

Inhaltsverzeichnis

Einführung

Als Branch-and-Bound(Verzweigung und Schranken) bezeichnet man eine ganzzahlig lineare Optimierungsmethode der Graphentheorie bzw. Kombinatorik der diskreten Mathematik .
Diese Optimierungen formulieren eine lineare Zielfunktion über einer Menge, beschränkt durch (Un)Gleichungen.
Alle Knoten eines Graphen stellen solch eine Menge dar und mittels verzweigen bzw beschränken in Teilgraphen, können sie in lineare Zielfunktionen abgebildet werden.
Rene Branch-andBound1.jpg
Lineare Abbildungen als Vektorräume über den selben Körper
Rene Branch-andBound3.jpg
Es ist kein Verfahren um einen neue Baum aus bestehenden Graphen zu erstellen, sondern eine Behandlungsmethode die den Ausgangsgraph verzweigt bzw. beschränkt.
Solche eine Behandlungsmethode wird auch als Metaverfahren bezeichnet.
Branch-and-Bound findet im Bereich Operations Research Anwendung, welcher sich zum Beispiel mit Optimierungsrechnung beschäftig und Verzweigen-Beschränken läßt sich als genau solche Optimierungsmethode kategorisieren.
Das Verfahren wurden 1960 von A. H. Land und A. G. Doig entwickelt und unterliegt über die Jahren ständiger Weiterentwicklung.

Prinzip

2 Grundprinzipien des Branch-and-Bound-Verfahrens(Minimierung):

Verzweigung(Branch)
Der Ausgangsgraph wird in disjunkte Teilmengen aufgeteilt.
Beschränkung(Bound)
Errechne bei Maximierungsproblem die obere Schranke bzw. bei Minimalproblemen die untere Schranke.
Zu jedem Verzweigungsschritt wird die Schranke mittels (Un)Gleichung bestimmt.

Verzweigung

Bei der Verzweigung werden von einem Knoten des Entscheidungsbaumes aus zwei oder mehr Teilprobleme erzeugt. Die Art der Aufspaltung in Teilprobleme hängt immer vom betrachteten Problem ab. Es gibt verschiedene Auswahlverfahren für die Wahl des nächsten zu bearbeitenden Knotens im Aufteilungsbaum, die unterschiedliche Zielsetzungen haben. Die haeufigste verwendete Methoden sind Tiefensuche und Breitensuche


Tiefensuche

Okyanus Depth-First-Search.gif


Mit dieser Auswahlregel arbeitet sich das Verfahren im Baum möglichst schnell in die Tiefe .
Hier geht man so weit wie möglich einen gewählten Pfad entlang. Wenn man am Ende eines Zweiges angekommen ist, geht man schrittweise zurück, bis man in einen bislang unbesuchten Teilbaum absteigen kann. Ist man wieder am Startknoten angelangt und es gibt keine unbesuchten Knoten, die mit dem Startknoten durch eine Kante verbunden sind, dann ist man fertig.
Dieses Verfahren nennt man Backtracking: Man geht solange man kann, wenn man nicht mehr weiter kommt, geht man zurück bis man einen anderen Weg findet.


Algorithmus

DFS(node, goal)
{
 if (node == goal) {
   return node;
 } else
 {
   stack := expand (node)
   while (stack is not empty)
   {
     node' := pop(stack);
     DFS(node', goal);
   }
 }
}

Laufzeit

Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen; Worst-case Laufzeit

 ; Anzahl der Knoten
 ; Anzahl der Kanten

Breitensuche

Breadth-First-Search-Algorithm.gif
Die Breiten Suche (breadth-first search) ist ein Algorithmenmuster, das die Knoten eines Graphen nach der Entfernung von einem Startknoten geordnet durchläuft. Zuerst werden alle von diesem Startknoten direkt durch eine Kante erreichbaren Knoten bearbeitet, danach die mit zwei Kanten Entfernung, dann die mit drei usw.
-Knoten werden in der Reihenfolge mit zunehmenden Abstand vom Startknoten aus besucht.
-Nachdem alle Knoten mit Abstand d verarbeitet wurden, werden die mit d + 1 angegangen.
-Die Suche terminiert, wenn in Abstand d keine Knoten auftreten.
-Die Tiefe des Knotens v im Breitensuchbaum ist seine kürzeste Kantendistanz zum Startknoten.
-Die zu verarbeitenden Knoten werden als FIFO-Queue (first-in first-out) organisiert.
-Es gibt eine einzige „Verarbeitungsmöglichkeit“ für v, nämlich, wenn es aus der Queue entnommen wird

Algorithmus

BFS(start_node, goal_node) {
 return BFS'({start_node}, ∅, goal_node);
}
BFS'(fringe, visited, goal_node) {
 if(fringe == ∅) {
   // Knoten nicht gefunden
   return false;
 }
 if (goal_node ∈ fringe) {
   return true;
 }
 return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node);
}

Laufzeit

Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen; Worst-case Laufzeit

 ; Anzahl der Knoten
 ; Anzahl der Kanten

Beschränkung (Bound)

Für das Gesamtproblem, also die Wurzel des Baumes, wird eine Wertschranke (bound) bestimmt. Hierbei kann es sich, in Abhängigkeit der Frage, ob das geforderte Optimum maximal oder minimal ist, um eine obere- oder untere Schranke (upper bound, lower bound) handeln. Kann Anfangs keine Grenze bestimmt werden, so gilt $bound = \infty$. Für jeden weiteren aus einem branch-Schritt expandierten Knoten wird wiederum eine Schranke bestimmt. Abhängig davon, ob ein Optimum maximaler- oder minimaler Gestalt gesucht wird, stehen verschiedene Verfahren zur Ermittlung der Wertschranke zur Verfügung. Die Schranke gibt an, dass für den aktuellen Knoten $v_i$ mit Wertschranke $bound_{v_i}$ kein durch Expansion erzeugter Folgeknoten $v_{i+n}$ mit $bound_{v_{i+n}} > bound_{v_i}$ existiert. 

  für maximales Optimum:
  $Ubound_{v_i}$von$\qquad v_i\colon \enspace \nexists v_{i+n}\mid Ubound_{v_{i+n}} > Ubound_{v_i}\mid n\in \mathbb{N}$
  für minimales Optimum:
  $Lbound_{v_i}$von$\qquad v_i\colon \enspace \nexists v_{i+n}\mid Lbound_{v_{i+n}} < Lbound_{v_i}\mid n\in \mathbb{N}$

In jedem Fall besagt die Wertschranke, dass es für das jeweilige Teilproblem keine bessere Lösung geben wird. In der Regel handelt es sich bei der Schranke um einen Näherungswert, an dem man sich orientieren kann. Es gilt stets eine Heuristik zu finden, welche unter möglichst linearem Aufwand einen Wert liefert, der gleichzeitig nicht zu grob ist und somit das Ergebnis hinreichend gut repräsentiert. Die perfekte Balance zu finden ist äußerst schwierig und für manche Probleme kaum möglich. In der Regel muss man sich sehr lange und intensiv mit einem Problem beschäftigen, um in die Nähe einer Brauchbaren Boundberechnung zu gelangen.

Herangehensweise

Im Folgenden wird die Herangehensweise und ein grandioser Irrtum dargestellt (welchem der Bearbeiter dieses Abschnittes ebenfalls zum Opfer fiel).

Jeder Expandierte Knoten, welcher keine endgültige Lösung darstellt, wird zwischengespeichert. Die Schranke des Aktuell betrachteten Knoten wird stets mit der des ersten in der Prioritätsliste verglichen. Ist die des Knotens in der Prioritätsliste besser, so wird der aktuelle Knoten gespeichert und der vielversprechendere Knoten der Prioritätsliste entnommen.

Flikkes First.gif


Jeder Expandierte Knoten, welcher keine endgültige Lösung darstellt, wird zwischengespeichert. Die Schranke des Aktuell betrachteten Knotens wird stets mit der des ersten in der Prioritätsliste verglichen. Ist die des Knotens in der Prioritätsliste besser, so wird der aktuelle Knoten gespeichert und der vielversprechendere Knoten der Prioritätsliste entnommen.

Im folgenden Beispiel wird spätestens beim Betrachten der gesamten Struktur des Baumes das Potenzial von Branch and Bound klar.

Flikkes Second.gif


Man darf aus der Idee des Verfahrens und der Motivation, große Probleme erheblich zu verkleinern, keine falschen Schlüsse ziehen:

Leider ist es nicht so einfach...

Offensichtlich können zunächst ignorierte Knoten nicht einfach entsorgt werden, da sie immer noch Lösungen bieten können, die Besser als die zunächst erhaltene sind. Somit können Probleme nach anfänglicher Verkleinerung wieder wachsen. Zwar ist diese Erkenntnis sehr ernüchternd, da im schlimmsten Fall keine Verkürzung der Rechenzeit erreicht wird, aber mit Blick auf average und best case, welche ja durchaus eintreten können, ist es natürlich lohnenswert ein Verfahren mit dem Potenzial der Verkürzung der Rechenzeit anzuwenden.

Rucksackproblem

Das Rucksackproblem ist ein Optimierungsproblem der Kombinatorik. Von Lösungsalgorithma her das Rucksackproblem ist einer der bekanntesten NP-Hard Probleme.

Es sei es gibt 'n' Gegenstände mit den Gewichten $ g_1,g_2 , \cdots , g_n $ und werten $ w_1, w_2 , \cdots , w_n $ . Gewicht der i ten Gegenstand ist $g_i$ und Wert der i ten Gegenstand ist $w_i$ Die Interpretation des Wertes wird durch den jeweiligen Sachkontext bestimmt.

Das aktuelle Gesamtgewicht des Rucksacks darf die Maximalkapazitaet , sei K , nicht übersteigen.

Mathematische Schreibweise der 0/1 Rucksackprobleme ;

$ \sum_{i=1}^n {x_i}{ω_i} $ -> max , wobei $ \sum_{i=1}^n{x_i}{g_i} \leq K $ mit $x_i \in $ {0,1}

Mit anderen Wörtern Rucksackproblem ist ; Ein Rucksack soll mit einer Auswahl von n Gegenständen unterschiedlichen Gewichts und Werts gefüllt werden. Wie muss die Auswahl getroffen werden, damit das Gesamtgewicht ein Grenzgewicht nicht überschreitet und der Gesamtwert möglichst hoch ist?
Es gibt vier Typen von der Rucksack Probleme
1)Jeder Gegenstand wird entweder vollstaendig in den Rucksack genommen (1) oder nicht gepackt (0) .
2) Es darf ein beliebiger teil t , mit 0% $ \leq $t $ \leq $ 100% , jedes Gegenstands eingepackt werden.
3)Unbeschränktes Rucksackproblem: Bei dieser Variante des Problems gibt es keine Kapazitätsobergrenze, d.h. $K = \infty$.
4)Teilmengen-Summen-Problem (subset-sum problem): In diesem speziellen Fall geht es darum die Gewichtskapazität des Rucksacks optimal auszunutzen, da der Wert mit dem Gewicht übereinstimmt, d.h. $g_i = w_i$ für alle $i$.

kleine Übung 1

Wir haben einen Dieb der maximal 1KG. gewicht mitnehmen kann. Was soll man in der Liste auswaehlen, damit das Gesamtgewint nicht schwerer als 1KG wird und Gesamtwert möglichst hoch ist ?

Okyanus Örnek.jpg

Lösung :

kleine Übung 2

Wir wollen zum Einkaufen gehen und wir haben eine Tüte die maximal 10 Kg. tragen kann, welche Kombination von Gemüsen sollen wir kaufen, damit wir möglichst Gesamtwert in unserer Tüte haben können ?
Okyanus Örnek2.JPG

Lösung :

Dynamische Programmierung

Divide & Conquer
1) Den Problem zu Teilprobleme teilen.
2) Die Teilprobleme lösen.
3) Die ergebnisse wieder kombinieren.
Bemerkung : Falls die Teilprobleme nicht unabhaengig sind , Subprobleme würden zu Subsubprobleme führen. Danach müssen wir mit diesem Alghoritmus Subsubprobleme lösen. Es waere eine große Zeitverschweundung.
Frage : Gibt es bessere Lösung?
JA! Dynamische Programmierung
Dynamische Programmierung ist eine Lösungsweg für Optimisierung Probleme.

Idee

Die Subsubprobleme berechnen und die ergebnisse in der Tabelle schreiben damit die wieder nutzen zu können.


Erklaerung mit einem Beispiel

Wir haben einen Rucksack , der maximal 5 KG tragen kann.

Okyanus Örnek3.jpg


Implementierung

http://www.dosya.tc/server6/zjmh2h/rucksack.rar.html

Greedy Algorithmus

Der erste Ansatz der einem Anfänger einfällt ist meistens ein Greedy-Algorithmus. Greedy bedeutet, dass man eine Bewertungsfunktion für die optimale Auswahl verwendet. In unserem Fall, bei Rucksackprobleme , müssen wir auf die Wert/Gewicht Rate achten. Je höher der Wert/Gewicht desto eher für uns den Artikel zu nehmen.
Okyanus Örnek4.JPG


Wie hier oben, auf dem Bild steht, rechnet man das Wert/Gewicht und schreibt die auf der Tabelle um sehen zu können welche Elemente bzw. Gegenstaende wertvoller sind.

Rekursion

Greedy Alghoritmus Lösung ist eigentlich sehr schön und nutzbar aber es ist nicht immer die optimale Lösung. Um das beste Ergebnis sicher zu finden kann man Rekursions Weg nehmen. Für jeden Gegenstand haben wir 2 Möglichkeiten: In den Rucksack oder nicht. Wahr oder falsch. Es dauert viel laenger als Greedy Alghoritmus aber gibt immer die beste Ergebniss aus.
Okyanus Adsız.png

Schluß

Knapsack bzw. Rucksack Problem ist einer der beliebsten Bespiele bei Algorithmen. Man kann damit Lektionen zur effizienten Implementierung eines Algorithmus lernen.Rekursion ist eines der grundlegenden Mitteln der Programmierung.

Traveling Salesman Problem

Problem des Handlungsreisenden(engl. Traveling Salesman Problem/Traveling Salesperson Problem(TSP))
Ein Handlungsreisender bereist geschäftlich mehrer Orte und möchte aus finanziellen Gründen eine möglichst geringe Reisestrecke.
Die Methoden des TSP in praktischer Anwendung, errechnen die kürzeste Strecke zwischen verschieden Punkten, in dem Fall Städte.
Beispiel: Handelsvertreter, Reisetouren, Pannendienst, etc.
Modelierung
Um das Problem des Handlungsreisenden zu lösen, ist es notwendig das ganze als Graphentheoretisches Modell darzustellen.
Allgemein bekannt, besteht solch ein Model aus zwei Komponenten: den Knoten und Kanten.
Die Knoten sind hierbei die einzelnen Städte und Kanten die Verbindung zwischen ihnen.
Die Gewichte der einzelnen Kanten sind hierbei die geographischen Länge zwischen den Städten, allgemein als Maß Kilometer festgelegt.
Dieser Graph ermöglicht dann die mathematische Untersuchung mittels diverser Techniken.
symetrisches/asymetrisches TSP
symetrisches: Beim symetrischen TSP ist der Graph ungerichtet. Das heißt, das er in beide Richtungen durchlaufen werden kann und die Reisetouren in beide Richtungen die gleiche Strecke besitzen.
asymetrisches: Ein gerichteter Graph ist beim asymetrischen TSP die Modelgrundlage. Mit gerichtet ist gemeint, daß die Kante die zwei Knoten verbindet in nur eine Richtung durchschritten werdem kann.
Metrisches TSP
Ein Modell wird als metrisch eingestuft, wenn die Länge der verschiedenen Kanten einen geometrischen Satz Namens Dreieckungleichung erfüllt.
Rene Bb2.jpg
Lösungsansatz
Prinzipiell kann man mittels ausprobieren zu einer Lösung kommen, aber der Aufwand ist selbst bei geringer Städteanzahl astronomische.
Als Beispiel der Aufwand bei asymethrischen TSP.
Aufwand bei 5 Städten = 12
Aufwand bei 10 Städten = 181.440
Aufwand bei 15 Städten = 43.589.145.600
Aufwand bei 20 Städten = 60.822.550.204.416.000
Aufwand bei 100 Städten = 1*10^156
Rechnerisch per Hand: unmöglich!!!

Daraus läßt sich die Formel für die asmethrische Aufwand ermitteln:
(n-1)!/2
Die Formel für den symethrischen Aufwand lautet ähnlich:
(n-1)!
Exakte Lösungsverfahren
Branch-and-Cut,
Dem Branch-and-Bound Verfahren ähnlich, beschränkt die Methode nicht den Baum, sondern bedient sich einem Schnittebenen-Verfahren.
Wurde später als das Branch-and-Bound Verfahren entwickelt und wird als eine der Standartmethoden des TSP eingestuft.
Heuristiken
In der Heuristik versucht man mit wenig bzw. unvollständigen Wissen dennoch die richtige Lösung zu finden(heurisko „ich finde").
Es sind mutmaßliche Schlussfolgerungen, die nicht frei von Fehlern sind.
Ergebniss wird in Optimierungsschritten verbessert.


kleine Übung

TSP für 5 Städte mittels Distanzmatrix

http://new-lv.de/distanzma.jpg

Maximum Satisfiability Problem

Das Max-Sat-Problem beschäftigt sich mit der Frage, für welche boolsche Wertbelegung von Literalen $x_0, x_1, ..., x_n$ und Klauseln der Normalform $(x_i \lor x_j \lor x_l) \land (x_{i+n} \lor x_{j+n} \lor x_{l+n})$ mit $\quad m = \quad \mid Klauseln \mid \quad$, für $s \leq m$ gilt: $s$ ist maximal. Max-Sat gehört zur Klasse NP-Schwer. An diesem Problem lässt sich sehr schön die Schwierigkeit der Findung einer brauchbaren Approximationsfunktion für eine sinnvolle Begrenzung, sowie einer sinnvollen Verzweigungsstrategie darstellen. Max.Sat gehört zu den NP-Schweren Problemen. Hier schnell eine brauchbare Lösung zu finden wäre viel wert. Um den Umfang ein wenig zu begrenzen betrachten wir ausschließlich Max-2-Sat-Probleme, bei welchen eine Klausel höchstens zwei Literale enthalten darf. Zusätzlich legen wir fest, dass pro Klausel jedes Literal nur einmal vorkommen darf. Auch Max-2-Sat wird den NP-Schweren Problemen zugeordnet.

Beispiel

Gegeben seien drei Literale $x_0, x_1, x_2$ das Gesamtproblem besteht aus fünf Klauseln: $(x_0\lor x_2)\land (\lnot x_0\lor x_1)\land (x_0\lor x_1)\land (x_1\lor x_2)\land (\lnot x_1\lor x_2)$ 

  Verzweigungsstrategie START: von der Wurzel wird für x-Belegungen $(x_o\quad x_1\quad x_2)$, abhängig von der Anzahl der TRUEs, eine
  eigene Verzweigung angelegt. 
  Verzweigungsstrategie NICHT START: vom Knoten wird für jede mit der jeweiligen Anzahl von TRUEs $k_T$ fehlende Kombination eine
  Verzweigung erstellt.
  Upper Bound WURZEL: Anzahl der Klauseln $m$
  Lower Bound NICHT WURZEL: $(1-(\frac{1}{2^{k_T}}))\cdot m$

Für ein Problem, welches mithilfe von Branch and Bound gelöst werden soll, können auch beide Schrankentypen eingesetzt werden. Gelegentlich ist eine Globale Obergrenze trivial, wohingegen sich im weiteren Verlauf für jeden expandierten Knoten eher eine Untergrenze (oft in Gestalt einer LP-Relaxation) anbietet. In diesem Fall sagt sie Untergrenze: "Schlechter wird das Ergebnis nicht".

Es ergibt sich nun folgender Baum:

Flikkes Maxsat1.png

Bis heute gibt es zur Boundbestimmung für Max-Sat-Probleme unterschiedliche Herangehensweisen und viele Schwierigkeiten, da häufig Hybride entstehen, deren Interpretation Rechenzeit in Anspruch nimmt und die von Außenstehenden nicht so leicht zu durchschauen sind.

kleine Übung

  • Schauen Sie sich den Baum an und vollziehen Sie jeden Expansionsschritt nach
  • Bauen Sie für das Problem $(\lnot x_0\lor \lnot x_1)\land (x_1\lor x_2)\land (\lnot x_1\lor x_2)\land (x_0\lor \lnot x_2)\land (\lnot x_0\lor x_1)\land (x_0\lor x_2)$ mit der im Beispiel eingeführten LB-Funktion einen Lösungsbaum auf.
  • Machen Sie sich klar, wann welcher Knoten Expandiert wird
  • Ist die erwartete Optimallösung tatsächlich optimal?
  • Welche Auswirkung hat das Hinzufügen von Klauseln auf den Baum, welche das Hinzufügen von Literalen?
  • Lösen Sie $(\lnot x_0\lor \lnot x_1)\land (x_0\lor \lnot x_1)\land (\lnot x_1\lor x_2)\land (\lnot x_0\lor x_2)\land (\lnot x_1\lor \lnot x_2)$ mit der Funktion $(1-(\frac{1}{2^{k_T}\cdot \frac{k_T}{k_F}}))\cdot m$ zur Berechnung der Untergrenze

Quellen

Christian Wagenknecht,

Algorithmen und Komplexität, Fachbuchverlag Leipzig, 2003

Rolf Wanka,

Approximationsalgorithmen, Teubner Verlag, 2006

Internet

https://de.wikipedia.org/wiki/Branch-and-Bound

https://en.wikipedia.org/wiki/Maximum_satisfiability_problem

http://www2.inf.fh-rhein-sieg.de/~pbecke2m/or/bandb1.pdf

Von „https://programmingwiki.de/Verzweigen_und_Begrenzen“
Persönliche Werkzeuge