Bei der algorithmischen Methode Branch & Bound ("Verzweigen und Begrenzen") werden alle Äste des Suchbaums "abgeschnitten", bei denen man sicher sein kann, dass dort keine optimale Lösung zu finden ist. Dazu wird vor dem Abstieg in einen Ast des Baumes eine obere Schranke für die Qualität der Lösungen in diesem Ast berechnet, und mit der besten bislang gefundenen Lösung verglichen. Die Methode wird hier am Beispiel des Rucksackproblems gezeigt.
00:00 - Intro
00:19 - Einleitung
00:51 - Beispiel Rucksackproblem: Einbrecher mit Rückenschmerzen
04:47 - Erschöpfende Suche mit Backtracking
07:27 - Beispiel für Branch & Bound
12:30 - Branch & Bound in Pseudocode
- Tiefensuche: https://youtu.be/W9FHgw0S5O0
- Erschöpfende Suche: https://youtu.be/ujhi2h70qIw
- Backtracking: https://youtu.be/MILZhs5ilQs
Mehr zum Rucksackproblem:
- mit Erschöpfender Suche: https://youtu.be/ujhi2h70qIw
- mit Dynamischem Programmieren und Approximation: https://youtu.be/CiX_eG0dXBo
