Partitionsproblem

Inom talteori och datavetenskap är partitionsproblemet , eller nummerpartitionering , uppgiften att avgöra om en given multimängd S av positiva heltal kan delas upp i två delmängder S ₁ och S ₂ så att summan av talen i S ₁ är lika med summan av talen i S ₂ . Även om partitionsproblemet är NP-komplett finns det en pseudopolynomisk tidsdynamisk programmeringslösning , och det finns heuristik som löser problemet i många fall, antingen optimalt eller ungefärligt. Av denna anledning har det kallats "det enklaste svåra problemet".

Det finns en _{optimeringsversion} av partitionsproblemet, vilket är att dela upp multiuppsättningen _S i _två delmängder Si , S2 så att skillnaden _mellan summan av element i S1 och summan av element i S2 minimeras. Optimeringsversionen är NP-hård , men kan lösas effektivt i praktiken.

Partitionsproblemet är ett specialfall av två relaterade problem:

I delmängdssummansproblemet är målet att hitta en delmängd av S vars summa är ett visst målnummer T givet som indata (partitionsproblemet är specialfallet där T är halva summan av S ).
I flervägsnummerpartitionering finns det en heltalsparameter k , och målet är att avgöra om S kan delas upp i k delmängder med samma summa (partitionsproblemet är specialfallet där k = 2).
Det är dock helt annorlunda än 3-partitionsproblemet : i det problemet är antalet delmängder inte fixat i förväg – det borde vara | S |/3, där varje delmängd måste ha exakt 3 element. 3-partition är mycket svårare än partition - den har ingen pseudopolynomisk tidsalgoritm om inte P = NP .

Exempel

Givet S = {3,1,1,2,2,1} är en giltig lösning på partitionsproblemet de två uppsättningarna S ₁ = {1,1,1,2} och S ₂ = {2,3}. Båda uppsättningarna summerar till 5, och de delar upp S . Observera att denna lösning inte är unik. S ₁ = {3,1,1} och S ₂ = {2,2,1} är en annan lösning.

Inte varje multimängd av positiva heltal har en partition i två delmängder med samma summa. Ett exempel på en sådan mängd är S = {2,5}.

Beräkningshårdhet

Partitionsproblemet är NP-svårt. Detta kan bevisas genom reduktion från delmängdssummaproblemet . En instans av DelmängdSumma består av en uppsättning S av positiva heltal och en målsumma T ; målet är att avgöra om det finns en delmängd av S med summan exakt T .

Givet en sådan instans, konstruera en instans av partition där indatamängden innehåller den ursprungliga mängden plus två element: z ₁ och z ₂ , med z ₁ = summa(S) och z ₂ = 2 T . Summan av denna ingångsmängd är summa( S ) + z ₁ + z ₂ = 2 sum( S ) + 2 T , så målsumman för partition är summa( S ) + T.

Anta att det finns en lösning S ′ till SubsetSum-instansen. Sedan summa( S ′) = T , så summa( S ′ u { z ₁ }) = summa( S ) + T , så S ′ u { z ₁ } är en lösning på partitionsinstansen.
Omvänt, anta att det finns en lösning S " till partitionsinstansen. Då S " innehålla antingen z ₁ eller z ₂ , men inte båda, eftersom deras summa är mer än summa( S ) + T . Om S'' innehåller z ₁ måste den innehålla element från S med summan av exakt T , så S'' minus z ₁ är en lösning på SubsetSum-instansen. Om S'' innehåller z ₂ måste det innehålla element från S med summan av exakt summa( S ) − T , så de andra objekten i S är en lösning på SubsetSum-instansen.

Approximationsalgoritmer

Som nämnts ovan är partitionsproblemet ett specialfall av flervägspartitionering och delmängdsumma. Därför kan det lösas med algoritmer utvecklade för vart och ett av dessa problem. Algoritmer utvecklade för flervägsnummerpartitionering inkluderar:

