P-I-1 Večírek
Prvního hosta můžeme umístit dvěma způsoby - do jedné nebo do
druhé místnosti. Jakmile zvolíme jeho umístění (třeba do
místnosti 1), je nezbytné usadit do místnosti 2 všechny hosty,
s nimiž se první host nezná. Pokud by se mezi nimi našli dva,
kteří se neznají, úloha nemá žádné řešení. Jinak je umístíme do
místnosti 2 a jsme pak nuceni umístit do místnosti 1 všechny
takové hosty, s nimiž se někdo z místnosti 2 nezná. Podobně
postupujeme tak dlouho, dokud je nějaké umístění hostů takto
vynuceno. Jestliže jsme tímto postupem rozmístili všech N hostů,
jsme hotovi a řešením úlohy jsou původní 2 možnosti, s nimiž jsme
začínali u prvního hosta (všechna ostatní umístění byla vynucena
pravidly hry). Jestliže naopak zůstali nějací zatím neumístění
hosté, můžeme jednoho libovolného z nich umístit do jedné
z místností a začít od něj umisťovat další jako na začátku. Pokud
se nám takto K-krát stane, že někoho můžeme umístit libovolně,
existuje celkem 2K způsobů, jak lze všechny hosty rozdělit do
dvou místností.
Jedná se vlastně o klasickou úlohu teorie grafů. Hosté představují vrcholy grafu, hrany odpovídají vztahu "neznat se" mezi hosty. O takovémto grafu zjišťujeme, zda je bipartitní, tzn. zda lze jeho vrcholy rozdělit do dvou skupin tak, aby v rámci ani jedné skupiny nevedla žádná hrana. Pokud graf bipartitní není, úloha nemá řešení. Jestliže bipartitní je, počet přípustných rozdělení vrcholů do dvou skupin je roven 2^(počet komponent souvislosti). Komponenty souvislosti přitom není třeba zvlášť vyhledávat, neboť algoritmus na testování bipartitnosti si je určuje sám.
Algoritmus řešení této úlohy je založen na vhodném procházení grafu. Stejně jako při prostém určování komponent souvislosti grafu můžeme použít libovolný způsob procházení, do hloubky nebo do šířky. Hostům zařazeným do první místnosti přiřadíme hodnotu 1 a hostům z druhé místnosti hodnotu -1. Na začátku výpočtu není žádný host nijak zařazen (má přiřazenu hodnotu místnosti 0).
Konečnost výpočtu je dána tím, že v každém kroku je umístěn jeden host. Počet kroků výpočtu je tedy roven nejvýše počtu všech hostů N. Odtud plyne, že časová složitost algoritmu je úměrná N2, neboť každý krok výpočtu představuje provedení až kN operací pro vhodnou konstantu k (jeden průchod přes všechny "neznámé" právě zařazeného hosta).
Budeme souběžně sledovat, jak by bylo možné co nejvíce naložit "auta" o nosnostech 1, 2, 3, ..., C. Budeme brát jeden výrobek po druhém (v libovolném pořadí) a pomocí každého dalšího výrobku se vždy pokusíme zvětšit zaplnění všech uvažovaných aut. Nejlepší naložení auta nosnosti J s využitím prvních I výrobků získáme následující úvahou: Předpokládejme, že známe nejlepší možná naložení všech uvažovaných aut pomocí výběru z prvních I-1 výrobků. Nyní dostáváme navíc k dispozici ještě I-tý výrobek. Pokud je hmotnost tohoto výrobku větší než J, do J-tého auta se nevejde a nejlepší možné zaplnění auta velikosti J prvními I výrobky je proto stejné jako zaplnění prvními I-1 výrobky. V opačném případě buď k co nejlepšímu naložení auta velikosti J nový I-tý výrobek nepoužijeme, nebo ho použijeme. Z obou možností si vybereme tu příznivější, která vede k větší hmotnosti nákladu. Nyní nám už jenom zbývá popsat tyto dvě možnosti. Jestliže se rozhodneme I-tý výrobek nenaložit, bude zaplnění J-tého auta stejné jako dosud, tj. jako při optimálním zaplnění prvními I-1 výrobky. Jestliže naopak I-tý výrobek na J-té auto naložíme, můžeme snadno spočítat zbývající volný prostor v tomto autě jako rozdíl J minus hmotnost I-tého výrobku. Tento volný prostor potřebujeme co nejlépe zaplnit prvními I-1 výrobky. To však již umíme, neboť optimální naložení všech různých menších aut pomocí výběru z prvních I-1 výrobků známe.
Celý výpočet skončí ve chvíli, kdy zpracujeme všechny výrobky a získáme tak informace o nejlepším zaplnění všech uvažovaných aut libovolnými z uvažovaných výrobků. Údaj zaznamenaný u největšího auta nosnosti C udává, jak nejlépe je možné naložit toto auto. Je-li roven hodnotě C, přesné zaplnění auta je možné, v opačném případě možné není.
Programová realizace uvedeného algoritmu je poměrně snadná. Program je v podstatě tvořen dvěma vnořenými cykly. Vnější cyklus postupně prochází zadaných N výrobků, pro každý z nich se ve vnitřním cyklu přepočítává údaj o maximálním možném naložení aut o nosnostech od 1 do C. Program nemá ani příliš velké paměťové nároky. Vystačíme s jedním pracovnímim polem o C složkách, ve kterém si budeme evidovat pro každé z aut hodnotu jeho zatím nejlepšího zaplnění.
První postup řešení lze použít pouze tehdy, pokud hodnoty R, S dovolují pracovat v programu s polem velikosti SxR reprezentujícím obrazovku. (Jako první souřadnici budeme i nadále udávat vždy číslo sloupce, jako je tomu např. v knihovnách CRT a GRAPH v Turbo Pascalu.) V našem konkrétním případě činí paměťové nároky programu 300 x 200 x 1 byte = 60000 byte. Takto velké pole můžeme bez problémů používat i v programu pracujícím na PC v reálném modu. Každý prvek pole bude představovat jeden bod na obrazovce a bude udávat, zda je tento bod "volný" pro nové okno. Na začátku výpočtu bude hodnota všech prvků pole inicializována na 1 (všude je volno). V první fázi budeme číst ze vstupu údaje o jednotlivých oknech umístěných na obrazovce a plochu všech těchto oken vyznačíme v našem poli nulami. To vyžaduje vykonat maximálně O(NRS) operací, neboť každé z N oken může mít velikost až SxR. Nadále již s jednotlivými okny nebudeme vůbec pracovat, pro nové okno velikosti AxB budeme hledat v poli volné obdélníkové místo této velikosti tvořené samými 1.
Nyní bychom mohli uvažovat postupně všechny obdélníkové výřezy velikosti AxB a každý z nich zkoumat, zda je tvořen jedničkami. Tímto způsobem bychom sice dostali správné řešení úlohy, byl by to však velmi neefektivní postup. Obdélník velikosti AxB je možné umístit řádově až R.S způsoby a samostatné prozkoumání každé jeho polohy vyžaduje provést A.B testů, což může být řádově rovněž R.S. Celková časová složitost algoritmu by nám pak vyšla O(R2S2). Lepší je zařadit jako druhou fázi algoritmu pomocný předvýpočet, ve kterém určíme a zaznamenáme si délky souvislých sloupců jedniček v poli. Nulové prvky zůstanou nulové i nadále, každý jedničkový prvek však zvýšíme o počet jedniček, které leží v souvislé posloupnosti ve sloupci bezprostředně pod ním. Tato druhá fáze má časovou složitost O(RS). Provádí se totiž samostatně v každém z S sloupců a vystačíme vždy s jedním průchodem sloupcem zdola nahoru, kdy každou jedničku zvýšíme o číslo uložené v poli pod ní.
Následovat bude třetí fáze výpočtu, v níž již vyhledáme polohu nového okna v našem upraveném poli. Budeme ho procházet postupně po řádcích a hledat prvek s hodnotou alespoň B. Jen v takovém místě může totiž ležet levý horní roh jedničkového obdélníku velikosti AxB. Když takový prvek najdeme, pokračujeme v procházení téhož řádku směrem doprava a přitom kontrolujeme, zda alespoň A-1 dalších sousedních prvků má hodnotu nejméně B. Jestliže ano, našli jsem přípustnou polohu nového okna a výpočet ukončíme. Pokud ne, právě zkoumané místo v poli nepostačuje pro nové okno a pokračujeme v hledání dalších prvků s hodnotou alespoň B. Nejpozději po projití všemi prvky pole známe buď možnou polohu nového okna, nebo víme, že ho na obrazovku nelze umístit. Tato fáze výpočtu má časovou složitost O(RS) - jedná se o jeden průchod polem velikosti SxR.
Celé řešení je tvořeno inicializací pole a třemi po sobě jdoucími fázemi výpočtu. Celková časová složitost uvedeného algoritmu je tedy rovna maximu ze složitostí jednotlivých kroků, tj. O(NRS). Paměťová složitost je dána velikostí pole a je O(RS).
Druhý postup řešení nepotřebuje pole velikosti SxR, místo něj si uložíme přímo seznam všech oken a setřídíme ho vzestupně podle souřadnice levého okraje okna. Při použití dobrého třídicího algoritmu to můžeme provést v čase O(N log N). Uvažujme nyní nejprve vodorovný pás výšky B bodů podél horního okraje obrazovky. Budeme zkoumat, zda do něj lze umístit nové okno o rozměrech AxB. Projdeme uspořádaný seznam všech oken a vybereme z něj ta, která do uvažovaného pásu zasahují. Díky setřídění přitom můžeme zároveň snadno počítat, jak široké "mezery" mezi okny v pásu zůstanou volné a zda je některá z nich velká alespoň A bodů. K tomu stačí průběžně si evidovat v jedné pomocné proměnné, jak daleko doprava je v pásu již "obsazeno". Takovéto ošetření jednoho pásu provedeme v čase O(N). Pokud jsme při něm nenašli dostatečný prostor pro nové okno, musíme zkoumat další pásy. Mohli bychom se jednoduše posunout s vodorovným pásem výšky B o jeden bod níže a postupovat dál stejně. Takto bychom postupně prošli v nejhorším případě všech R-B+1 poloh uvažovaného pásu a vykonali přitom tedy celkem O(RN) operací. Lepší ale bude posunout pás rovnou o tolik bodů níže, až ho poprvé opustí některé z oken, která do něj právě zasahují. Jen tak se může v pásu vytvořit větší prostor pro nové okno. K tomu stačí evidovat si průběžně v jedné proměnné minimum ze souřadnic dolních okrajů těch oken, které do pásu momentálně zasahují. Každé z N oken opustí pás nejvýše jednou, takže bude rozhodně stačit zkoumat nejvýše N různých poloh pásu. Počet vykonaných operací se tím změní na O(N2).
Celková asymptotická časová složitost tohoto druhého algoritmu je dána složitostí vytvoření setříděného seznamu hran a složitostí vlastního výpočtu a vychází tedy O(N log N + N2)= O(N2). Paměťová složitost je určena nutností uložit si seznam oken a je rovna O(N). Jedná se tedy pravděpodobně o lepší řešení než bylo předchozí (a to i s využitím výše uvedeného zrychlujícího předvýpočtu), neboť reálně lze očekávat N2 < NRS (srovnání časových nároků) a N < RS (srovnání paměťových nároků obou algoritmů). Zvláště při větším počtu bodů na obrazovce (tzn. při vyšším rozlišení) časové i paměťové nároky prvního uvedeného řešení výrazně rostou, zatímco u druhého postupu se nemění a závisí jen na počtu oken. Teoreticky vzato však nejsou oba uvedené postupy řešení přímo srovnatelné z hlediska svých časových a paměťových nároků, neboť pro některé hodnoty parametrů může být první uvedené řešení lepší (při extrémně velkém počtu oken na obrazovce s malým rozlišením).
Předpokládejme, že počet vstupů je mocnina dvou. Pokud není, doplníme si další fiktivními vstupy o stálé hodnotě 0 (takové vstupy nám výsledek neovlivní) na nejbližší vyšší mocninu dvou. Při výpočtu minima postupujeme stejně, jen místo fiktivních vstupů s hodnotou 0 použijeme vstupy s hodnotou 9.
Nejprve problém vyřešíme pro 2 vstupy, a to zavedením hradla
MAX(a,b), jehož přechodovou funkcí bude maximum z hodnot vstupů
a, b. Setrojení tabulky hradla MAX je snadné. Máme-li již problém
vyřešen pro k vstupů a hledáme řešení pro 2k vstupů, rozdělíme
vstupy libovolným způsobem do dvou skupin po k vstupech,
nalezneme pro každou z nich maximum a poté (za pomoci hradla MAX)
určíme maximum z těchto dílčích maxim. Takto nalezený výsledek je
jistě maximem z daných 2k hodnot. Zapojení sítě tedy bude shodné
se sítí uvedenou v ukázkovém příkladu, pouze místo hradel XOR
použijeme hradla MAX:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | MAX | MAX | MAX | MAX | MAX | MAX | MAX | Výstup |
| OR | Y | |
| 0 | 1 | X | 0 | 0 | 1 |
| 1 | 1 | 1 |
| AND | Y | |
| 0 | 1 | X | 0 | 0 | 0 |
| 1 | 0 | 1 |
| ANDN | Y | |
| 0 | 1 | X | 0 | 0 | 0 |
| 1 | 1 | 0 |
Z těchto hradel pak sestrojíme "selektor" - jednoduchou síť se
třemi vstupy S, A0 a A1 a
jedním výstupem Q, která na Q přivede
AS (tedy A0,
pokud je S=0, nebo A1 při S=1). Budeme značit
Q=SEL(A0,A1,S).
B0 = ANDN(A0, S)
B1 = AND(A1, S)
Q = OR(B0, B1)
Nyní již můžeme přikročit ke konstrukci sítě pro danou úlohu,
zatím ovšem v trochu pozměněném tvaru: vstupů budeme mít n=2p
(označeny X0, X1, ..., Xn-1),
výstupů p+1, kde první výstup (S)
bude informovat o tom, zda jednička vůbec někde byla (hodnota 1)
či nikoliv (hodnota 0). Je-li S=1, potom ostatní výstupy Q0,
Q1,..., Qp-1 obsahují
nejmenší z čísel jedničkových vstupů,
je-li S=0, ostatní výstupy mohou mít libovolné hodnoty. Výsledné
číslo bude na výstupech umístěno tak, že Q0 obsahuje jeho
nejnižší řád a Qp-1 řád nejvyšší.
Pro 2 vstupy (p=1) lze tuto síť sestavit snadno:
S = OR(X0, X1)
Q0 = ANDN(X1, X0)
Máme-li již řešení pro n=2p vstupů, pro 2n vstupů lze řešení
rovněž sestrojit snadno: rozdělíme vstupy do dvou skupin: X0 až
Xn-1 a Xn až X2n-1,
přičemž pro každou z těchto skupin úlohu
vyřešíme. Výstupy částečných řešení označíme M a A0
až Ap-1 pro
první skupinu a N a B0 až Bp-1 pro druhou skupinu.
Pokud je M=1, je první jednička zaručeně v první skupině, tudíž Qp bude 0 a ostatní Qi budou rovna Ai. S musí být 1.
Pokud je M=0 a N=1, je první jednička v druhé skupině, takže Qp bude 1 a ostatní Qi budou rovna Bi. S musí být 1.
Pokud je M=0 a N=0, žádný ze vstupů jedničku neobsahuje, proto hodnoty Qi mohou být libovolné a S bude rovno 0.
Tyto požadavky lze snadno realizovat pomocí již definovaných
hradel a bloku SEL:
S = OR(M, N)
Qp = ANDN(N, M)
Qi = SEL(Ai, Bi, Qp)
pro 0<= i < p
Takto sestrojíme kombinační síť řešící upravenou úlohu pro
libovolný počet vstupů rovný mocnině dvou. Na tento problém nyní
zadání naší úlohy snadno převedeme: zadané vstupy doplníme (na
konec) jedním vstupem o fixní hodnotě 1 na mocninu dvou - tím
bude výstup S upravené úlohy vždy 1 a ostatní výstupy budou
udávat buďto pozici první jedničky na zadaných vstupech nebo
pozici nově přidané jedničky, která ovšem odpovídá samým
jedničkám na výstupech, čímž jsme požadavky zadání přesně
splnili.
Pro počet vstupů n=2k-1 má vytvořená kombinační síť hloubku 3k-2, tudíž její výpočet má časovou složitost O(log n).