Problemet med att partitionera en uppsättning nummer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 oktober 2021; verifiering kräver 1 redigering .

Problemet med att dela upp en uppsättning tal är problemet med att avgöra om en given multimängd S av positiva heltal kan delas upp i två delmängder S 1 och S 2 så att summan av siffror från S 1 är lika med summan av siffror från S 2 . Även om nummerpartitioneringsproblemet är NP-komplett , finns det en pseudopolynomisk tidslösning genom dynamisk programmering och det finns heuristiska algoritmer för att lösa många konkreta problem, antingen optimalt eller ungefärligt. Av denna anledning kallas problemet "det enklaste NP-hårda problemet" [1] .

Det finns en optimeringsversion av partitionsproblemet, där det krävs att dela upp multiuppsättningen S i två delmängder S 1 och S 2 , så att skillnaden mellan summan av elementen i S 1 och summan av elementen i S 2 är minimal. Optimeringsversionen är NP-hård , men kan i praktiken lösas effektivt [2] .

Exempel

Med en uppsättning S ={3,1,1,2,2,1} är två uppsättningar S 1 ={1,1,1,2} och S 2 ={2,3} en möjlig lösning på partitionsproblemet . Båda uppsättningarna har summa 5 och de är en partition av S . Observera att denna lösning inte är unik. S1 = {3,1,1} och S2 = { 2,2,1} är en annan lösning.

Inte varje multimängd positiva heltal har en uppdelning i två delar med lika summor. Ett exempel på en sådan mängd är S = {2,5}.

Pseudopolynomisk tidsalgoritm

Problemet kan lösas med hjälp av dynamisk programmering , så länge som storleken på mängden och storleken på summan av heltal i mängden inte är för stora för att göra minneskraven omöjliga.

Låt oss representera inmatningen av algoritmen som en lista över formen:

S=x1 , ..., x n

Låt N vara antalet element i mängden S . Låt K vara summan av alla element från mängden S . Det vill säga K = x 1 + ... + x n . Vi kommer att konstruera en algoritm som avgör om det finns en delmängd S vars summa av element är lika med . Om delmängden finns, då:

om K är jämnt ger också resten av mängden S om K är udda, kommer resten av mängden S att ge summan . Detta är den bästa möjliga lösningen.

Återkommande relationer

Vi vill avgöra om det finns en delmängd S vars summa av element är . Låta:

p ( i , j ) är Sant om det finns en delmängd bland { x 1 , ..., x j } vars element summerar till i och False annars.

Då är p ( , n ) Sant om och endast om det finns en delmängd av S vars summa är . Målet med vår algoritm är att beräkna p ( , n ). För att uppnå detta har vi följande återkommande formler :

p ( i , j ) är sant om antingen p ( i , j − 1) är sant eller p ( i − x j , j − 1) är sant p ( i , j ) evaluerar till Falskt annars

Anledningen till detta är följande: det finns någon delmängd S vars summa är lika med i för talen

x 1 , ..., x j

om och bara om en av de två är sann:

det finns en delmängd { x 1 , ..., x j-1 } som ger summan i ; det finns en delmängd { x 1 , ..., x j-1 } som ger summan i − x j , eftersom x j + summan av denna delmängd = i .

Pseudopolynomalgorithm

Algoritmen bygger en tabell med storlek n som innehåller rekursionsvärdena, där är summan av värdena och är antalet element. När hela bordet är fullt, återvänd . Nedan är P -tabellen . I figuren, en blå pil från ett block till ett annat, om värdet på det sista blocket kan bero på värdet på källblocket. Detta beroende är en egenskap hos en rekursiv relation.

INPUT: Lista över heltal S OUTPUT: Sant om S kan delas upp i två delmängder som har samma summor 1 funktion find_partition ( S ): 2n ← |S| 3 K ← summa(S) 4 P ← tom boolesk tabell med storlek ( + 1) med (n + 1) 5 initiera den översta raden ( P(0,x) ) i tabell P till True 6 initiera kolumnen längst till vänster ( P(x, 0) ) i tabell P , förutom cell P(0, 0) till False 7 för i från 1 till 8 för j från 1 till n 9 om (iS[j-1]) >= 0 10 P(i, j) ← P(i, j-1) eller P(iS[j-1], j-1) 11 annars 12 P(i, j) ← P(i, j-1) 13 retur värde P( , n)

