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