Problemet med at opdele et sæt tal er problemet med at bestemme, om et givet multisæt S af positive heltal kan opdeles i to delmængder S 1 og S 2 , således at summen af tal fra S 1 er lig med summen af tal fra S 2 . Selvom nummeropdelingsproblemet er NP-komplet , er der en pseudopolynomisk tidsløsning ved dynamisk programmering, og der er heuristiske algoritmer til at løse mange konkrete problemer enten optimalt eller tilnærmelsesvis. Af denne grund kaldes problemet "det simpleste NP-hårde problem" [1] .
Der er en optimeringsversion af partitionsproblemet, hvor det er nødvendigt at opdele multisættet S i to delmængder S 1 og S 2 , således at forskellen mellem summen af elementerne af S 1 og summen af elementerne i S 2 er minimal. Optimeringsversionen er NP-hård , men kan i praksis løses effektivt [2] .
Givet et sæt S ={3,1,1,2,2,1}, er to sæt S 1 ={1,1,1,2} og S 2 ={2,3} en mulig løsning på partitioneringsproblemet . Begge sæt har sum 5, og de er en partition af S . Bemærk, at denne løsning ikke er unik. S1 = {3,1,1} og S2 = {2,2,1} er en anden løsning.
Ikke hvert multisæt af positive heltal har en opdeling i to dele med lige store summer. Et eksempel på et sådant sæt er S = {2,5}.
Problemet kan løses ved hjælp af dynamisk programmering , så længe størrelsen af sættet og størrelsen af summen af heltal i sættet ikke er for store til at gøre hukommelseskravene umulige.
Lad os repræsentere input af algoritmen som en liste over formen:
S=x1 , ..., x nLad N være antallet af elementer i mængden S . Lad K være summen af alle elementer fra mængden S . Det vil sige, K = x 1 + ... + x n . Vi vil konstruere en algoritme, der bestemmer, om der er en delmængde S , hvis sum af elementer er lig med . Hvis undersættet eksisterer, så:
hvis K er lige, så giver resten af mængden S også hvis K er ulige, vil resten af mængden S give summen . Dette er den bedst mulige løsning.Vi ønsker at bestemme, om der er en delmængde S , hvis sum af elementer er . Lade:
p ( i , j ) er Sand , hvis der er en delmængde blandt { x 1 , ..., x j }, hvis elementer summeres til i og Falsk ellers.Så er p ( , n ) Sand hvis og kun hvis der findes en delmængde af S hvis sum er . Målet med vores algoritme er at beregne p ( , n ). For at opnå dette har vi følgende tilbagevendende formler :
p ( i , j ) er Sand, hvis enten p ( i , j − 1) er Sand eller p ( i − x j , j − 1) er Sand p ( i , j ) vurderes til Falsk ellersÅrsagen til dette er som følger: der er en delmængde S , hvis sum er lig med i for tallene
x 1 , ..., x jhvis og kun hvis en af de to er sand:
der er en delmængde { x 1 , ..., x j-1 } der giver summen i ; der er en delmængde { x 1 , ..., x j-1 } der giver summen i − x j , da x j + summen af denne delmængde = i .Algoritmen bygger en tabel af størrelse n indeholdende rekursionsværdierne, hvor er summen af værdierne og er antallet af elementer. Når hele bordet er fyldt, vender du tilbage . Nedenfor ses P- tabellen . På figuren en blå pil fra en blok til en anden, hvis værdien af den sidste blok kan afhænge af værdien af kildeblokken. Denne afhængighed er en egenskab ved en rekursiv relation.
INPUT: Liste over heltal S OUTPUT: Sandt, hvis S kan opdeles i to delmængder, der har samme summer 1 funktion find_partition ( S ): 2n ← |S| 3 K ← sum(S) 4 P ← tom boolsk tabel med størrelse ( + 1) gange (n + 1) 5 initialiser den øverste række ( P(0,x) ) i tabel P til Sand 6 initialisere kolonnen længst til venstre ( P(x, 0) ) i tabel P , undtagen celle P(0, 0) til Falsk 7 for i fra 1 til 8 for j fra 1 til n 9 hvis (iS[j-1]) >= 0 10 P(i, j) ← P(i, j-1) eller P(iS[j-1], j-1) 11 ellers 12 P(i, j) ← P(i, j-1) 13 retur værdi P( , n)Nedenfor er tabellen P for mængden S ={3, 1, 1, 2, 2, 1} brugt ovenfor:
Denne algoritme kører i O ( KN ) tid , hvor N er antallet af elementer i inputsættet og K er summen af elementerne i inputsættet.
Algoritmen kan udvides til k - part multipartitionsproblemet, men kræver O ( n ( k − 1) m k − 1 ) hukommelse , hvor m er det største tal i inputmængden, hvilket gør algoritmen praktisk talt meningsløs selv for k = 3 , medmindre meget små tal ikke er angivet som input [2] .
Partitionsproblemet kan opfattes som et særligt tilfælde af delmængdesumproblemet, og den pseudopolynomiske tidsdynamiske programmeringsløsning , der er givet ovenfor, er generaliseret til delmængdesumproblemet .
Der er nogle heuristiske algoritmer til at tilnærme partitionsoptimeringsproblemet. De kan udvides til eksakte lineære tidsalgoritmer [2] .
En tilgang til problemet, som efterligner den måde, en partners barn leger på, er en grådig algoritme , der itererer over tallene i faldende rækkefølge og lægger hvert tal til en mindre sum. Denne tilgang har O ( n log n ) køretid . Denne heuristiske algoritme fungerer godt i praksis, hvis tallene i sættet er af omtrent samme rækkefølge, men algoritmen er ikke garanteret at producere den bedst mulige partition. For eksempel, givet sættet S ={4, 5, 6, 7, 8} som input, ville denne grådige algoritme resultere i en opdeling af S i delmængder {4, 5, 8} og {6, 7}. S har dog en nøjagtig afbalanceret partition i undersæt {7, 8} og {4, 5, 6}.
Denne grådige tilgang er kendt for at give en 7 ⁄ 6 tilnærmelse til den optimale løsning af optimeringsversionen. Det vil sige, hvis outputtet af den grådige algoritme giver to sæt A og B , så , hvor OPT er størrelsen af det største sæt i den bedste partition [3] . Nedenfor er et eksempel (i Python ) på en grådig algoritme.
def find_partition ( int_list ): "Partitioner `int_list` i to sæt med lige store summer " A = sæt () B = sæt () for n i sorteret ( int_list , omvendt = Sand ): hvis sum ( A ) < sum ( B ) : A . tilføje ( n ) andet : B. _ tilføje ( n ) returnere ( A , B )Algoritmen kan udvides til tilfælde af k > 2 sæt - vælg de k største elementer, fordel dem over k sæt, iterér derefter over de resterende tal i faldende rækkefølge og tilføj dem til mængden med en mindre sum (den simple version ovenfor svarer til til k = 2 ). Denne version kører i O (2 k n 2 ) tid og er kendt for at give en tilnærmelse [3] . Vi har således et tilnærmet polynomisk tidsskema (PTAS) for partitioneringsproblemet, selvom det ikke er et fuldt tilnærmet polynomisk tidsskema (løbetiden er eksponentiel for det ønskede niveau af garanteret tilnærmelse). Der er dog varianter af denne idé, der er fuldstændigt tilnærmede polynomiske tidsskemaer for delmængdesumproblemet og dermed også for partitionsproblemet [4] [5] .
En anden heuristik er Largest Difference Method (LDM) [6] , som kaldes Karmarkar - Karp - heuristikken [2] efter de videnskabsmænd, der offentliggjorde metoden i 1982 [7] . MNR har to faser. Den første fase af algoritmen tager de to største tal fra inputtet og erstatter dem med forskellen. Gentag handlingen, indtil der er et nummer tilbage. Substitutionen repræsenterer en beslutning om at placere to numre i forskellige undersæt, men i hvilke sæt disse numre er placeret, træffes beslutningen ikke. Ved slutningen af den første fase er det resterende enkelte tal forskellen mellem de to delmængdesummer. På anden fase bygges selve løsningen [1] .
Forskellens heuristiske algoritme klarer sig bedre end den grådige algoritme, men forbliver dårlig til problemer, hvor tallene afhænger eksponentielt af størrelsen af mængden [1] .
Den følgende Java -kode repræsenterer den første fase af Karmarkar-Karp-algoritmen. Algoritmen bruger heapen til effektivt at finde det par af de største tal blandt de resterende.
int karmarkarKarpPartition ( int [] baseArr ) { // create max heap PriorityQueue < Integer > heap = new PriorityQueue < Integer > ( baseArr . length , REVERSE_INT_CMP ); for ( int værdi : baseArr ) { heap . tilføje ( værdi ); } while ( heap . size ( ) > 1 ) { int val1 = heap . meningsmåling (); int val2 = heap . meningsmåling (); dynge . add ( val1 - val2 ); } retur bunke . meningsmåling (); }Der er også tidsskæringsalgoritmer baseret på differensheuristikken, der først finder løsningen opnået ved differensheuristikken, derefter finder man gradvist bedre løsninger, hvis tiden tillader det ( eksponentiel vækst af køretid er mulig for at opnå den optimale løsning i det værste tilfælde) [8] [9] .
Sæt med kun én eller ingen partitioner er ofte de sværeste (eller mest spildfulde) at få en beslutning om størrelsen af input. Hvis værdierne er små sammenlignet med størrelsen af sættet, er gode partitioner mere sandsynlige. Problemet er kendt for at gennemgå en " faseovergang ", når gode partitioner er mest sandsynlige for nogle sæt og usandsynlige for andre. Hvis m er antallet af bits, der kræves for at udtrykke ethvert tal fra mængden, og n er størrelsen af mængden, så har problemet oftere mange løsninger, og problemet har oftere én løsning eller slet ingen løsning. Når n og m bliver større, tenderer sandsynligheden for en god partition til henholdsvis 1 og en dårlig partition til 0. Denne kendsgerning var oprindeligt baseret på de empiriske resultater fra Gent og Walsh [10] , derefter på metoderne inden for statistisk fysik (Mertens [11] [12] ), og endelig blev faktum bevist af Borgs, Chayes og Pittel [13] .
Der er et problem omkring 3-partition af et sæt tal , som leder efter en partition af sættet S i | S |/3 tredobler, hver tredobbelt med samme mængde. Dette problem er fuldstændig forskelligt fra partitionsproblemet og har ikke en pseudopolynomial køretidsalgoritme, medmindre P=NP [14] .
Problemet med at opdele i flere sæt generaliserer optimeringsversionen af opdelingsproblemet. Her er målet at opdele et sæt eller multisæt af n heltal i et givet antal k delmængder, hvilket minimerer forskellen mellem den mindste og største sum af tal i delmængderne [2] .
Yderligere generaliseringer af partitioneringsproblemet kan findes i papiret " The Containerizing Problem ".
Et relateret problem, der lidt ligner fødselsdagsparadokset , er at finde en inputmængdestørrelse, hvor sandsynligheden for eksistensen af en løsning er 0,5, givet at hvert element i sættet er tilfældigt valgt mellem 1 og en given værdi.
Løsningen på dette problem kan være paradoksal. For eksempel, når man tilfældigt vælger heltal mellem 1 og én million, tror mange mennesker, at svaret vil være tusinder, titusinder eller endda hundredtusinder, mens det korrekte svar faktisk vil være omkring 23 (for detaljer, se artiklen Partitioneringsproblem ).