Verzweigen und Begrenzen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
=Einführung=
: Als Branch-and-Bound(Verzweigung und Schranken) bezeichnet man eine spezielle Optimierungsmethode in der Graphentheorie, welches nicht gewünschte Teilbäume aus einem Baum entfernt.
: Es ist kein Verfahren um einen neue Baum aus einem bestehenden Baum zu erstellen, sondern eine Behandlungsmethode die den Ausgangsbaum 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.
: [[Datei: Rene_Bb1.jpg]]
==Prinzip==
=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==
[[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
<language>Scheme</language>
=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.
==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.
[[Bild:Flikkes_First.gif]]
<popup name="Erläuterung">
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.
</popup>
<popup name="gesamte Baumstruktur">
[[Bild:Flikkes_Full.png]]
</popup>
Im folgenden Beispiel wird spätestens beim Betrachten der gesamten Struktur des Baumes das Potenzial von Branch and Bound klar.
[[Bild:Flikkes_Second.gif]]
<popup name="gesamte Baumstruktur">
[[Bild:Flikkes_Full2.png]]
</popup>
Man darf aus der Idee des Verfahrens und der Motivation, große Probleme erheblich zu verkleinern, keine falschen Schlüsse ziehen:
<popup name="kleiner Irrtum: ">
[[Bild:Flikkes_1stBoundEx.gif]]
<popup name="größerer Irrtum: ">
[[Bild:Flikkes_2ExComplicated.gif]]
<popup name="Erläuterung">
Das Problem konnte (scheinbar) mit Leichtigkeit verkleinert werden.
</popup>
Leider ist es nicht so einfach...
<popup name="Bittere Wahrheit">
[[Bild:Flikkes_4thBoundEx.gif]]
<popup name="Erläuterung">
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''.
</popup>
Zwar ist diese Erkenntnis, besonders nach Blick auf das zweite Beispiel, sehr ernüchternd, jedoch ist noch nicht alles Verloren. Zwei vielversprechende Lösungen heißen: ''Prioritätswarteschlange'' (priority queue) und ''tiefe zuerst'' (depth first).
==Speichern von Knoten==
Zunächst wollen wir noch einmal das 2. Beispiel aus dem vorigen Unterpunkt betrachten, diesmal jedoch leicht abgewandelt und mit der richtigen Herangehensweise.
<popup name="Allgemein gültige Herangehensweise">
[[Bild:Flikkes_ComplEx.gif]]
</popup>
=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 Zwei 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.
==kleine Übung 1==
: Wir haben einen Diebstahler 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 ?
[[Bild: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 ?
: [[Bild: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.
[[Bild:Okyanus_Örnek3.jpg]]
==Greedy Methode==
=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.
: [[Datei: Rene_Bb2.jpg]]
: '''Lösungsansatz'''
: Prinzipiell kann man mittels ausprobieren zu einer Lösung kommen, aber der Aufwand selbst bei geringer Städteanzahl ist astronomische.
: 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
: Rechnerisch per Hand: unmöglich!!!
: Um den Aufwand rechnerisch darzustellen, wurde die darunterstehende Scheme Prozedur erstellt.
<run id="5693d2706a5c1">
#lang racket
(define fak
(lambda(x)
(cond
[(= x 0)1]
[else(* x (fak(- x 1)))])))
(define TSP
(lambda(x)
(/(fak (- x 1))2)))</run>
==kleine Übung==
=Maximum Satisfiability Problem=
==kleine Übung==