Egy számhalmaz particionálásának problémája

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 27-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Egy számhalmaz particionálásának problémája annak meghatározása, hogy egy adott S pozitív egész számok többhalmaza felosztható -e két S 1 és S 2 részhalmazra úgy, hogy az S 1 számok összege egyenlő az S -ből származó számok összegével. 2 . Bár a számfelosztási probléma NP-teljes , létezik egy pszeudopolinomiális időmegoldás dinamikus programozással , és vannak heurisztikus algoritmusok számos konkrét probléma optimális vagy közelítő megoldására. Emiatt a problémát "a legegyszerűbb NP-nehéz feladatnak" [1] nevezik .

A felosztási feladatnak van egy optimalizálási változata , amelyben az S multihalmazt két S 1 és S 2 részhalmazra kell felosztani úgy , hogy az S 1 elemeinek összege és az S elemeinek összege közötti különbség 2 minimális. Az optimalizálási változat NP-kemény , de a gyakorlatban hatékonyan megoldható [2] .

Példák

Adott egy S ={3,1,1,2,2,1} halmaz, két S 1 ={1,1,1,2} és S 2 ={2,3} halmaz megvalósítható megoldás a particionálási problémára. . Mindkét halmaznak 5 összege van , és ezek S partíciói . Vegye figyelembe, hogy ez a megoldás nem egyedi. S 1 ={3,1,1} és S 2 ={2,2,1} egy másik megoldás.

Nem minden pozitív egész halmaz osztható két egyenlő összegű részre. Példa egy ilyen halmazra: S = {2,5}.

Pszeudopolinomiális idő algoritmus

A probléma megoldható dinamikus programozással , amennyiben a halmaz mérete és a halmazban lévő egész számok összege nem túl nagy ahhoz, hogy a memóriaigény teljesíthetetlen legyen.

Az algoritmus bemenetét ábrázoljuk az űrlap listájaként:

S=x 1 , ..., x n

Legyen N az S halmaz elemeinek száma . Legyen K az S halmaz összes elemének összege . Vagyis K = x 1 + ... + x n . Összeállítunk egy algoritmust, amely meghatározza, hogy van-e olyan S részhalmaz , amelynek elemeinek összege egyenlő -val . Ha a részhalmaz létezik, akkor:

ha K páros, akkor az S halmaz maradéka is megadja ha K páratlan, az S halmaz maradéka adja az összeget . Ez a lehető legjobb megoldás.

Ismétlődő kapcsolatok

Meg akarjuk határozni, hogy van-e olyan S részhalmaz , amelynek elemeinek összege . Legyen:

p ( i , j ) igaz , ha van egy részhalmaz az { x 1 , ..., x j } között, amelynek elemei összeadódnak i -vel, ellenkező esetben pedig hamis .

Ekkor p ( , n ) akkor és csak akkor igaz , ha létezik S -nek olyan részhalmaza, amelynek összege . Algoritmusunk célja p ( , n ) kiszámítása. Ennek eléréséhez a következő ismétlődő képletekkel rendelkezünk :

p ( i , j ) igaz, ha vagy p ( i , j - 1) igaz, vagy p ( i - x j , j - 1) igaz p ( i , j ) egyébként hamisra értékeli

Ennek oka a következő: van néhány S részhalmaz , amelynek összege a számokra egyenlő i -vel

x 1 , ..., x j

akkor és csak akkor, ha a kettő közül az egyik igaz:

van egy { x 1 , ..., x j-1 } részhalmaz, amely az i összeget adja ; van egy { x 1 , ..., x j-1 } részhalmaz, amely az i − x j összeget adja , mivel x j + ennek a részhalmaznak az összege = i .

Pszeudopolinomiális algoritmus

Az algoritmus összeállít egy n méretű táblázatot, amely tartalmazza a rekurziós értékeket, ahol az értékek összege és az elemek száma. Amikor az egész asztal megtelt, térjen vissza . Alul a P táblázat látható . Az ábrán kék nyíl az egyik blokkról a másikra, ha a végső blokk értéke függhet a forrásblokk értékétől. Ez a függőség egy rekurzív reláció tulajdonsága.

