Problema partiționării unui set de numere

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 27 octombrie 2021; verificarea necesită 1 editare .

Problema partiționării unei mulțimi de numere este problema de a determina dacă un multimul dat S de numere întregi pozitive poate fi împărțit în două submulțimi S 1 și S 2 astfel încât suma numerelor din S 1 să fie egală cu suma numerelor din S 2 . Deși problema partiționării numerelor este NP-completă , există o soluție de timp pseudopolinomială prin programare dinamică și există algoritmi euristici pentru rezolvarea multor probleme concrete fie optim, fie aproximativ. Din acest motiv, problema se numește „cea mai simplă problemă NP-hard” [1] .

Există o versiune de optimizare a problemei partiției, în care este necesară împărțirea multisetului S în două subseturi S 1 și S 2 , astfel încât diferența dintre suma elementelor lui S 1 și suma elementelor lui S 2 este minim. Versiunea de optimizare este NP-hard , dar în practică poate fi rezolvată eficient [2] .

Exemple

Având în vedere o mulțime S ={3,1,1,2,2,1}, două mulțimi S 1 ={1,1,1,2} și S 2 ={2,3} sunt o soluție fezabilă pentru problema de partiționare . Ambele mulțimi au suma 5 și sunt o partiție a lui S . Rețineți că această soluție nu este unică. S 1 ={3,1,1} și S 2 ={2,2,1} este o altă soluție.

Nu fiecare multiset de numere întregi pozitive are o împărțire în două părți cu sume egale. Un exemplu de astfel de mulțime este S = {2,5}.

Algoritm de timp pseudopolinomial

Problema poate fi rezolvată folosind programarea dinamică , atâta timp cât dimensiunea mulțimii și dimensiunea sumei întregilor din mulțime nu sunt prea mari pentru a face ca cerințele de memorie să nu fie fezabile.

Să reprezentăm intrarea algoritmului ca o listă de forma:

S=x1 , ..., x n

Fie N numărul de elemente din mulțimea S . Fie K suma tuturor elementelor din mulțimea S . Adică K = x 1 + ... + x n . Vom construi un algoritm care determină dacă există o submulțime S a cărei sumă de elemente este egală cu . Dacă subsetul există, atunci:

dacă K este par, atunci și restul mulțimii S dă și dacă K este impar, restul mulțimii S va da suma . Aceasta este cea mai bună soluție posibilă.

Relații recurente

Vrem să determinăm dacă există o submulțime S a cărei sumă de elemente este . Lăsa:

p ( i , j ) este adevărat dacă există o submulțime între { x 1 , ..., x j } ale cărei elemente se adună la i și Fals în caz contrar.

Atunci p ( , n ) este adevărat dacă și numai dacă există o submulțime a lui S a cărei sumă este . Scopul algoritmului nostru este de a calcula p ( , n ). Pentru a realiza acest lucru, avem următoarele formule recurente :

p ( i , j ) este adevărat dacă fie p ( i , j - 1) este adevărat sau p ( i - x j , j - 1) este adevărat p ( i , j ) se evaluează la Fals în caz contrar

Motivul pentru aceasta este următorul: există o submulțime S a cărei sumă este egală cu i pentru numere

x 1 , ..., x j

dacă și numai dacă unul dintre cele două este adevărat:

există o submulțime { x 1 , ..., x j-1 } care dă suma i ; există o submulțime { x 1 , ..., x j-1 } care dă suma i − x j , deoarece x j + suma acestei submulțimi = i .

Algoritm pseudopolinom

Algoritmul construiește un tabel de dimensiunea n care conține valorile recursiunii, unde este suma valorilor și este numărul de elemente. Când întreaga masă este plină, întoarceți . Mai jos este tabelul P. În figură, o săgeată albastră de la un bloc la altul, dacă valoarea blocului final poate depinde de valoarea blocului sursă. Această dependență este o proprietate a unei relații recursive.

