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

==Tiefen Suche==
==Breiten Suche==

=Beschränkung=
Für jeden aus einem Verzweigungsschritt erzeugten Knoten wird eine Beschränkung, die sogenannte ''Wertschranke'', 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.
==Dominanz==

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