INPUT: Egész számok listája S OUTPUT: Igaz, ha S két részhalmazra osztható, amelyek összege megegyezik 1 függvény find_partition ( S ): 2n ← |S| 3 K ← összeg(S) 4 P ← üres ( + 1) méretű logikai táblázat (n + 1) 5 értékkel 5 inicializálja a P tábla felső sorát ( P (0,x) ) igazra 6 inicializálja a P tábla bal szélső oszlopát ( P (x, 0) ) , kivéve a P(0, 0) cellát , hamisra 7 i esetén 1 - től 8 - ig j esetén 1 -től n -ig 9 , ha (iS[j-1]) >= 0 10 P(i, j) ← P(i, j-1) vagy P(iS[j-1], j-1) 11 else 12 P(i, j) ← P(i, j-1) 13 visszatérés érték P( , n)

Példa

Az alábbiakban látható a fent használt S ={3, 1, 1, 2, 2, 1} halmaz P táblázata :

Elemzés

Ez az algoritmus O ( KN ) időben fut , ahol N a bemeneti halmaz elemeinek száma, K pedig a bemeneti halmaz elemeinek összege.

Az algoritmus kiterjeszthető a k -részes többpartíciós feladatra, de O ( n ( k − 1) m k − 1 ) memóriát igényel , ahol m a legnagyobb szám a bemeneti halmazban, ami gyakorlatilag értelmetlenné teszi az algoritmust még k esetén is. = 3 , hacsak nem adunk meg nagyon kis számokat bemenetként [2] .

A részhalmazösszeg probléma speciális esete

A partíciós probléma felfogható a részhalmazösszeg-probléma speciális eseteként, és a fent megadott pszeudopolinomiális idődinamikus programozási megoldást általánosítjuk a részhalmazösszeg-problémára .

Közelítő algoritmusok

Létezik néhány heurisztikus algoritmus a partícióoptimalizálási probléma közelítésére . Kiterjeszthetők pontos lineáris idő algoritmusokra [2] .

Mohó algoritmus

A probléma egyik megközelítése, amely a partner gyermekének játékát utánozza, egy mohó algoritmus , amely csökkenő sorrendben iterálja a számokat, és minden számot hozzáad egy kisebb összeghez. Ennek a megközelítésnek O ( n log n ) futási ideje van . Ez a heurisztikus algoritmus a gyakorlatban jól működik, ha a halmazban lévő számok megközelítőleg azonos sorrendűek, azonban az algoritmus nem garantálja, hogy a lehető legjobb partíciót hozza létre. Például, ha az S ={4, 5, 6, 7, 8} halmazt bemenetként használjuk, ez a mohó algoritmus az S felosztását eredményezné {4, 5, 8} és {6, 7} részhalmazokra. Azonban S -nek van egy pontosan kiegyensúlyozott partíciója {7, 8} és {4, 5, 6} részhalmazokra.

Ez a mohó megközelítés köztudottan 7 ⁄ 6 -os közelítést ad az optimalizálási verzió optimális megoldásához. Vagyis ha a mohó algoritmus kimenete két A és B halmazt eredményez , akkor , ahol OPT a legjobb partíció legnagyobb halmazának mérete [3] . Az alábbiakban egy példa ( Python nyelven ) látható egy mohó algoritmusra.

def find_partition ( int_list ): "Az `int_list' felosztása két halmazra egyenlő összegekkel " A = set () B = set () for n in rendezve ( int_list , fordított = True ): if sum ( A ) < sum ( B ) : A. _ add ( n ) else : B. _ add ( n ) return ( A , B )

Az algoritmus kiterjeszthető k > 2 halmaz eseteire - válassza ki a k ​​legnagyobb elemet, ossza el őket k halmazra, majd iterálja a fennmaradó számokat csökkenő sorrendben, és adja hozzá őket a halmazhoz kisebb összeggel (a fenti egyszerű változat megfelel k = 2 - hez ). Ez a változat O (2 k n 2 ) időben fut, és köztudottan közelítést ad [3] . Így van egy közelítő polinomiális idősémánk (PTAS) a particionálási problémára, bár ez nem teljesen közelítő polinomiális időséma (a futási idő exponenciális a garantált közelítés kívánt szintjéhez). Ennek az elképzelésnek azonban vannak olyan változatai, amelyek teljesen közelítő polinomiális idősémák a részhalmazösszeg-probléma, és így a partíciós probléma számára is [4] [5] .

Különbség algoritmus

