Die Indizierung läuft dabei nicht über die erste Zeile; vor der Auswertung werden die erste Zeile und Spalte direkt aus der Instanz abgelesen.
ERMITTLUNG EINER OPTIMALEN AUSWAHL
Die beiden oben beschriebenen Algorithmen liefern zunächst nur den optimalen Zielfunktionswert, aber keine optimale Auswahl der Items. Deshalb haben wir zusätzlich Backtracking implementiert.
Dabei wird mit einem optimalen Zustand begonnen. Durch Vergleiche wird ermittelt, aus welchem Zustand er durch die jeweilige Rekurrenzgleichung entstanden sein kann. Dementsprechend wird das zur jeweiligen Zeile des Zustandsraums gehörende Item entweder mit in die Auswahl aufgenommen (oder nicht) und es wird zum Vorgängerzustand übergegangen. Dieser Schritt wird so lange iteriert, bis wir in der ersten Zeile des Zustandsraums angekommen sind.
Das Backtracking ist für beide Algorithmen relativ leicht zu implementieren und hat jeweils eine lineare Laufzeitschranke.
IMPLEMENTIERUNG
Wir haben beide Algorithmen in
C# implementiert
10, wobei die Indizierung der Items natürlich bei 0 und nicht bei 1 beginnt. In der jeweils auszuwertenden Zeile des Zustandsraums können die Einträge unabhängig voneinander (und somit durch verschiedene Threads) ermittelt werden. Da es vergleichsweise einfach war, haben wir also beide Algorithmen parallelisiert.
Zusätzlich haben wir einen Preprocessing-Schritt
11 vorangestellt, der vor der eigentlichen Lösung der Instanz diejenigen Items entfernt, auf die in einer optimalen Lösung verzichtet werden kann. Genauer sind dies Items mit Profit 0 oder kapazitätsüberschreitendem Gewicht und Items mit geringem Profit innerhalb einer Gewichtsklasse.
Schließlich haben wir mithilfe von Linq
12 den oben erwähnten Backtracking-Schritt implementiert.
Wir haben die Implementierung auf einer Instanzbibliothek
13 mit bekannten Optima getestet
14. Wer möchte, kann das gerne selbst ausprobieren. Dazu müssen die als „Small Coefficients“ klassifizierten Instanzen
15 ins Verzeichnis gleichen Namens kopiert werden.
Die Auswertungen sind als Komponententests implementiert und können z.B. in Visual Studio über MSTest gestartet werden. Es ist dabei allerdings zu beachten, dass die Implementierungen sehr speicherintensiv sind, da der Zustandsraum explizit dargestellt wird.
FAZIT
Der erste Ansatz, bei dem das Gewicht abgezählt wird, ist etwas unmittelbarer, da das maximale Gewicht einer optimalen Lösung direkt aus der Instanz abgelesen werden kann und die Werte der Zustände direkt den Zielfunktionswerten von zulässigen Lösungen entsprechen. Beim zweiten Ansatz hingegen muss eine Schranke für den optimalen Profit erst künstlich erzeugt werden, was durch Relaxierung oder einen Approximationsalgorithmus möglich ist.
Allerdings wachsen sowohl die Laufzeit als auch der Speicherbedarf beider Algorithmen exponentiell an. Die Laufzeitschranken sind zwar polynomiell in der Anzahl der Items beschränkt, aber es gehen Zahlenwerte der Items
16 in die Laufzeitschranken ein, sodass diese dennoch exponentiell in der Länge ihrer Eingaben wachsen können.
Die implementierten Algorithmen können in diesem Sinne nicht als effizient angesehen werden
17, was bei einem NP-schweren Optimierungsproblem
18 aber auch nicht zu erwarten war.
Effiziente Algorithmen (wie etwa der
PowerOpt , der grundsätzlich ebenfalls für Packungsprobleme des hier vorgestellten Typs geeignet ist) haben ein wesentlich günstigeres Skalierungsverhalten. Sie erfüllen ggf. sogar Echtzeit-Anforderungen.
Schließlich sei noch der Vollständigkeit halber darauf hingewiesen, dass der zweite Algorithmus als Grundlage eines Approximationsschemas
19 verwendet werden kann, was bei dem ersten Algorithmus jedoch nicht möglich ist.
Weitere Artikel:
➡
TOPOLOGISCHE SORTIERUNG
➡
DAS RUCKSACKPROBLEM
➡
TRAVELING SALESPERSON PROBLEM
➡
GANTT CHARTS IN DER TOURENPLANUNG