Exempel

Nedan är tabellen P för mängden S ={3, 1, 1, 2, 2, 1} som används ovan:

Analys

Denna algoritm körs i O ( KN ) tid , där N är antalet element i ingångsmängden och K är summan av elementen i ingångsmängden.

Algoritmen kan utökas till k -parts multipartitionsproblem, men kräver O ( n ( k − 1) m k − 1 ) minne , där m är det största talet i ingångsmängden, vilket gör algoritmen praktiskt taget meningslös även för k = 3 , såvida inte mycket små tal inte anges som indata [2] .

Ett specialfall av delmängdssummaproblemet

Partitionsproblemet kan ses som ett specialfall av delmängdssummaproblemet, och den pseudopolynomiska tidsdynamiska programmeringslösningen som ges ovan är generaliserad till delmängdssummaproblemet .

Approximationsalgoritmer

Det finns några heuristiska algoritmer för att approximera partitionsoptimeringsproblemet. De kan utökas till exakta linjära tidsalgoritmer [2] .

Girig algoritm

En metod för problemet, som efterliknar hur en partners barn spelar, är en girig algoritm som itererar över siffrorna i fallande ordning och lägger till varje nummer till en mindre summa. Detta tillvägagångssätt har O ( n log n ) körtid . Denna heuristiska algoritm fungerar bra i praktiken om siffrorna i uppsättningen är av ungefär samma ordning, men det är inte garanterat att algoritmen producerar bästa möjliga partition. Till exempel, givet uppsättningen S ={4, 5, 6, 7, 8} som indata, skulle denna giriga algoritm resultera i en uppdelning av S i delmängder {4, 5, 8} och {6, 7}. S har dock en exakt balanserad partition i delmängder {7, 8} och {4, 5, 6}.

Detta giriga tillvägagångssätt är känt för att ge en approximation på 7 ⁄ 6 till den optimala lösningen för optimeringsversionen. Det vill säga, om utdata från den giriga algoritmen ger två uppsättningar A och B , då , där OPT är storleken på den största uppsättningen i den bästa partitionen [3] . Nedan är ett exempel (i Python ) på en girig algoritm.

def find_partition ( int_list ): "Partitionera `int_list` i två uppsättningar med lika summor " A = set () B = set () för n i sorterad ( int_list , omvänd = True ): om summa ( A ) < summa ( B ) : A . lägg till ( n ) annat : B. lägg till ( n ) returnera ( A , B )

Algoritmen kan utökas till fall av k > 2 set - välj de k största elementen, fördela dem över k set, iterera sedan över de återstående talen i fallande ordning och lägg till dem till mängden med en mindre summa (den enkla versionen ovan motsvarar till k = 2 ). Denna version körs i O (2 k n 2 ) tid och är känd för att ge en approximation [3] . Således har vi ett ungefärligt polynomtidsschema (PTAS) för partitioneringsproblemet, även om det inte är ett helt ungefärligt polynomtidsschema (körtiden är exponentiell för den önskade nivån av garanterad approximation). Det finns dock varianter av denna idé som är helt approximativa polynomtidsscheman för delmängdssummaproblemet, och därmed även för partitionsproblemet [4] [5] .

Skillnadsalgoritm

En annan heuristik är Largest Difference Method (LDM) [6] , som kallas Karmarkar- Karp - heuristiken [2] efter de vetenskapsmän som publicerade metoden 1982 [7] . MNR har två faser. Den första fasen av algoritmen tar de två största talen från ingången och ersätter dem med skillnaden. Upprepa operationen tills ett nummer återstår. Substitutionen representerar ett beslut att placera två nummer i olika delmängder, men i vilka uppsättningar dessa nummer placeras fattas inte beslutet. I slutet av den första fasen är det återstående enskilda talet skillnaden mellan de två delmängdssummorna. I det andra steget byggs själva lösningen [1] .

Den heuristiska skillnadsalgoritmen presterar bättre än den giriga algoritmen, men förblir dålig för problem där siffrorna beror exponentiellt på mängden storlek [1] .