Girig nummeruppdelning – går över siffrorna och sätter varje nummer i den uppsättning vars nuvarande summa är minst. Om siffrorna inte är sorterade är körtiden O( n ) och approximationsförhållandet är som mest 3/2 ("approximationsförhållande" betyder den större summan i algoritmens utdata, dividerat med den större summan i en optimal partition). Sortering av siffrorna ökar körtiden till O( n log n ) och förbättrar approximationsförhållandet till 7/6. Om talen är jämnt fördelade i [0,1], är approximationsförhållandet högst $1+O\left({\frac {\log {\log { n}}}{n}}\right)$ nästan säkert , och $1+O\left({\frac {1}{n}}\right)$ i förväntan.
Största skillnadsmetoden (även kallad Karmarkar–Karp-algoritmen ) sorterar siffrorna i fallande ordning och ersätter siffror upprepade gånger med deras skillnader. Körtidskomplexiteten är O( n log n ). I värsta fall är dess approximationsförhållande liknande – högst 7/6 . Men i det genomsnittliga fallet presterar den mycket bättre än den giriga algoritmen: när siffror är jämnt fördelade i [0,1], är dess approximationsförhållande som mest $1+1 /n^{\Theta (\log {n})}$ i väntan. Den presterar också bättre i simuleringsexperiment.
Multifit -algoritmen använder binär sökning i kombination med en algoritm för bin-packning . I värsta fall är dess approximationsförhållande 8/7 .
Delmängdens summaproblem har en FPTAS som kan användas för partitionsproblemet också, genom att sätta målsumman till summa( S )/2.

Exakta algoritmer

Det finns exakta algoritmer som alltid hittar den optimala partitionen. Eftersom problemet är NP-hårt kan sådana algoritmer ta exponentiell tid i allmänhet, men kan vara praktiskt användbara i vissa fall. Algoritmer utvecklade för flervägsnummerpartitionering inkluderar:

Den pseudopolynomiska tidsnummerpartitioneringen tar $O(nm)$ minne, där $m$ är det största talet i inmatningen.
The Complete Greedy Algorithm (CGA) tar hänsyn till alla partitioner genom att konstruera ett binärt träd . Varje nivå i trädet motsvarar ett inmatat nummer, där roten motsvarar det största numret, nivån under det näst största numret, etc. Varje gren motsvarar en annan uppsättning där det aktuella numret kan läggas. Att korsa trädet i djup-första ordning kräver bara $O(n)$ mellanslag, men det kan ta $O(2^{n})$ tid. Körtiden kan förbättras genom att använda en girig heuristik: i varje nivå utvecklar du först den gren där det aktuella numret sätts i setet med den minsta summan. Denna algoritm hittar först lösningen som hittas av girig nummerpartitionering , men fortsätter sedan med att leta efter bättre lösningar. Vissa varianter av denna idé är fullständigt polynom-tidsapproximationsscheman för delmängdssummaproblemet, och därmed även för partitionsproblemet.
Den kompletta Karmarkar-Karp-algoritmen (CKK) tar hänsyn till alla partitioner genom att konstruera ett binärt träd. Varje nivå motsvarar ett par siffror. Den vänstra grenen motsvarar att placera dem i olika delmängder (dvs. att ersätta dem med deras skillnad), och den högra grenen motsvarar att sätta dem i samma delmängd (dvs. att ersätta dem med deras summa). Denna algoritm hittar först lösningen som hittas av den största differensmetoden , men fortsätter sedan med att hitta bättre lösningar. Det går betydligt snabbare än CGA på slumpmässiga instanser. Dess fördel är mycket större när en lika partition finns, och kan vara av flera storleksordningar. I praktiken kan problem av godtycklig storlek lösas av CKK om talen har högst 12 signifikanta siffror . CKK kan också köras som en när som helst algoritm : den hittar KK-lösningen först och hittar sedan successivt bättre lösningar när tiden tillåter (kräver eventuellt exponentiell tid för att nå optimalitet, i de värsta fallen). Det kräver $O(n)$ utrymme, men i värsta fall kan det ta $O(2^{n})$ tid.

Algoritmer utvecklade för delmängdssumma inkluderar:

Horowitz och Sanhi – går i tid $O(2^{n/2}\cdot (n/2))$ , men kräver $O(2^{n/2})$ mellanslag.
Schroeppel och Shamir – går i tiden ${\displaystyle O(2^{n/2}\cdot (n/4))} ,$ och kräver mycket mindre utrymme – $O(2^{n/4})$ .
Howgrave-Graham och Joux – körs i tid $O(2^{n/3})$ , men det är en randomiserad algoritm som bara löser beslutsproblemet (inte optimeringsproblemet).

Hårda instanser och fasövergång

Uppsättningar med endast en eller inga partitioner tenderar att vara svårast (eller dyrast) att lösa jämfört med deras inmatningsstorlekar. När värdena är små jämfört med storleken på uppsättningen är perfekta partitioner mer sannolika. Problemet är känt för att genomgå en " fasövergång "; är troligt för vissa uppsättningar och osannolikt för andra. Om m är antalet bitar som behövs för att uttrycka ett tal i mängden och n är storleken på mängden så $m/n<1$ att ha många lösningar och $m/n>1$ tenderar att ha få eller inga lösningar. När n och m blir större går sannolikheten för en perfekt partition till 1 respektive 0. Detta argumenterades ursprungligen baserat på empiriska bevis av Gent och Walsh, sedan genom att använda metoder från statistisk fysik av Mertens, och senare bevisade av Borgs , Chayes och Pittel.

