Definition · Begriff 3 von 25
Branch-and-Bound (B&B)
Ein Algorithmus für ganzzahlige und kombinatorische Probleme, der die Suche in Teilprobleme zerlegt und alle verwirft, die keine bessere Lösung enthalten können.
RechenbeispielEin Zweig fällt wegZweig A erreicht bestenfalls Kosten von 100. Ein Plan mit Kosten von 96 ist bereits bekannt. Zweig A wird verworfen, ohne ihn zu durchsuchen, und die Suche geht dort weiter, wo noch ein besserer Plan möglich ist.
In einfachen Worten
Branch-and-Bound teilt ein Problem in kleinere Teilprobleme (Branching) und berechnet für jedes eine Schranke für das bestmögliche Ergebnis. Kann diese Schranke die beste bisher gefundene Lösung nicht schlagen, fällt der ganze Zweig weg. So muss das Verfahren nicht jede Kombination prüfen und schließt am Ende trotzdem die Optimalitätslücke.
Branch-and-Bound, auf Ihre eigene Entscheidung angewandt.
Bringen Sie eine wiederkehrende Entscheidung ein. Ihre Planer sehen die Begriffe dieses Glossars, angewandt auf ihre eigenen Regeln und Daten.
- Glossar
- alle 25 Begriffe, A bis Z
- Problemtypen
- die Entscheidungen, die kint löst
- Vergleiche
- kint im Vergleich mit anderen Ansätzen
- Kontakt
- hello@kint.pro