Komplexitätsbetrachtungen

Ein Algorithmus zur Lösung des Rucksackproblems

Wir betrachten weiterhin den folgenden Algorithmus zur Lösung des Rucksackproblems:

ALGORITHMUS optimaleLoesung:
    Übergabe:
    erzeuge eine erste kombination, z.B. '00000000'
    maxKombination = kombination
    maxWert = Gesamtwert von kombination
    SOLANGE noch nicht alle Kombinationen durchlaufen sind:
        erzeuge eine neue kombination
        WENN der Gesamtwert von kombination > maxWert und
             das Gesamtgewicht von kombination <= grenzgewichtRucksack:
            maxKombination = kombination
            maxWert = Gesamtwert von kombination
    Rückgabe: (maxKombination, maxWert, Gesamtgewicht von maxKombination)

Komplexität des Algorithmus

Eine naive Beschreibung der Komplexität des oben gezeigten Algorithmus geht von folgenden Annahmen aus:

Die Problemgröße wird durch die Anzahl n der Gegenstände festgelegt.

Als Kostenmaß wählen wir die Anzahl der zu untersuchenden Kombinationen. Es ergibt sich dann die Kostenfunktion K(n) = 2ⁿ.

Diese Kostenfunktion ist eine Exponentialfunktion. Der Algorithmus hat demnach eine exponentielle Komplexität.

Komplexität des Problems

Ob das Rucksackproblem selbst eine exponentielle Komplexität hat, ist hierdurch noch nicht erwiesen. Es könnte Algorithmen geben, die das Problem viel schneller - z.B. mit polynomialer Komplexität - lösen.

Tatsächlich gibt es einen Algorithmus, der das Rucksackproblem viel effizienter als der oben gezeigte Algorithmus bearbeiten. Er beruht auf der Idee, dass man das Problem, einen Rucksack bei n Gegenständen optimal zu packen, auf das Problem, einen Rucksack bei n-1 Gegenständen optimal zu packen, reduzieren kann.

Analysiert man die Komplexität dieses Algorithmen, so erweist sich die oben vorgenommene naive Problembeschreibung als inadäquat. Man muss die Größe und Verarbeitung der insgesamt 2n+1 zu verarbeitenden Ausgangszahlen differenzierter betrachten. Insbesondere muss man berücksichtigen, dass sinnvollerweise die Rucksackkapazität mit wachsender Anzahl von Gegenständen auch wachsen sollte. Es erweist sich dann, dass bei diesem Algorithmus trotz großer Verbesserungen dennoch eine exponentielle Komplexität vorliegt.

Alle bis heute entwickelten Algorithmen zur Lösung des Rucksackproblems haben eine exponentielle Komplexität. Es ist kein Algorithmus bekannt, der das Rucksackproblem mit polynomialem Zeitaufwand löst. Vieles spricht dafür, dass das Rucksackproblem nicht zur Klasse der Probleme mit polynomialer Komplexität gehört. Eine endgültige Klärung dieser Komplexitätsfrage ist noch nicht gelungen.

Näherungsverfahren zur Lösung des Problems

Probleme, für die es keine effizienten Algorithmen gibt, müssen dennoch sehr häufig in der Praxis gelöst werden. Wenn keine praktikablen Verfahren zur exakten Lösung des Problems bekannt sind, weicht man oft auf Näherungsverfahren aus, sofern diese hinreichend gute Lösungen liefern. Wir werden im folgenden Abschnitt ein solches Näherungsverfahren genauer betrachten, das beim Rucksackproblem und auch bei vielen anderen Optimierungsproblemen eingesetzt werden kann.