e-mail    Debatní kniha    Mapa stránek    Hlavní  
 perličky 
 

Problém dvou loupežníků

RNDr. Vladimír Zábrodský

Praktická poznámka k jednomu prakticky neřešitelnému problému

-----------------------------------------------------------------------------
Upozornění: v textu (nikoli v programu samotném) jsou vloženy příkazy TeXu pro
matematické indexování (začínají a končí znakem $).
-----------------------------------------------------------------------------

Problém dvou loupežníků spočívá v otázce, zda lze rozdělit daných N čísel do dvou skupin tak, aby součet čísel v obou skupinách byl stejný (tj. aby se dva loupežníci mohli spravedlivě rozdělit o kořist N věcí, jejichž ceny jednotlivá čísla představují). Není-li čísel mnoho, najdou "laici" řešení obvykle za několik sekund, i když není znám jiný algoritmus, než postupné probírání všech možných rozdělení N čísel do dvou skupin (a těch je celkem 2N). Už spravedlivé rozdělení věcí z trochu větší kanceláře (N 50) nemá smysl řešit ani na nejrychlejším počítači na světě.

Odstavec, který jste právě dočetli, shrnuje vše podstatné, co je o problému dvou loupežníků napsáno v článku [1]. Z pohledu teorie výpočtové složitosti je tento problém prakticky neřešitelný. Ale podíval se na něj někdo očima těch loupežníků? Jak mám vlastně postupovat, když se ve své praxi setkám s úlohou spravedlivě rozdělit třeba tisíc zadaných čísel? {\it Vzdej to}, čtu mezi řádky v [1].

V tomto příspěvku nejprve dokážu, že problém dvou loupežníků je možné redukovat na problém plnění batohu z článku [4]. V nejhorším případě je pro jeho vyřešení nutné prozkoumat zhruba $2N-1$ možností. Dále popíšu algoritmus řešení -- výsledek hledání vhodného kritéria výběru, které by mohlo podstatně snížit počet zkoumaných kandidátů. Na příkladech pak chci ukázat, že řešení můžeme získat pro relativně velké hodnoty $N$ v rozumné době i na "obyčejném" počítači.

Algoritmus
Bez újmy na obecnosti předpokládejme, že zadaná čísla $A_{1}, A_{2}, ..., A_{N}, N>1$ jsou přirozená, tvoří neklesající posloupnost a jejich součet je sudé číslo. Pro $N=2$ (resp. $N=3$) nalezneme řešení porovnáním hodnot $A_{1}, A_{2}$ (resp. $A_{1}+A_{2}, A_{3}$). Pro $N>3$ můžeme -- místo toho abychom rozdělovali posloupnost na dvě skupiny -- hledat jen skupinu obsahující prvek $A_{N}$. Označme $Ls_{K}=A_{1}+A_{2}+ ... +A_{K}$ a $Pc=(Ls_{N} div 2)-A_{N}$. Řešení se snadno určí, pokud je $A_{1}>=Pc$. V opačném případě je řešením odpověď na otázku: Existuje v neklesající posloupnosti přirozených čísel $A_{1}, ..., A_{N-1}$, splňující podmínku:

$(Ls_{N} mod 2)=0, A_{1}3$ \hfill (1)

skupina prvků, jejichž součet se rovná přirozenému číslu} $Pc$?

Předpokládejme obecně, že je zadáno vzestupně uspořádané pole přirozených čísel $A$ rozsahu $R$, přirozené číslo $C$ a platí počáteční podmínka $A_{1}<=C1$. Z pole $A$ se má vybrat skupina prvků tak, aby jejich součet byl $C$.

Uvedu jednoduchý příklad algoritmu, kterým se neprobírají všechny možnosti.

Nejprve se určí buď index $K$ takový, že $Ls_{K-1}C$, nebo index $P$ takový, že platí $Ls_{P}=C$ (v tomto případě je skupina nalezena a patří do ní také prvky $A_{1}, ..., A_{P}$; výpočet končí). Z $Ls_{K-1}

