Problém rozdělení množiny čísel

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 27. října 2021; ověření vyžaduje 1 úpravu .

Problém rozdělení množiny čísel je problém určit, zda lze danou množinu S kladných celých čísel rozdělit na dvě podmnožiny S 1 a S 2 tak, že součet čísel z S 1 je roven součtu čísel z S 2 . Ačkoli je problém dělení čísel NP-úplný , existuje pseudopolynomiální časové řešení dynamickým programováním a existují heuristické algoritmy pro řešení mnoha konkrétních problémů buď optimálně nebo přibližně. Z tohoto důvodu se problém nazývá „nejjednodušší NP-těžký problém“ [1] .

Existuje optimalizační verze problému rozdělení, ve které je požadováno rozdělit multimnožinu S na dvě podmnožiny S1 a S2 , takže rozdíl mezi součtem prvků S1 a součtem prvků S 2 je minimální. Optimalizační verze je NP-hard , ale v praxi může být efektivně vyřešena [2] .

Příklady

Vzhledem k množině S ={3,1,1,2,2,1} jsou dvě množiny S 1 ={1,1,1,2} a S 2 ={2,3} proveditelným řešením problému dělení . Obě množiny mají součet 5 a jsou dělením S . Upozorňujeme, že toto řešení není jedinečné. S 1 ={3,1,1} a S 2 ={2,2,1} je další řešení.

Ne každá multimnožina kladných celých čísel má rozdělení na dvě části se stejnými součty. Příkladem takové množiny je S = {2,5}.

Pseudopolynomiální časový algoritmus

Problém lze vyřešit pomocí dynamického programování , pokud velikost množiny a velikost součtu celých čísel v množině nejsou příliš velké, aby byly požadavky na paměť neproveditelné.

Představme si vstup algoritmu jako seznam formuláře:

S = x 1 , ..., x n

Nechť N je počet prvků v množině S . Nechť K je součet všech prvků z množiny S . To znamená, že K = x 1 + ... + x n . Sestavíme algoritmus, který určí, zda existuje podmnožina S , jejíž součet prvků je roven . Pokud podmnožina existuje, pak:

je -li K sudé, pak dává i zbytek množiny S je -li K liché, zbytek množiny S dá součet . Toto je nejlepší možné řešení.

Opakující se vztahy

Chceme určit, zda existuje podmnožina S , jejíž součet prvků je . Nechat:

p ( i , j ) má hodnotu True , pokud mezi { x 1 , ..., x j } existuje podmnožina , jejíž prvky se sčítají k i a jinak False .

Pak p ( , n ) je pravdivé tehdy a jen tehdy, když existuje podmnožina S , jejíž součet je . Cílem našeho algoritmu je vypočítat p ( , n ). Abychom toho dosáhli, máme následující opakující se vzorce :

p ( i , j ) je pravda, pokud buď p ( i , j − 1) je pravda, nebo p ( i − x j , j − 1) je pravda p ( i , j ) se jinak vyhodnotí jako False

Důvod je následující: existuje nějaká podmnožina S , jejíž součet je roven i pro čísla

x 1 , ..., x j

tehdy a jen tehdy, je-li jedna z těchto dvou pravdivá:

existuje podmnožina { x 1 , ..., x j-1 }, která dává součet i ; existuje podmnožina { x 1 , ..., x j-1 }, která dává součet i − x j , protože x j + součet této podmnožiny = i .

Pseudopolynomiální algoritmus

Algoritmus vytvoří tabulku velikosti n obsahující hodnoty rekurze, kde je součet hodnot a je počet prvků. Když je celý stůl plný, vraťte se . Níže je tabulka P. Na obrázku modrá šipka z jednoho bloku do druhého, pokud hodnota konečného bloku může záviset na hodnotě zdrojového bloku. Tato závislost je vlastností rekurzivního vztahu.

