Problemet med at opdele et sæt tal

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. oktober 2021; verifikation kræver 1 redigering .

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] .

Eksempler

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}.

Pseudopolynomisk tidsalgoritme

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 n

Lad 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.

Tilbagevendende relationer

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 j

hvis 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 .

Pseudopolynomial algoritme

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)

Eksempel

Nedenfor er tabellen P for mængden S ={3, 1, 1, 2, 2, 1} brugt ovenfor:

Analyse

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] .

Et særligt tilfælde af delmængdesumproblemet

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 .

Approksimationsalgoritmer

Der er nogle heuristiske algoritmer til at tilnærme partitionsoptimeringsproblemet. De kan udvides til eksakte lineære tidsalgoritmer [2] .

Grådig algoritme

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] .

Forskelsalgoritme

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 (); }

Andre tilgange

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] .

Vanskelige sager

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] .

Varianter og generaliseringer

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 ".

Probabilistisk version

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 ).

Noter

  1. ↑ 123 Hayes , 2002 .
  2. ↑ 1 2 3 4 5 Korf, 2009 .
  3. ↑ 1 2 Graham, 1969 , s. 416-429.
  4. ↑ Kellerer, Pferschy, Pisinger, 2004 , s. 94.
  5. ↑ Martello, Toth, 1990 , s. 105-136.
  6. ↑ Michiels, Korst, Aarts, 2003 , s. 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 og Johnson 1979 , s. 96-105.

Litteratur