Verzweigen und Begrenzen
Inhaltsverzeichnis |
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.