Egy másik heurisztika a Largest Difference Method (LDM) [6] , amelyet a módszert 1982-ben publikáló tudósok után Karmarkar - Karp heurisztikának [2] neveznek [7] . Az MNR-nek két fázisa van. Az algoritmus első fázisa a két legnagyobb számot veszi ki a bemenetből, és helyettesíti a különbséggel. Addig ismételje a műveletet, amíg egy szám nem marad. A helyettesítés azt a döntést jelenti, hogy két számot különböző részhalmazokba helyeznek, de amely halmazba kerülnek ezek a számok, a döntés nem születik meg. Az első fázis végén a fennmaradó egyetlen szám a két részhalmaz összegének különbsége. A második szakaszban megépül a tényleges megoldás [1] .

A különbség-heurisztikus algoritmus jobban teljesít, mint a mohó algoritmus, de gyenge marad olyan problémák esetén, amelyekben a számok exponenciálisan függenek a halmaz méretétől [1] .

A következő Java kód a Karmarkar–Karp algoritmus első fázisát képviseli. Az algoritmus a kupac segítségével hatékonyan megkeresi a fennmaradó számok közül a legnagyobb számpárt.

int karmarkarKarpPartition ( int [] baseArr ) { // max kupac létrehozása PriorityQueue < Integer > heap = new PriorityQueue < Integer > ( baseArr . long , REVERSE_INT_CMP ); for ( int érték : baseArr ) { kupac . hozzáad ( érték ); } while ( kupac . méret ( ) > 1 ) { int val1 = kupac . szavazás (); int val2 = kupac . szavazás (); kupac . add ( érték1 - érték2 ); } visszatérő kupac . szavazás (); }

Egyéb megközelítések

Léteznek a különbség-heurisztikán alapuló idővágási algoritmusok is , amelyek először megtalálják a differencia-heurisztikával kapott megoldást, majd fokozatosan jobb megoldásokat találnak, ha az idő engedi ( a futási idő exponenciális növekedése lehetséges az optimális megoldás eléréséhez a legrosszabb esetben eset) [8] [9] .

Nehéz esetek

Azok a készletek, amelyeknek csak egy partíciója vagy nincs partíciója, gyakran a legnehezebb (vagy a legpazarlóbb) döntést hozni a bemenet méretéről. Ha az értékek kicsik a készlet méretéhez képest, valószínűbb a jó partíció. A probléma köztudottan " fázisváltáson " megy keresztül, amikor a jó partíciók a legvalószínűbbek bizonyos halmazoknál, míg mások számára nem valószínű. Ha m a bitek száma a halmazból tetszőleges szám kifejezéséhez, és n a halmaz mérete, akkor a feladatnak gyakrabban sok megoldása van, és a feladatnak gyakrabban van egy megoldása, vagy nincs megoldása. Ahogy n és m növekszik, a jó partíció valószínűsége 1-re, a rossz partíció pedig 0-ra hajlik. Ez a tény kezdetben Gent és Walsh empirikus eredményein [10] , majd a statisztikus fizika módszerein (Mertens [11] [12] ) alapult, végül Borgs, Chayes és Pittel igazolta. [13] .

Változatok és általánosítások

Probléma van egy számhalmaz 3-partíciójával kapcsolatban , amely az S halmaz partícióját keresi | S |/3 tripla, mindegyik hármas azonos mennyiséggel. Ez a probléma teljesen különbözik a partíciós problémától, és nincs pszeudopolinomiális futási idő algoritmusa, hacsak nem P=NP [14] .

A több halmazra való felosztás problémája általánosítja a felosztási probléma optimalizálási változatát. Itt az a cél, hogy egy n egész számból álló halmazt vagy multihalmazt particionáljanak adott számú részhalmazra, minimalizálva a részhalmazok legkisebb és legnagyobb számösszege közötti különbséget [ 2] .

A particionálási probléma további általánosításai a " The Containerizing Problem " című cikkben találhatók.

Valószínűségi változat

A születésnapi paradoxonhoz némileg hasonló probléma egy olyan bemeneti halmazméret megtalálása, amelyre a megoldás létezésének valószínűsége 0,5, feltéve, hogy a halmaz minden eleme véletlenszerűen van kiválasztva 1 és valamilyen adott érték között.

A probléma megoldása paradox lehet. Például amikor véletlenszerűen választunk ki 1 és egymillió közötti egész számokat, sokan azt gondolják, hogy ezrek, tízezrek vagy akár százezrek is a válasz, holott a helyes válasz körülbelül 23 lesz (a részleteket lásd a cikk Particionálási probléma ).

Jegyzetek

  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, Tóth, 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 és Johnson 1979 , p. 96–105.

Irodalom