Partitionsproblem - Partition problem

In der Zahlentheorie und Informatik , das Partitionsproblem oder Anzahl Partitionierung , ist die Aufgabe , ob ein bestimmte entscheiden multiset S von positiven ganzen Zahlen können aufgeteilt in zwei Teilmengen S 1 und S 2 , so dass die Summe der Zahlen in S 1 equals die Summe der Zahlen in S 2 . Obwohl das Partitionsproblem NP-vollständig ist , gibt es eine pseudopolynomialzeitdynamische Programmierungslösung , und es gibt Heuristiken, die das Problem in vielen Fällen entweder optimal oder näherungsweise lösen. Aus diesem Grund wurde es "das einfachste schwierige Problem" genannt.

Es gibt eine Optimierungsversion des Partitionierungsproblems, die darin besteht, die Multimenge S in zwei Teilmengen S 1 , S 2 zu unterteilen, so dass die Differenz zwischen der Summe der Elemente in S 1 und der Summe der Elemente in S 2 minimiert wird. Die Optimierungsvariante ist NP-hart , kann aber in der Praxis effizient gelöst werden.

Das Partitionsproblem ist ein Sonderfall von zwei verwandten Problemen:

  • Beim Teilmengensummenproblem besteht das Ziel darin, eine Teilmenge von S zu finden, deren Summe eine bestimmte Zielzahl T als Eingabe ist (das Partitionsproblem ist der Spezialfall, bei dem T die Hälfte der Summe von S ist ).
  • Bei der Mehrweg-Zahlenpartitionierung gibt es einen ganzzahligen Parameter k , und das Ziel besteht darin, zu entscheiden, ob S in k Teilmengen gleicher Summe partitioniert werden kann (das Partitionsproblem ist der Spezialfall, bei dem k = 2).
  • Es ist jedoch ganz anders als beim 3-Partitionsproblem : Bei diesem Problem ist die Anzahl der Teilmengen nicht im Voraus festgelegt - sie sollte | . sein S |/3, wobei jede Teilmenge genau 3 Elemente haben muss. 3-Partition ist viel schwieriger als Partition - sie hat keinen pseudopolynomialen Zeitalgorithmus, es sei denn, P = NP .

Beispiele

Gegeben S = {3,1,1,2,2,1} ist eine gültige Lösung des Partitionsproblems die beiden Mengen S 1 = {1,1,1,2} und S 2 = {2,3}. Beide Mengen summieren sich auf 5, und sie partitionieren S . Beachten Sie, dass diese Lösung nicht eindeutig ist. S 1 = {3,1,1} und S 2 = {2,2,1} ist eine weitere Lösung.

Nicht jede Mehrfachmenge von positiven ganzen Zahlen hat eine Aufteilung in zwei Teilmengen mit gleicher Summe. Ein Beispiel für eine solche Menge ist S = {2,5}.

Rechnerische Härte

Das Partitionsproblem ist NP-schwer. Dies kann durch Reduktion aus dem Teilmengensummenproblem bewiesen werden . Eine Instanz von SubsetSum besteht aus einer Menge S von positiven ganzen Zahlen und einer Zielsumme T < S; das Ziel ist zu entscheiden, ob es eine Teilmenge von S mit der Summe genau T gibt .

