Verzweigen und Begrenzen

Wiki-Quelltext dieser Seite.

=Einführung=
==Prinzip==
=Verzweigung=

Bei der Verzweigung werden von einem Knoten des Entscheidungsbaumes aus zwei oder mehrTeilprobleme 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==
[[Bild: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.

==Breitensuche==
: [[Bild:Breadth-First-Search-Algorithm.gif]]
  
: Die Breiten Suche  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

=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 eine untere Schranke (upper bound, lower bound) handeln.
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.
   
==Naive Herangehensweise==
Im Folgenden wird eine Herangehensweise in Kombination mit einem grandiosen Irrtum dargestellt (welchem der Bearbeiter dieses Abschnittes zum Opfer fiel).
<popup name="Einfaches Beispiel">
[[Bild:Flikkes_1stBoundEx.gif]]
<popup name="Erläuterung">
Es ist zu beachten, dass es sich bei diesem Beispiel um ein Worst-Case-Szenario handelt.
</popup>
<popup name="Größeres Beispiel">
[[Bild:Flikkes_2ExComplicated.gif]]
<popup name="Erläuterung">
Das Problem konnte verkleinert werden.
</popup>
Spätestens beim Anschauen der zweiten Animation sollte der (vermeintliche) Vorteil von Branch and Bound klar sein. Große Probleme können so extrem verkleinert und mit weniger Kosten gelöst werden. Leider ist es nicht ganz so einfach, wie die dritte Animation (eine Abwandlung der Ersten in diesem Unterpunkt) deutlich zeigt.
<popup name="Bittere Wahrheit des Einfachen Beispiels">
[[Bild:Flikkes_4thBoundEx.gif]]
<popup name="Erläuterung">
Offensichtlich können zunächst ignorierte Knoten nicht einfach ''entsorgt'' werden.
</popup>
Zwar ist diese Erkenntnis sehr ernüchternd, jedoch ist noch nicht alles Verloren. Die Lösung heißt ''Prioritätswarteschlange'' (priority queue).

==Dominanztest==

=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}


==kleine Übung==

=Traveling Salesman Problem=
==kleine Übung==
=Maximum Satisfiability Problem=
==kleine Übung==