Partitionsproblem - LinkFang.de





Partitionsproblem


Das Partitionsproblem (auch Zahlenaufteilungsproblem, oft mit PARTITION notiert) ist ein Optimierungs- bzw. Entscheidungsproblem der Kombinatorik.

Formulierung des Partitionsproblems

Die Aufgabenstellung beim Partitionsproblem lautet: Gegeben sei eine (Multi-)Menge von natürlichen Zahlen. Gesucht wird eine Aufteilung dieser Zahlen auf zwei Haufen, so dass die Differenz der Summen der Zahlen in den beiden Haufen möglichst klein ist.

Eine äquivalente Formulierung lautet präziser: Gegeben sei eine (Multi-)Menge A von N natürlichen Zahlen [math]a_i[/math]. Gesucht wird eine Untermenge [math]A_1 \subset A[/math], so dass

[math] E := \left| \sum_{a_i \in A_1} a_i - \sum_{a_i \in A \setminus A_1} a_i \right| [/math]

minimal wird. Eine Aufteilung, für die [math]E = 0[/math] ist, heißt perfekte Aufteilung.

Als zusätzliche Bedingung kann man die Lösungsmenge des Partitionsproblems von vornherein einschränken, indem man nur ausgewogene Aufteilungen zulässt, in denen beide Haufen gleich groß sind, das heißt die Anzahl der Zahlen in den Untermengen muss für gerades N gleich sein und muss sich für ungerades N um 1 unterscheiden. Auch in diesem Fall ist das Partitionsproblem [math]\mathcal{NP}[/math]-Vollständig.[1]

Wandelt man die Fragestellung ab und fragt, „Gibt es eine perfekte Aufteilung?“, so wird das oben beschriebene Optimierungsproblem zu einem Entscheidungsproblem. Dabei sucht man nicht mehr nach der besten Aufteilung, sondern fragt nur noch nach deren Existenz.

Das Partitionsproblem gehört zu den 21 klassischen NP-vollständigen Problemen[2], von denen Richard M. Karp 1972 die Zugehörigkeit zur Klasse der NP-vollständigen Probleme zeigen konnte.

Phasenübergang im Partitionsproblem

Man beobachtet beim Partitionsproblem zwei verschiedene sogenannte Phasen: Besteht die Menge A aus vielen kleinen Zahlen, so ist anschaulich klar, dass es viele perfekte Aufteilungen gibt, und es einfach ist, eine dieser Aufteilungen zu finden (einfache Phase). Besteht A hingegen aus wenigen großen Zahlen, so ist es unwahrscheinlich, dass überhaupt eine perfekte Aufteilung existiert, und man muss alle Möglichkeiten durchprobieren, um die beste Aufteilung zu finden (harte Phase).

Zwischen der einfachen und der harten Phase beobachtet man einen Übergang, den man in Analogie zur statistischen Physik Phasenübergang nennt. An diesem Phasenübergang fällt die Wahrscheinlichkeit, eine perfekte Aufteilung zu finden, sprunghaft von 1 in der einfachen Phase auf 0 in der harten Phase. Mit wachsender Anzahl N der Zahlen wird der Übergang immer schärfer.

Die Lage des Phasenübergangs in Abhängigkeit von der Anzahl und der Größe der einzelnen Zahlen lässt sich mit Methoden der statistischen Physik berechnen.

Alle momentan bekannten Algorithmen haben dabei eine „worst-case-Laufzeit“, die exponentiell mit der Anzahl der Zahlen N wächst, das heißt im schlimmsten Fall benötigt er zur Lösung des Entscheidungsproblem eine Rechenzeit, die exponentiell mit N ansteigt. In vielen Fällen liegt die tatsächlich benötigte Rechenzeit jedoch deutlich darunter: In der einfachen Phase stößt der Algorithmus schnell auf eine der vielen perfekten Lösungen und kann das Entscheidungsproblem somit mit „ja, es gibt eine perfekte Lösung“ beantworten und die Suche abbrechen. Auch in der harten Phase können geeignete Algorithmen (z. B. der cBLDM-Algorithmus[3]) die Suche schnell mit einer negativen Entscheidung abschließen, falls keine Lösung existiert. Die „schwierigsten“ Probleme liegen somit direkt am Phasenübergang, wo erst alle [math]2^{N-1}[/math] Aufteilungen durchprobiert werden müssen, bevor das Problem entschieden werden kann.

Lösung durch dynamische Programmierung

Mithilfe der dynamischen Programmierung kann man das Partitionsproblem in pseudopolynomieller Zeit entscheiden.[4] Hierbei werden systematisch kleinere Teilprobleme betrachtet und ihre Lösungen tabelliert und rekursiv zusammengefügt.

Sei [math]S[/math] die Summe aller gegebenen Zahlen. Falls sie ungerade ist, existiert offensichtlich keine perfekte Aufteilung. Andernfalls wird für alle [math]1 \leq i \leq N[/math] und alle [math]0 \leq j \leq S/2[/math] geprüft, ob es eine Auswahl von Zahlen in der Familie [math]\{a_1, a_2, ..., a_i\}[/math] der ersten [math]i[/math] Zahlen gibt, deren Summe genau [math]j[/math] ergibt. Für [math]i=1[/math] und [math]j=0[/math] ist dies offenbar der Fall, genauso für [math]i=1[/math] und [math]j=a_1[/math]. Für [math]i=1[/math] und alle anderen [math]j[/math] dagegen nicht. Dies ist der Anfang der Rekursion, der in der ersten Zeile einer Tabelle notiert wird. Für die weiteren Zeilen ergeben sich die Einträge nach folgender Rekursion: Eine Auswahl für [math](i, j)[/math] existiert genau dann, wenn entweder bereits eine für [math](i-1, j)[/math] existiert, oder wenn [math]j\gta_i[/math] ist und eine Auswahl für [math](i-1, j-a_i)[/math] existiert. Die Antwort auf das Entscheidungsproblem gibt der letzte Eintrag in der Tabelle (für [math]i=N[/math] und [math]j=S/2[/math]) an.

Die Komplexität dieses Algorithmus ist [math]\mathcal{O}(n \cdot S)[/math].

Literatur

Einzelnachweise

  1. Michael R. Garey, David Stifler Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5, S. 223.
  2. Michael R. Garey, David Stifler Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5, S. 47.
  3. S. Mertens: A complete anytime algorithm for balanced number partitioning, arXiv:cs/9903011
  4. Michael R. Garey, David Stifler Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5, S. 90–92.

Kategorien: Komplexitätstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Partitionsproblem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.