Probabilistisk version

Ett relaterat problem, något liknande födelsedagsparadoxen , är att bestämma storleken på ingångsmängden så att vi har en sannolikhet på hälften att det finns en lösning, under antagandet att varje element i mängden är slumpmässigt utvalda med enhetlig fördelning mellan 1 och något givet värde. Lösningen på detta problem kan vara kontraintuitiv, som födelsedagsparadoxen.

Varianter och generaliseringar

Lika kardinalitetspartition är en variant där båda delarna ska ha lika många poster, förutom att ha lika summa. Denna variant är också NP-hård. Bevis . Givet en standardpartitionsinstans med några n nummer, konstruera en Equal-Cardinality-Partition-instans genom att lägga till n nollor. Det är uppenbart att den nya instansen har en lika-kardinalitet lika summa-partition om den ursprungliga instansen har en lika-summa-partition. Se även Balanserad nummeruppdelning .

Distinkt partition är en variant där alla ingående heltal är distinkta. Denna variant är också NP-hård. ^{[ citat behövs ]}

Produktpartition är problemet med att partitionera en uppsättning heltal i två uppsättningar med samma produkt (snarare än samma summa). Detta problem är starkt NP-hårt .

Kovalyov och Pesch diskuterar ett generiskt tillvägagångssätt för att bevisa NP-hårdhet hos problem av partitionstyp.

Ansökningar

En tillämpning av uppdelningsproblemet är för manipulation av val . Anta att det finns tre kandidater (A, B och C). En enskild kandidat bör väljas med hjälp av en röstningsregel baserad på poängsättning, t.ex. vetoregeln (varje väljare lägger sitt veto mot en enskild kandidat och den kandidat som har minst veton vinner). Om en koalition vill säkerställa att C väljs, bör de dela upp sina röster mellan A och B för att maximera det minsta antalet veton var och en av dem får. Om rösterna viktas, kan problemet reduceras till partitionsproblemet, och därmed kan det lösas effektivt med CKK. Detsamma gäller för alla andra röstningsregel som är baserade på poängsättning.

Anteckningar

Borgs, Christian; Chayes, Jennifer; Pittel, Boris (2001), "Phase transition and finite-size scaling for the integer partitioning problem", Random Structures and Algorithms , 19 (3–4): 247–288, CiteSeerX 10.1.1.89.9577 , doi : 2/r. .10004 , S2CID 6819493
Gent, Ian; Walsh, Toby (augusti 1996). "Fasövergångar och glödgade teorier: Nummeruppdelning som en fallstudie". I Wolfgang Wahlster (red.). Handlingar från den 12:e europeiska konferensen om artificiell intelligens . ECAI-96. John Wiley och söner. s. 170–174. CiteSeerX 10.1.1.2.4475 .
Gent, Ian; Walsh, Toby (1998), "Analysis of Heuristics for Number Partitioning", Computational Intelligence , 14 (3): 430–451, CiteSeerX 10.1.1.149.4980 , doi : 10.1111/0824-709310 430-709391 30 , S20691 30.1.1.149.4980 .
Korf, Richard E. (1998), "A complete anytime algorithm for number partitioning", Artificial Intelligence , 106 (2): 181–203, CiteSeerX 10.1.1.90.993 , doi : 10.1016/S0004-300068) 1 , ISSN 0004-3702
) , "Phase Transition in the Number Partitioning Problem", Physical Review Letters , 81 (20): 4281–4284, arXiv : cond-mat/9807077 , Bibcode : 1998PhRvL..81.42i : 01.42i . /PhysRevLett.81.4281 , S2CID 119541289
Mertens, Stephan (2001), "A physicist's approach to number partitioning", Theoretical Computer Science , 265 (1–2): 79–108, arXiv : cond-mat/0009230 , doi : 10.1016/S0304-30015(501) -0 , S2CID 16534837
Mertens, Stephan (2006). "Det enklaste svåra problemet: nummerpartitionering" . I Allon Percus; Gabriel Istrate; Cristopher Moore (red.). Beräkningskomplexitet och statistisk fysik . USA: Oxford University Press. s. 125–140. arXiv : cond-mat/0310317 . Bibcode : 2003cond.mat.10317M . ISBN 9780195177374 .
Mertens, Stephan (1999), "En komplett när som helst algoritm för balanserad nummerpartitionering", arXiv : cs/9903011