Ziel der Arbeit ist es, einen Einblick in die kombinatorische Optimierung und im Speziellen in das Rucksackproblem zu geben, um ein Verständnis der Thematik zu ermöglichen. Zudem sollen weitergehend verschiedene Lösungsansätze erläutert werden.
In der diskreten Mathematik gibt es einige noch ungelöste Probleme, welche allgemein als Optimierungsprobleme der Kombinatorik bezeichnet werden. Es geht hierbei jeweils darum, aus einer Menge an Elementen eine Reihenfolge festzulegen, welche die geforderten Bedingungen möglichst genau erfüllen. Hierbei gibt es meist nur bis zu einem gewissen Punkt genaue und exakte Lösungen, da man hierfür alle Kombinationen) durchgehen muss. Somit lässt sich meist nur eine Annäherung an die tatsächliche Lösung bestimmen.
Eines dieser kombinatorischen Optimierungsprobleme ist das Rucksackproblem. Dabei muss ein Rucksack mit Gegenständen gefüllt werden. Jeder Gegenstand besitzt einen bestimmten Wert und ein Volumen beziehungsweise. ein Gewicht. Ziel ist es den Rucksack so zu füllen, dass der Inhalt einen maximalen Wert ergibt, ohne das Gesamtvolumen beziehungsweise Gesamtgewicht des Rucksacks zu überschreiten. Für eine überschaubare Anzahl an Gegenständen, lässt sich das Problem recht einfach lösen. Nehmen diese jedoch zu, so steigen die Möglichkeiten exponentiell an, wodurch das genaue Ergebnis selbst mit den schnellen Computern der heutigen Zeit nicht bestimmt werden kann, da dies zu große Zeitspannen in Anspruch nehmen würde.
Der historische Hintergrund und der Bezug zu den anderen Problemen der kombinatorischen Optimierung sollen in weiteren Abschnitten aufgezeigt werden. Der Schwerpunkt der Arbeit soll aber auf den Lösungsansätzen und Algorithmen liegen. Zunächst soll der Greedy-Algorithmus, welcher auch als Profitabilitätsindex bezeichnet wird, erläutert werden. Darauffolgend werden weitere Approximationsalgorithmen zur Lösung des Problems wie den Nemhauser Algorithmus, den Backtrackingalgorithmus und die dynamische Programmierung vorgestellt, ausführlich beschreiben und mit Beispielen untermalt. Anhand dessen soll auch aufgezeigt werden, warum es nicht immer möglich ist, eine genaue Lösung zu finden und es sich meist um Näherungslösungen handelt.
Das Fazit zu den beschriebenen Algorithmen soll den Abschluss der Seminararbeit bilden.
Inhaltsverzeichnis
- Einleitung
- Allgemeines
- Erläuterung der Problematik
- Historischer Hintergrund und Bezug zu anderen Problemen
- Greedy-Algorithmus
- Algorithmus von Nemhauser und Ullmann
- Dynamische Programmierung
- Backtracking
- Zusammenfassung
- Quellenverzeichnis
Zielsetzung und Themenschwerpunkte
Diese Seminararbeit befasst sich mit dem Rucksackproblem, einem kombinatorischen Optimierungsproblem, das in der diskreten Mathematik eine wichtige Rolle spielt. Die Arbeit zielt darauf ab, dem Leser ein umfassendes Verständnis des Problems zu vermitteln, indem sie die Problematik erläutert, den historischen Hintergrund beleuchtet und verschiedene Lösungsansätze sowie Algorithmen vorstellt.
- Erläuterung des Rucksackproblems und seiner Bedeutung in der Kombinatorik
- Historische Entwicklung und Zusammenhang mit anderen NP-vollständigen Problemen
- Vorstellung und Analyse verschiedener Approximationsalgorithmen wie Greedy-Algorithmus, Nemhauser Algorithmus, Backtracking und dynamische Programmierung
- Bedeutung und Herausforderungen der kombinatorischen Optimierung bei der Suche nach optimalen Lösungen
- Praktische Anwendung des Rucksackproblems in verschiedenen Alltagsbeispielen
Zusammenfassung der Kapitel
- Einleitung: Die Einleitung führt in die Welt der kombinatorischen Optimierungsprobleme ein und stellt das Rucksackproblem als ein prominentes Beispiel vor. Sie beleuchtet die Problematik, dass exakte Lösungen bei großen Problemgrößen nicht praktikabel sind und Approximationsalgorithmen notwendig werden. Die Arbeit fokussiert sich auf die Lösungsansätze und Algorithmen.
- Allgemeines: Dieses Kapitel vertieft die Erläuterung des Rucksackproblems. Es wird ein Beispiel mit konkreten Werten gegeben, um die Problematik zu veranschaulichen. Der historische Hintergrund und der Bezug zu anderen NP-vollständigen Problemen werden ebenfalls beleuchtet.
Schlüsselwörter
Kombinatorische Optimierung, Rucksackproblem, NP-vollständig, Greedy-Algorithmus, Nemhauser-Algorithmus, Backtracking, Dynamische Programmierung, Approximationsalgorithmen, NP-Probleme, Entscheidungsprobleme, Exakte Überdeckung, Traveling Salesman Problem (TSP), Behälterproblem (Bin-Packing), Millennium-Probleme, Polynomialer Algorithmus.
- Quote paper
- Maximilian Schanz (Author), 2018, Das Rucksackproblem. Ein Optimierungsproblem der Informatik, Munich, GRIN Verlag, https://www.grin.com/document/453267