INTRARE: Lista de numere întregi S IEȘIRE: Adevărat dacă S poate fi împărțit în două submulțimi care au aceleași sume 1 funcție find_partition ( S ): 2n ← |S| 3 K ← sumă(S) 4 P ← tabel boolean gol de dimensiune ( + 1) prin (n + 1) 5 inițializați rândul de sus ( P(0,x) ) al tabelului P la Adevărat 6 inițializați coloana din stânga ( P(x, 0) ) a tabelului P , cu excepția celulei P(0, 0) la Fals 7 pentru i de la 1 la 8 pentru j de la 1 la n 9 dacă (iS[j-1]) >= 0 10 P(i, j) ← P(i, j-1) sau P(iS[j-1], j-1) 11 altfel 12 P(i, j) ← P(i, j-1) 13 return valoarea P( , n)

Exemplu

Mai jos este tabelul P pentru mulțimea S ={3, 1, 1, 2, 2, 1} folosită mai sus:

Analiză

Acest algoritm rulează în timp O ( KN ) , unde N este numărul de elemente din setul de intrare și K este suma elementelor din setul de intrare.

Algoritmul poate fi extins la problema multipartiției k -part, dar necesită O ( n ( k − 1) m k − 1 ) memorie , unde m este cel mai mare număr din setul de intrare, ceea ce face algoritmul practic lipsit de sens chiar și pentru k = 3 , cu excepția cazului în care nu sunt date numere foarte mici ca intrare [2] .

Un caz special al problemei sumei subsetului

Problema partiției poate fi considerată ca un caz special al problemei sumei submulțimii, iar soluția de programare dinamică în timp pseudopolinomială dată mai sus este generalizată la problema sumei submulților .

Algoritmi de aproximare

Există niște algoritmi euristici pentru aproximarea problemei de optimizare a partițiilor. Ele pot fi extinse la algoritmi de timp liniar exact [2] .

Algoritm lacom

O abordare a problemei, care imită modul în care copilul unui partener se joacă, este un algoritm lacom care repetă numerele în ordine descrescătoare și adaugă fiecare număr la o sumă mai mică. Această abordare are O ( n log n ) timp de rulare . Acest algoritm euristic funcționează bine în practică dacă numerele din mulțime sunt aproximativ de aceeași ordine, totuși nu se garantează că algoritmul va produce cea mai bună partiție posibilă. De exemplu, având în vedere setul S ={4, 5, 6, 7, 8} ca intrare, acest algoritm lacom ar avea ca rezultat o împărțire a lui S în subseturile {4, 5, 8} și {6, 7}. Cu toate acestea, S are o partiție exact echilibrată în subseturile {7, 8} și {4, 5, 6}.

Se știe că această abordare lacomă oferă o aproximare de 7 ⁄ 6 la soluția optimă a versiunii de optimizare. Adică, dacă rezultatul algoritmului greedy produce două seturi A și B , atunci , unde OPT este dimensiunea celui mai mare set din cea mai bună partiție [3] . Mai jos este un exemplu (în Python ) de algoritm lacom.

def find_partition ( int_list ): " Partiționați `int_list` în două seturi cu sume egale " A = set () B = set () for n in sorted ( int_list , reverse = True ): dacă sum ( A ) < sum ( B ) : A . adaugă ( n ) altfel : B . adaugă ( n ) return ( A , B )

Algoritmul poate fi extins la cazuri de k > 2 seturi - alegeți k elementele cele mai mari, distribuiți-le pe k seturi, apoi repetați peste numerele rămase în ordine descrescătoare și adăugați-le la mulțime cu o sumă mai mică (versiunea simplă de mai sus corespunde la k = 2 ). Această versiune rulează în timp O (2 k n 2 ) și se știe că oferă o aproximare [3] . Astfel, avem o schemă de timp polinomială aproximativă (PTAS) pentru problema de partiționare, deși nu este o schemă de timp polinomială complet aproximativă (timpul de rulare este exponențial pentru nivelul dorit de aproximare garantată). Cu toate acestea, există variante ale acestei idei care sunt scheme de timp polinomiale complet aproximative pentru problema sumei submulțimii și, prin urmare, și pentru problema partiției [4] [5] .

Algoritm de diferență