Dále se určí největší index $J (J>=K-1)$ takový, že $A_{J}<=C$ (je-li $A_{J}=C$, je skupina nalezena a patří do ní také prvek $A_{J}$; výpočet končí). Aby skupina mohla existovat, nemůže být $J=K-1$, protože součet $K-1$ nejmenších prvků je menší než $C$, ale už $A_{K}$ je větší než $C$.

Pro každé $L=K, ..., J$ může hledanou skupinu tvořit prvek $A_{L}$ a ještě aspoň jeden z prvků $A_{1}, ..., A_{L-1}$, platí-li podmínka $A_{1}<=C-A_{L}1$. Ale to už jsme jen krůček od vyřešení problému.

V uspořádaném poli $A$ rozsahu $L-1$ totiž můžeme stejným postupem hledat skupinu prvků, jejichž součet se rovná přirozenému číslu $C-A_{L}$.

Popis tohoto algoritmu v jazyce Turbo Pascal 6.0 je uveden na obrázku. Nazval jsem ho Laik, protože najde řešení obvykle za několik sekund.

Indexy polí $A$, $Ls$ a $V$ jsou typu index=$1..N$ a prvky těchto polí jsou po řadě typu longint, longint (předpokládají se výpočty s velkými přirozenými čísly) a index. Pole $V$ slouží k postupnému ukládání indexů prvků hledané skupiny. Jeho momentální naplnění určuje hodnota proměnné $U$.

Problém se rozdělí na více podproblémů menšího rozsahu rekurzívním voláním procedury Laik. Návrat z ní znamená, že skupina dosud nebyla nalezena; je buď přechodem na řešení dalšího podproblému, nebo návratem do hlavního programu, jestliže skupina neexistuje. Nalezením skupiny provádění algoritmu končí; v jeho popisu je v tomto případě uveden příkaz volání procedury Nalezeno_Stop. Označíme-li hodnoty indexů, které se jí předají jako skutečné parametry, $D, E, B$ ($B=E$ nebo $B=1$), pak hledanou skupinu tvoří sestupně uspořádané prvky $A_{V_{1}}, ..., A_{V_{D}}$ a $A_{E}, ..., A_{B}$.

Aby procedura Laik byla korektní, musí se v Nalezeno_Stop ukončit provádění celého programu standardní procedurou Halt.

Má-li se řešit problém dvou loupežníků pro pole $A$ rozsahu $N$, splňující podmínku (1), vypočtou se hodnoty $Ls_{1}, ..., Ls_{N-1}$; index prvního známého prvku hledané skupiny se uloží do pole $V (V_{1}:=N)$ a provede se příkaz Laik$(N-1, 1, Pc)$.

procedure Laik(R, U: index; C: longint); var H, K, P: index; begin K:=1; H:=R-1; while K<=H do begin P:=(K+H) div 2; if Ls[P]<C then K:=P+1 else if Ls[P]>C then H:=P-1 else Nalezeno_Stop(U, P, 1); end; while A[R]>C do R:=R-1; if A[R]=C then Nalezeno_Stop(U, R, R); while (K<=R) and (A[1]<=C-A[K]) do begin V[U+1]:=K; Laik(K-1, U+1, C-A[K]); K:=K+1; end; end;

Příklady řešení
Při řešení problému dvou loupežníků má algoritmus Laik v nejhorším případě exponenciální časovou složitost.

Příklad 1
$A_{1}=2, A_{K}=A_{K-1}+100$

kde $K=2, ..., N$. Pro $N=29$ (resp. $N=30$) je k zjištění, že skupina neexistuje, zapotřebí zhruba 2,6 (resp. 4,5) miliónu vyvolání procedury Laik.

V příkladech 2 a 3 jsem použil následující program. Pro zadanou množinu čísel $M$ a čísla $N, T$ se provedl příkaz RandSeed:=$T$; pole $A$ se naplnilo $N$ čísly, pseudonáhodně vybranými funkcí Random z $M$; vypočetla se hodnota $Ls_{N}$; pole se vytřídilo a pokud nevyhovovalo podmínce (1), výběr čísel se opakoval, jinak se vypočetly hodnoty $Ls_{1}, ..., Ls_{N-1}$ a měřila se doba výpočtu procedury Laik (PC AT 386/40 MHz). Program se pro zadané $M$ a $N$ spustil vždy $S$-krát ($T=1, ..., S$).

