Verzweigen und Begrenzen

Wiki-Quelltext dieser Seite.

=Einführung=
==Prinzip==
=Verzweigung=
==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==