VSTUP: Seznam celých čísel S VÝSTUP: Pravda, pokud lze S rozdělit na dvě podmnožiny, které mají stejné součty 1 funkce find_partition ( S ): 2n ← |S| 3 K ← součet(S) 4 P ← prázdná booleovská tabulka velikosti ( + 1) krát (n + 1) 5 inicializovat horní řádek ( P(0,x) ) tabulky P na hodnotu True 6 inicializovat sloupec zcela vlevo ( P(x, 0) ) tabulky P , kromě buňky P(0, 0) na hodnotu False 7 pro i od 1 do 8 pro j od 1 do n 9 , pokud (iS[j-1]) >= 0 10 P(i, j) ← P(i, j-1) nebo P(iS[j-1], j-1) 11 jinak 12 P(i, j) ← P(i, j-1) 13 návrat hodnota P( , n)

Příklad

Níže je tabulka P pro množinu S ={3, 1, 1, 2, 2, 1} použitou výše:

Analýza

Tento algoritmus běží v čase O ( KN ) , kde N je počet prvků ve vstupní sadě a K je součet prvků ve vstupní sadě.

Algoritmus lze rozšířit na problém s více oddíly k -částí, ale vyžaduje O ( n ( k − 1) m k − 1 ) paměti , kde m je největší číslo ve vstupní množině, takže algoritmus prakticky ztrácí smysl i pro k = 3 , pokud nejsou jako vstup uvedena velmi malá čísla [2] .

Speciální případ problému součtu podmnožiny

Problém rozdělení lze považovat za speciální případ problému součtu podmnožin a řešení dynamického programování v pseudopolynomiálním čase uvedené výše je zobecněno na problém součtu podmnožin .

Aproximační algoritmy

Existuje několik heuristických algoritmů pro aproximaci problému optimalizace oddílu. Mohou být rozšířeny na přesné lineární časové algoritmy [2] .

Greedy algoritmus

Jedním z přístupů k problému, který napodobuje způsob, jakým si hraje partnerovo dítě, je chamtivý algoritmus , který iteruje čísla v sestupném pořadí a každé číslo přičte k menšímu součtu. Tento přístup má dobu běhu O ( n log n ) . Tento heuristický algoritmus funguje dobře v praxi, pokud jsou čísla v množině přibližně stejného řádu, ale není zaručeno, že algoritmus vytvoří nejlepší možný oddíl. Například, dáme-li jako vstup množinu S ={4, 5, 6, 7, 8}, tento chamtivý algoritmus by vedl k rozdělení S do podmnožin {4, 5, 8} a {6, 7}. S má však přesné vyvážené rozdělení na podmnožiny {7, 8} a {4, 5, 6} .

Je známo, že tento chamtivý přístup poskytuje optimálnímu řešení optimalizační verze 7⁄6 aproximaci . To znamená, že pokud výstup chamtivého algoritmu poskytne dvě množiny A a B , pak , kde OPT je velikost největší množiny v nejlepším oddílu [3] . Níže je uveden příklad (v Pythonu ) chamtivého algoritmu.

def find_partition ( int_list ): "Rozdělení `int_list` na dvě množiny se stejnými součty " A = množina () B = množina () pro n v seřazeném ( int_list , obráceně = True ): if součet ( A ) < součet ( B ) : A. _ přidat ( n ) jinak : B. _ přidat ( n ) vrátit ( A , B )

Algoritmus lze rozšířit na případy k > 2 množin - vyberte k největších prvků, rozložte je do k množin, poté iterujte zbývající čísla v sestupném pořadí a přidejte je do množiny s menším součtem (odpovídá jednoduchá verze výše až k = 2 ). Tato verze běží v čase O (2 k n 2 ) a je známo, že poskytuje aproximaci [3] . Máme tedy přibližné polynomiální časové schéma (PTAS) pro problém rozdělení, i když to není plně přibližné polynomiální časové schéma (doba běhu je exponenciální pro požadovanou úroveň zaručené aproximace). Existují však varianty této myšlenky, které jsou zcela přibližnými polynomiálními časovými schématy pro problém součtu podmnožin, a tedy i pro problém rozdělení [4] [5] .

Diferenční algoritmus