Příklad 2
Množina $M$ obsahovala čísla od 1 do 65535. Pole $A$ se plnilo příkazem $A_{K}$ :=Random$(65535)+1, K=1, ..., N$. Pro $N=50, N=1000$ a $S=1000$ byla skupina vždy nalezena. Maximální doba výpočtu (Max) byla pro $N=50$ 66 ms ($T=139$) a pro $N=1000$ 55 ms ($T=955$). Pro $N=1000$ a libovolné $T$ bychom, například algoritmem z knihy [3, s. 35--36], kterým se probírají všechny možnosti, nezískali řešení ani za desítky let.

Jaký výsledek můžeme očekávat při dělení věcí z trochu větší kanceláře? Provedl jsem řadu zkoušek s daty převzatými z různých ceníků a katalogů. Reprezentují je následující dva příklady.

Příklad 3
Množinu $M$ tvořilo deset tisíc hodnot ze souboru Ceník (VPS ČKD Blansko). Po vynásobení stem by mohly představovat věci v ceně od 2 Kč do téměř 400 miliónů Kč. Prohlédněte si připojenou tabulku. Pro $N=20, 30, 40$ a $S=100$ jsou v ní uvedeny hodnoty: Neex -- počet výsledků "skupina neexistuje" a Max -- maximální doba výpočtu, vždy naměřená v případě, když skupina neexistovala.

Pro $N=50$ bychom se takového výsledku vůbec nedočkali. Z tabulky je ale vidět, že se hodnota Neex s růstem $N$ snižuje. Pro relativně velké hodnoty $N$ bude tedy skupina téměř vždy existovat. Můžeme ji určit v rozumné době, když z výsledků druhého příkladu navíc usuzuji, že počet vyhovujících skupin se s růstem $N$ zvyšuje? Pro $N=500$ a $S=1000$ jsem jen jednou musel výpočet (po 9 hodinách) násilně přerušit. Ve zbývajících případech byla skupina nalezena. Nejdéle za 96 minut, v průměru za 16,5 sekundy, v 967 případech výpočet netrval déle než 5 sekund.

N Neex Max[ms] 20 84 6 30 63 379 40 49 131 794

Příklad 4
V časopise Bajt (červenec 1993, č. 33) je na s. 123--135 (resp. s. 35) uveden seznam 202 počítačů (resp. 82 softwarových produktů) i s cenami. Loupežníci si mohou počítače spravedlivě rozdělit (v případě softwaru se postupuje podobně) takto:

Nejprve si vyberou libovolný počítač, na který každý z nich položí 50 centů (ceny jsou v dolarech a jejich součet je liché číslo); cenu tohoto počítače zvýší o jednu; návod na rozdělení pak určí algoritmem Laik do 8 sekund.

A jak se mohou dva loupežníci spravedlivě rozdělit o kořist, není-li počítač po ruce nebo algoritmus Laik přece jen zklame? Podle knihy [2, s. 158] si určí (třeba i losem), kdo z nich bude dělit (ten rozdělí lup na dvě části) a kdo vybírat (ten si vybere tu část, která se mu bude zdát výhodnější).

Literatura:
[1] Coufal, J., Hindls, R.: Proč výpočtová složitost? MAA, č. 2, 1993, s. 41--43; č. 4, 1993, s. 36-38.
[2] Kowal, S.: Matematika pro volné chvíle. SNTL, Praha 1985.
[3] Lipski, W.: Kombinatorika dlja programmistov. Mir, Moskva 1988.
[4] Vyskoč, J.: Kryptografia a výpočtová zložitosť. Informačné systémy, č. 3,1989, s. 261--282.




Pascal - hlavní
Překladače
Vlastní články
Převzaté články
Věci na stáhnutí
Odkazy k tématu
BP7 buglist
Chyba Run-time 200

BASIC