Rucksackproblem: Approximation NP-schwerer Probleme

Manche NP-schweren Probleme lassen sich beliebig gut näherungsweise lösen, andere nicht. Wir zeigen hier ein einfaches Approximationsschema für das ganzzahlige Rucksackproblem. Sobald man erlaubt, dass die gefundene Näherungslösung auch nur ein klein wenig (um einen beliebig wählbaren Faktor alpha) von der optimalen Lösung abweichen darf, kann man im Falle des Rucksackproblems eine derartige Näherungslösung in polynomieller Zeit berechnen. Das ist sehr erstaunlich, denn das Rucksackproblem ist ja NP-schwer 00:00 - Intro 00:19 - Einführung Rucksackproblem 03:39 - Lösungsansätze Überblick 07:43 - Lösung mit Dynamischem Programmieren 22:15 - Beispiel DP-Matrix 28:22 - Sparse Dynamic Programming 51:07 - Approximation des ganzzahligen Rucksackproblems 57:38 - Was ist ein alpha-Approximationsalgorithmus? 58:28 - Parameterwahl und Laufzeitabschätzung 1:05:52 - Beweis der Approximationsgüte 1:13:59 - Fazit und Schluss Mehr zu NP-schweren Problemen: - Einführung zum Thema NP-schwer: https://youtu.be/spUTwAbcw9o - Traveling Salesman Problem: https://youtu.be/bRVARQ0s3dw Mehr zum Rucksackproblem: - mit Erschöpfender Suche: https://youtu.be/ujhi2h70qIw - mit Branch & Bound: https://youtu.be/Zz7hmnpOXEI