Další heuristikou je metoda největšího rozdílu (LDM) [6] , která se nazývá Karmarkar - Karp heuristika [2] podle vědců, kteří metodu publikovali v roce 1982 [7] . MNR má dvě fáze. První fáze algoritmu vezme dvě největší čísla ze vstupu a nahradí je rozdílem. Opakujte operaci, dokud nezůstane jedno číslo. Substituce představuje rozhodnutí umístit dvě čísla do různých podmnožin, ale ve kterých sadách jsou tato čísla umístěna, rozhodnutí není učiněno. Na konci první fáze je zbývající jediné číslo rozdílem součtů dvou podmnožin. Ve druhé fázi je postaveno vlastní řešení [1] .

Rozdílový heuristický algoritmus funguje lépe než chamtivý algoritmus, ale zůstává špatný pro problémy, ve kterých čísla exponenciálně závisí na velikosti množiny [1] .

Následující kód Java představuje první fázi algoritmu Karmarkar–Karp. Algoritmus používá haldu k efektivnímu nalezení dvojice největších čísel mezi zbývajícími.

int karmarkarKarpPartition ( int [] baseArr ) { // vytvoření max. haldy PriorityQueue < Integer > halda = new PriorityQueue < Integer > ( baseArr . length , REVERSE_INT_CMP ); for ( int value : baseArr ) { heap . přidat ( hodnota ); } while ( halda . velikost () > 1 ) { int val1 = halda . anketa (); int val2 = halda . anketa (); hromada . přidat ( val1 - val2 ); } vrátit hromadu . anketa (); }

Jiné přístupy

Existují také algoritmy časového zkrácení založené na diferenční heuristice, které nejprve najdou řešení získané diferenční heuristikou, poté se postupně nalézají lepší řešení, pokud to čas dovolí ( exponenciální růst provozní doby je možný pro získání optimálního řešení v nejhorším případě případ) [8] [9] .

Obtížné případy

U sad s jedním nebo žádným oddílem je často nejobtížnější (nebo nejplýtvavější) získat rozhodnutí o velikosti vstupu. Pokud jsou hodnoty ve srovnání s velikostí sady malé, jsou pravděpodobnější dobré oddíly. Je známo, že problém prochází " fázovým přechodem ", kdy jsou dobré oddíly nejpravděpodobnější pro některé sady a nepravděpodobné pro jiné. Jestliže m je počet bitů potřebných k vyjádření libovolného čísla z množiny a n je velikost množiny, pak pro problém má častěji mnoho řešení a pro problém má častěji jedno řešení nebo nemá žádné řešení. Jak se n a m zvětšují, pravděpodobnost dobrého rozdělení má tendenci k 1 a špatného rozdělení k 0, v tomto pořadí. Tato skutečnost byla zpočátku založena na empirických výsledcích Genta a Walshe [10] , poté na metodách statistické fyziky (Mertens [11] [12] ) a nakonec tuto skutečnost dokázali Borgs, Chayes a Pittel [13] .

Varianty a zobecnění

Nastal problém s 3-dílením množiny čísel , který hledá dělení množiny S do | S |/3 trojnásobek, každý trojnásobek se stejným množstvím. Tento problém je zcela odlišný od problému rozdělení a nemá algoritmus pseudopolynomiální doby běhu, pokud není P=NP [14] .

Problém rozdělení do několika sad zobecňuje optimalizační verzi problému rozdělení. Zde je cílem rozdělit množinu nebo multimnožinu n celých čísel do daného počtu k podmnožin, čímž se minimalizuje rozdíl mezi nejmenším a největším součtem čísel v podmnožinách [2] .

Další zobecnění problému dělení lze nalézt v článku " Problém kontejnerování ".

Pravděpodobnostní verze

Související problém, poněkud podobný narozeninovému paradoxu , má najít vstupní velikost množiny, pro kterou je pravděpodobnost existence řešení 0,5, za předpokladu, že každý prvek množiny je náhodně vybrán mezi 1 a nějakou danou hodnotou.

Řešení tohoto problému může být paradoxní. Například při náhodném výběru celých čísel mezi 1 a jedním milionem si mnoho lidí myslí, že odpověď bude tisíce, desetitisíce nebo dokonce statisíce, i když ve skutečnosti bude správná odpověď asi 23 (podrobnosti viz článek Problém s oddíly ).

Poznámky

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

Literatura