Rucksackproblem: Erschöpfende Suche
Вставка
- Опубліковано 21 лип 2024
- Beim Rucksackproblem sollen in einen Rucksack möglichst wertvolle Objekten eingepackt werden, ohne dass der Rucksack dabei überladen wird. Eine optimale Lösung kann man z.B. mit einer erschöpfenden Suche finden, bei der einfach alle Packmöglichkeiten ausprobiert werden (rohe Gewalt = "brute force"). Aber wie zählt man dann überhaupt alle Auswahlmöglichkeiten auf? Das geht am besten rekursiv.
00:00 - Intro
00:19 - Optimales "Looten" in Games
01:45 - das Rucksackproblem
04:34 - Anwendungen des Rucksackproblems
06:08 - Beispiel vom Einbrecher mit Rückenschmerzen
08:12 - Erschöpfende Suche
14:11 - Teilmengen aufzählen
23:18 - Rucksackproblem rekursiv gelöst
29:04 - Optimierung durch Backtracking
- Backtracking: • Backtracking am Beispi...
Mehr zum Rucksackproblem:
- mit Branch & Bound: • Rucksackproblem: Branc...
- mit Dynamischem Programmieren und Approximation: • Rucksackproblem: Appro...
Sehr cool mit der Skyrim Einführung
Danke! Zugabe! Zugabe! ;)
Der Gaming Bereich ist durchaus ein sehr seriöser Bereich, wenn man sich die immer weiter steigenden Umsätze ansieht! ;-) Auch das hat wirtschaftliches Potenzial!
Es geht in der Wissenschaft nicht nur um Umsatz. Und egal in welchem Medium oder Bereich ist die Unterhaltungsbranche nunmal weniger seriös zu sehen als der andere shit.
Als 2 Arrays… Wie schließe ich dann wieder auf das zurück, was tatsächlich ausgewählt wurde? Diese Info geht bei dem Pseudo-Code völlig verloren.
Intuitiv habe ich schon etwas Ähnliches umgesetzt, wonach in einer (das weiß ich seit heute durch diesen Kanal) Map die entsprechenden Daten als assoziatives (multidimensionales) Array vorliegen. Dabei ist die Struktur bereits der Baum und traversieren ist dann eher “selektionsartig”.
Um den Algorithmus etwas übersichtlicher zu machen, habe ich das Problem so gestellt, dass er nur den maximalen Wert der ausgewählten Objekte berechnen soll, nicht aber welche Objekte das sind. Im Fall der erschöpfenden Suche ist es aber leicht, den Algorithmus so anzupassen, dass er sich die (bzw. eine) optimale Objektauswahl merkt: Immer, wenn wir eine bessere Auswahlmöglichkeit gefunden haben, merken wir uns nicht nur den neuen maximalen Gesamtwert G, sondern auch noch die Auswahlmenge S als Kopie in einer extra Variable.
@@Gogol-Doering , vielen Dank.
Ich weiß nicht, ob es da nur mir so geht, aber das Abstraktionslevel wird durch die “Vereinfachung” explosionsartig potenziert. Ich habe nichts gegen Abstraktion, allerdings war die Frage “und welche Dinge sind das nun” so ablenkend und überlagernd, dass ich extreme Konzentrationsprobleme hatte. 😆😆 Da es ein Video ist, kann man es immer wieder ansehen. In einer Vorlesung wäre ich hoffnungslos überfordert gewesen. ❤️