Konstruieren Sie für eine solche Instanz eine Instanz von Partition, in der die Eingabemenge die ursprüngliche Menge plus zwei Elemente enthält: z 1 und z 2 , mit z 1 = sum(S) und z 2 = 2 T. Die Summe dieser Eingabemenge ist sum(S)+ z 1 + z 2 = 2 sum(S)+2 T, also ist die Zielsumme für Partition sum(S) + T.

  • Angenommen, es existiert eine Lösung S' für die SubsetSum-Instanz. Dann sum(S')=T, also sum(S' u { z 1 }) = sum(S) + T, also ist S' u { z 1 } eine Lösung für die Partitionsinstanz.
  • Angenommen, es existiert eine Lösung S'' für die Partitionsinstanz. Dann muss S'' entweder z 1 oder z 2 enthalten , aber nicht beide, da ihre Summe größer ist als sum(S) + T. Wenn S'' z 1 enthält , dann muss es Elemente aus S mit einer Summe von . enthalten genau T, also ist S'' minus z 1 eine Lösung der SubsetSum-Instanz. Wenn S'' z 2 enthält , muss es Elemente aus S mit einer Summe von genau sum(S)-T enthalten, also sind die anderen Objekte in S eine Lösung der SubsetSum-Instanz.

Näherungsalgorithmen

Wie oben erwähnt, ist das Partitionsproblem ein Spezialfall der Mehrweg-Partitionierung und der Teilmengensumme. Daher kann es durch Algorithmen gelöst werden, die für jedes dieser Probleme entwickelt wurden. Zu den für die Mehrweg-Nummernpartitionierung entwickelten Algorithmen gehören:

  • Gierige Zahlenpartitionierung - Schleift über die Zahlen und fügt jede Zahl in die Menge ein, deren aktuelle Summe am kleinsten ist. Wenn die Zahlen nicht sortiert sind, ist die Laufzeit O( n ) und das Approximationsverhältnis höchstens 3/2 ("Approximationsverhältnis" bedeutet die größere Summe in der Algorithmusausgabe geteilt durch die größere Summe in einer optimalen Partition). Das Sortieren der Zahlen erhöht die Laufzeit auf O( n log n ) und verbessert das Näherungsverhältnis auf 7/6. Wenn die Zahlen gleichmäßig in [0,1] verteilt sind, dann ist das Näherungsverhältnis höchstens fast sicher undin Erwartung.
  • Die größte Differenzierungsmethode (auch Karmarkar-Karp-Algorithmus genannt ) sortiert die Zahlen in absteigender Reihenfolge und ersetzt die Zahlen wiederholt durch ihre Differenzen. Die Laufzeitkomplexität beträgt O( n log n ). Im schlimmsten Fall ist sein Näherungsverhältnis ähnlich - höchstens 7/6 . Im durchschnittlichen Fall schneidet er jedoch viel besser ab als der Greedy-Algorithmus: Wenn Zahlen gleichmäßig in [0,1] verteilt sind, ist sein Näherungsverhältnis höchstenszu erwarten. Es schneidet auch in Simulationsexperimenten besser ab.
  • Der Multifit-Algorithmus verwendet eine binäre Suche kombiniert mit einem Algorithmus für das Bin Packing . Im schlimmsten Fall beträgt sein Näherungsverhältnis 8/7 .
  • Das Teilmengensummenproblem hat einen FPTAS, der auch für das Partitionsproblem verwendet werden kann, indem die Zielsumme auf sum( S )/2 gesetzt wird.

Genaue Algorithmen

Es gibt exakte Algorithmen , die immer die optimale Partition finden. Da das Problem NP-schwer ist, können solche Algorithmen im Allgemeinen eine exponentielle Zeit in Anspruch nehmen, können aber in bestimmten Fällen praktisch anwendbar sein. Zu den für die Mehrwegnummernpartitionierung entwickelten Algorithmen gehören:

  • Die pseudopolynomiale Zeitzahlpartitionierung benötigt Speicher, wobei m die größte Zahl in der Eingabe ist.
  • Der Complete Greedy Algorithm (CGA) berücksichtigt alle Partitionen, indem er einen Binärbaum erstellt . Jede Ebene im Baum entspricht einer Eingabenummer, wobei die Wurzel der größten Zahl entspricht, die darunter liegende Ebene der nächstgrößeren Zahl usw. Jeder Zweig entspricht einer anderen Menge, in die die aktuelle Zahl eingefügt werden kann. Das Durchqueren des Baums in der Tiefe erster Ordnung erfordert nur Platz, kann aber Zeit in Anspruch nehmen . Die Laufzeit kann durch eine gierige Heuristik verbessert werden: Entwickeln Sie in jeder Ebene zuerst den Zweig, in dem die aktuelle Zahl in die Menge mit der kleinsten Summe gelegt wird. Dieser Algorithmus findet zuerst die Lösung, die durch gierige Zahlenpartitionierung gefunden wurde , sucht dann aber nach besseren Lösungen. Einige Variationen dieser Idee sind Approximationsschemata in vollständig polynomieller Zeit für das Teilmengen-Summen-Problem und somit auch für das Teilungsproblem.
  • Der Complete Karmarkar-Karp Algorithmus (CKK) berücksichtigt alle Partitionen, indem er einen binären Baum konstruiert. Jede Ebene entspricht einem Zahlenpaar. Der linke Zweig entspricht dem Einfügen in verschiedene Teilmengen (dh dem Ersetzen durch ihre Differenz), und der rechte Zweig entspricht dem Einordnen derselben in die gleiche Teilmenge (dh dem Ersetzen durch ihre Summe). Dieser Algorithmus findet zuerst die Lösung, die durch die größte Differenzierungsmethode gefunden wurde, fährt dann jedoch fort, bessere Lösungen zu finden. Es läuft in zufälligen Instanzen wesentlich schneller als CGA. Sein Vorteil ist viel größer, wenn eine gleiche Aufteilung existiert und kann mehrere Größenordnungen haben. In der Praxis können Probleme beliebiger Größe durch CKK gelöst werden, wenn die Zahlen höchstens 12 signifikante Stellen haben . CKK kann auch als jederzeitiger Algorithmus ausgeführt werden : Er findet zuerst die KK-Lösung und findet dann nach und nach bessere Lösungen, wenn es die Zeit erlaubt (in den schlimmsten Fällen möglicherweise exponentielle Zeit, um die Optimalität zu erreichen). Es braucht Platz, kann aber im schlimmsten Fall Zeit in Anspruch nehmen .

Zu den für die Teilmengensumme entwickelten Algorithmen gehören:

  • Horowitz und Sanhi – läuft in der Zeit , braucht aber Platz.
  • Schroeppel und Shamir - läuft in der Zeit und benötigt viel weniger Platz - .
  • Howgrave-Graham und Joux - läuft in der Zeit , aber es ist ein randomisierter Algorithmus , der nur das Entscheidungsproblem (nicht das Optimierungsproblem) löst.

Harte Instanzen und Phasenübergang

Sätze mit nur einer oder keinen Partitionen sind im Vergleich zu ihren Eingabegrößen in der Regel am schwierigsten (oder am teuersten) zu lösen. Wenn die Werte im Vergleich zur Größe des Sets klein sind, sind perfekte Partitionen wahrscheinlicher. Das Problem durchläuft bekanntlich einen „ Phasenübergang “; für einige Sätze wahrscheinlich und für andere unwahrscheinlich. Wenn m die Anzahl von Bits ist, die benötigt wird, um eine beliebige Zahl in der Menge auszudrücken, und n die Größe der Menge ist, dann tendiert dazu, viele Lösungen zu haben und neigt dazu, wenige oder keine Lösungen zu haben. Wenn n und m größer werden, geht die Wahrscheinlichkeit einer perfekten Partition auf 1 bzw. 0. Dies wurde ursprünglich auf der Grundlage empirischer Beweise von Gent und Walsh argumentiert, dann mit Methoden der statistischen Physik von Mertens und später von Borgs , Chayes und Pittel bewiesen .

Wahrscheinlichkeitsversion

Ein verwandtes Problem, das dem Geburtstagsparadoxon etwas ähnlich ist, besteht darin, die Größe der Eingabemenge so zu bestimmen, dass wir eine halbe Wahrscheinlichkeit haben, dass es eine Lösung gibt, unter der Annahme, dass jedes Element in der Menge zufällig mit uniform . ausgewählt wird Verteilung zwischen 1 und einem bestimmten Wert. Die Lösung für dieses Problem kann kontraintuitiv sein, wie das Geburtstagsparadoxon.

Varianten und Verallgemeinerungen

Eine Partition mit gleicher Kardinalität ist eine Variante, bei der beide Teile zusätzlich zur gleichen Summe die gleiche Anzahl von Elementen haben sollten. Auch diese Variante ist NP-hart, wie in Problem [SP12] gezeigt wurde. Siehe Partitionierung mit ausgeglichener Zahl .

Eine eindeutige Partition ist eine Variante, bei der alle Eingabe-Ganzzahlen unterschiedlich sind. Auch diese Variante ist NP-hart.

Produktpartitionierung ist das Problem der Partitionierung einer Menge von ganzen Zahlen in zwei Mengen mit dem gleichen Produkt (anstelle der gleichen Summe). Dieses Problem ist stark NP-schwer .

Kovalyov und Pesch diskutieren einen generischen Ansatz zum Nachweis der NP-Härte von Problemen vom Partitionstyp.

Anwendungen

Eine Anwendung des Teilungsproblems ist die Manipulation von Wahlen . Angenommen, es gibt drei Kandidaten (A, B und C). Ein einzelner Kandidat sollte nach einer Abstimmungsregel basierend auf der Punktzahl gewählt werden, zB der Vetoregel (jeder Wähler legt sein Veto gegen einen einzelnen Kandidaten ein und der Kandidat mit den wenigsten Vetos gewinnt). Wenn eine Koalition sicherstellen möchte, dass C gewählt wird, sollten sie ihre Stimmen auf A und B aufteilen, um die kleinste Anzahl von Vetos zu maximieren, die jeder von ihnen erhält. Wenn die Stimmen gewichtet werden, kann das Problem auf das Teilungsproblem reduziert und somit effizient mit CKK gelöst werden. Das gleiche gilt für jede andere Abstimmungsregel, die auf der Bewertung basiert.

Anmerkungen

Verweise