Följande Java -kod representerar den första fasen av Karmarkar-Karp-algoritmen. Algoritmen använder högen för att effektivt hitta paret med största siffror bland de återstående.

int karmarkarKarpPartition ( int [] baseArr ) { // create max heap PriorityQueue < Integer > heap = new PriorityQueue < Integer > ( baseArr . length , REVERSE_INT_CMP ); for ( int värde : baseArr ) { heap . addera ( värde ); } while ( hög . storlek () > 1 ) { int val1 = hög . omröstning (); int val2 = hög . omröstning (); hög . add ( val1 - val2 ); } återvända högen . omröstning (); }

Andra tillvägagångssätt

Det finns också tidsavskärningsalgoritmer baserade på skillnadsheuristiken som först hittar lösningen som erhålls av skillnadsheuristiken, sedan hittas progressivt bättre lösningar om tiden tillåter ( exponentiell tillväxt av körtid är möjlig för att få den optimala lösningen i det värsta fall) [8] [9] .

Svåra fall

Uppsättningar med endast en eller inga partitioner är ofta de svåraste (eller mest slösaktiga) för att få ett beslut om storleken på inmatningen. Om värdena är små jämfört med storleken på uppsättningen, är bra partitioner mer sannolikt. Problemet är känt för att genomgå en " fasövergång " när bra partitioner är mest sannolika för vissa uppsättningar och osannolikt för andra. Om m är antalet bitar som krävs för att uttrycka ett tal från mängden, och n är storleken på mängden, så har problemet oftare många lösningar, och för problemet har oftare en lösning eller ingen lösning alls. När n och m blir större tenderar sannolikheten för en bra partition till 1 respektive en dålig partition till 0. Detta faktum baserades till en början på de empiriska resultaten av Gent och Walsh [10] , sedan på metoderna för statistisk fysik (Mertens [11] [12] ) och slutligen bevisades faktum av Borgs, Chayes och Pittel [13] .

Varianter och generaliseringar

Det finns ett problem med 3-partition av en uppsättning nummer , som letar efter en partition av uppsättningen S i | S |/3 trippel, varje trippel med samma mängd. Detta problem skiljer sig helt från partitionsproblemet och har ingen pseudopolynomisk körtidsalgoritm, såvida inte P=NP [14] .

Problemet med att dela upp i flera uppsättningar generaliserar optimeringsversionen av uppdelningsproblemet. Här är målet att dela upp en uppsättning eller multimängd av n heltal i ett givet antal k delmängder, vilket minimerar skillnaden mellan den minsta och största summan av tal i delmängderna [2] .

Ytterligare generaliseringar av partitioneringsproblemet kan hittas i artikeln " The Containerizing Problem ".

Probabilistisk version

Ett relaterat problem, något som liknar födelsedagsparadoxen , är att hitta en indatamängdsstorlek för vilken sannolikheten för att det finns en lösning är 0,5, givet att varje element i mängden väljs slumpmässigt mellan 1 och något givet värde.

Lösningen på detta problem kan vara paradoxal. Till exempel, när man slumpmässigt väljer heltal mellan 1 och en miljon tror många att svaret kommer att vara tusentals, tiotusentals eller till och med hundratusentals, medan det korrekta svaret i själva verket kommer att vara ungefär 23 (för detaljer, se artikel Partitioneringsproblem ).

Anteckningar

  1. ↑ 123 Hayes , 2002 .
  2. ↑ 1 2 3 4 5 Korf, 2009 .
  3. ↑ 1 2 Graham, 1969 , sid. 416–429.
  4. ↑ Kellerer, Pferschy, Pisinger, 2004 , sid. 94.
  5. ↑ Martello, Toth, 1990 , sid. 105–136.
  6. ↑ Michiels, Korst, Aarts, 2003 , sid. 71–75.
  7. ↑ Karmarkar, Karp, 1982 .
  8. ↑ Korff, 1998 .
  9. ↑ Mertens, 1999 .
  10. ↑ Gent, Walsh, 1996 .
  11. ↑ Mertens, 1998 .
  12. ↑ Mertens, 2001 .
  13. ↑ Borgs, Chayes, Pittel, 2001 .
  14. ↑ Garey och Johnson 1979 , sid. 96–105.

Litteratur