O altă euristică este Metoda celor mai mari diferențe (LDM) [6] , care este numită euristica Karmarkar - Karp [2] după oamenii de știință care au publicat metoda în 1982 [7] . MNR are două faze. Prima fază a algoritmului ia cele mai mari două numere din intrare și le înlocuiește cu diferența. Repetați operația până când rămâne un număr. Înlocuirea reprezintă o decizie de a plasa două numere în submulțimi diferite, dar în care seturi sunt plasate aceste numere, decizia nu se ia. La sfârșitul primei faze, numărul unic rămas este diferența dintre cele două sume de subseturi. La a doua etapă se construiește soluția actuală [1] .

Algoritmul euristic de diferență funcționează mai bine decât algoritmul lacom, dar rămâne slab pentru probleme în care numerele depind exponențial de mărimea mulțimii [1] .

Următorul cod Java reprezintă prima fază a algoritmului Karmarkar-Karp. Algoritmul folosește heap -ul pentru a găsi eficient perechea de numere cele mai mari dintre cele rămase.

int karmarkarKarpPartition ( int [] baseArr ) { // creați heap maxim PriorityQueue < Integer > heap = new PriorityQueue < Integer > ( lungimeArr . bază , REVERSE_INT_CMP ); for ( int value : baseArr ) { heap . adăugare ( valoare ); } în timp ce ( heap . size () > 1 ) { int val1 = heap . sondaj (); int val2 = heap . sondaj (); grămada . adaugă ( val1 - val2 ); } înapoi grămada . sondaj (); }

Alte abordări

Există, de asemenea, algoritmi de reducere a timpului bazați pe euristica diferențelor care găsesc mai întâi soluția obținută prin euristica diferenței, apoi se găsesc soluții progresiv mai bune dacă timpul o permite ( creșterea exponențială a timpului de rulare este posibilă pentru a obține soluția optimă în cel mai rău caz). caz) [8] [9] .

Cazuri dificile

Seturile cu o singură partiție sau fără partiții sunt adesea cele mai dificile (sau cele mai risipitoare) pentru a obține o decizie cu privire la dimensiunea intrării. Dacă valorile sunt mici în comparație cu dimensiunea setului, sunt mai probabile partiții bune. Se știe că problema suferă o „ tranziție de fază ” atunci când partițiile bune sunt cele mai probabile pentru unele seturi și puțin probabil pentru altele. Dacă m este numărul de biți necesari pentru a exprima orice număr din mulțime și n este dimensiunea mulțimii, atunci pentru problema are mai des mai multe soluții, iar pentru problemă mai des are o soluție sau nicio soluție. Pe măsură ce n și m devin mai mari, probabilitatea unei partiții bune tinde la 1 și, respectiv, a unei partiții proaste la 0. Acest fapt s-a bazat inițial pe rezultatele empirice ale lui Gent și Walsh [10] , apoi pe metodele fizicii statistice (Mertens [11] [12] ) și, în final, faptul a fost dovedit de Borgs, Chayes și Pittel. [13] .

Variante și generalizări

Există o problemă despre 3-partiția unui set de numere , care caută o partiție a mulțimii S în | S |/3 triple, fiecare triplă cu aceeași cantitate. Această problemă este complet diferită de problema partiției și nu are un algoritm de timp de rulare pseudopolinom, cu excepția cazului în care P=NP [14] .

Problema împărțirii în mai multe mulțimi generalizează versiunea de optimizare a problemei de divizare. Aici, scopul este de a împărți o mulțime sau o mulțime de n numere întregi într-un număr dat k de submulțimi, minimizând diferența dintre cea mai mică și cea mai mare sumă de numere din submulțimi [2] .

Alte generalizări ale problemei de partiționare pot fi găsite în lucrarea „ The Containerizing Problem ”.

Versiune probabilistică

O problemă înrudită, oarecum asemănătoare cu paradoxul zilei de naștere , este găsirea unei mărimi a mulțimii de intrare pentru care probabilitatea existenței unei soluții este 0,5, având în vedere că fiecare element al mulțimii este ales aleatoriu între 1 și o anumită valoare dată.

Soluția la această problemă poate fi paradoxală. De exemplu, atunci când aleg aleatoriu numere întregi între 1 și un milion, mulți oameni cred că răspunsul va fi mii, zeci de mii sau chiar sute de mii, când de fapt, răspunsul corect va fi aproximativ 23 (pentru detalii, vezi articolul Problemă de partiționare ).

Note

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

Literatură