Parametrické vyhledávání - Parametric search

Při návrhu a analýze algoritmy pro kombinatorická optimalizace, parametrické vyhledávání je technika, kterou vynalezl Nimrod Megiddo (1983 ) pro transformaci a rozhodovací algoritmus (má tento optimalizační problém řešení s lepší kvalitou, než je určitá prahová hodnota?) do optimalizační algoritmus (najít nejlepší řešení). Často se používá k řešení optimalizačních problémů v systému Windows výpočetní geometrie.

Technika

Základní myšlenkou parametrického vyhledávání je simulace a testovací algoritmus který bere jako vstup číselný parametr ${ displaystyle X}$ , jako by to bylo spuštěno s (neznámou) optimální hodnotou řešení ${ displaystyle X ^ {*}}$ jako jeho vstup. Předpokládá se, že se tento testovací algoritmus chová diskontinuálně když ${ displaystyle X = X ^ {*}}$ , a pracovat s jeho parametrem ${ displaystyle X}$ pouze jednoduchým porovnáním ${ displaystyle X}$ s jinými vypočítanými hodnotami nebo testováním znamení nízkého stupně polynomiální funkce z ${ displaystyle X}$ . Pro simulaci algoritmu je třeba simulovat každé z těchto srovnání nebo testů, i když ${ displaystyle X}$ simulovaného algoritmu není znám. Pro simulaci každého srovnání použije parametrické vyhledávání druhý algoritmus, a rozhodovací algoritmus, který bere jako vstup další číselný parametr ${ displaystyle Y}$ , a to určuje, zda ${ displaystyle Y}$ je nad, pod nebo rovna hodnotě optimálního řešení ${ displaystyle X ^ {*}}$ .

Protože samotný rozhodovací algoritmus se nutně chová diskontinuálně ${ displaystyle X ^ {*}}$ , stejný algoritmus lze také použít jako testovací algoritmus. Mnoho aplikací však používá jiné testovací algoritmy (často srovnávací třídění algoritmy). Pokročilé verze parametrické techniky vyhledávání používají a paralelní algoritmus jako testovací algoritmus a seskupte srovnání, která musí být simulována do dávek, aby se významně snížil počet instancí rozhodovacího algoritmu.

Algoritmus sekvenčního testu

V nejzákladnější formě techniky parametrického vyhledávání jsou testovací algoritmus i rozhodovací algoritmy sekvenční (neparalelní) algoritmy, případně stejný algoritmus jako každý jiný. Technika krok za krokem simuluje testovací algoritmus, protože by běžel, když by mu byla jako parametr uvedena (neznámá) optimální hodnota řešení ${ displaystyle X}$ . Kdykoli simulace dosáhne kroku, ve kterém testovací algoritmus porovná svůj parametr ${ displaystyle X}$ na jiné číslo ${ displaystyle Y}$ , nemůže provést tento krok provedením číselného srovnání, protože neví co ${ displaystyle X}$ je. Místo toho volá rozhodovací algoritmus s parametrem ${ displaystyle Y}$ a používá výsledek rozhodovacího algoritmu k určení výstupu srovnání. Tímto způsobem čas pro simulaci skončí roven součinu časů pro testovací a rozhodovací algoritmy. Protože se předpokládá, že se testovací algoritmus chová diskontinuálně při optimální hodnotě řešení, nelze jej přesně simulovat, pokud jedna z hodnot parametrů ${ displaystyle Y}$ předaný rozhodovacímu algoritmu se ve skutečnosti rovná hodnotě optimálního řešení. Když k tomu dojde, může rozhodovací algoritmus detekovat rovnost a uložit optimální hodnotu řešení pro pozdější výstup.Pokud testovací algoritmus potřebuje znát znaménko polynomu v ${ displaystyle X}$ , to lze opět simulovat předáním kořeny polynomu k rozhodovacímu algoritmu za účelem zjištění, zda je neznámá hodnota řešení jedním z těchto kořenů, nebo pokud ne, mezi kterými dvěma kořeny leží.

Příklad považovaný za Megiddo (1983) a van Oostrum & Veltkamp (2002) týká se systému lichého počtu částic, všechny se pohybují doprava různými konstantní rychlostí podél stejné linie. Medián částic také bude mít pohyb doprava, ale takový, který je po částech lineární, spíše než s konstantní rychlostí, protože různé částice budou mediánem v různých časech. Zpočátku jsou částice a jejich medián nalevo od původ čáry a nakonec oni a jejich medián budou všichni napravo od původu. Problém je spočítat čas ${ displaystyle t_ {0}}$ ve kterém medián leží přesně na počátku lineární čas rozhodovací algoritmus lze snadno definovat: kdykoli ${ displaystyle t}$ , lze vypočítat polohu každé částice v čase ${ displaystyle t}$ a spočítat počet částic na každé straně původu. Pokud je vlevo více částic než vpravo, pak ${ displaystyle t$ , a pokud je více částic napravo než nalevo, pak ${ displaystyle t> t_ {0}}$ . Každý krok tohoto rozhodovacího algoritmu porovnává vstupní parametr ${ displaystyle t}$ do doby, kdy jedna z částic překročí původ.

Použití tohoto rozhodovacího algoritmu jako testovacího algoritmu i rozhodovacího algoritmu parametrického vyhledávání vede k algoritmu pro nalezení optimálního času ${ displaystyle t_ {0}}$ v kvadratickém celkovém čase. Simulovat rozhodovací algoritmus pro parametr ${ displaystyle t_ {0}}$ , musí simulace u každé částice určit, zda je její doba křížení před nebo po ${ displaystyle t_ {0}}$ , a tedy zda je to nalevo nebo napravo od počátku v čase ${ displaystyle t_ {0}}$ . Odpověď na tuto otázku pro jednu částici - porovnání doby křížení částice s neznámou optimální dobou křížení ${ displaystyle t_ {0}}$ - lze provést spuštěním stejného rozhodovacího algoritmu s časem křížení částice jako jeho parametru. Simulace tedy skončí spuštěním rozhodovacího algoritmu v každém z časů křížení částic, z nichž jeden musí být optimální čas křížení. rozhodovací algoritmus jednou trvá lineární čas, takže jeho spuštění samostatně v každém čase křížení trvá kvadratický čas.

Algoritmus paralelního testu

Tak jako Megiddo (1983) jak již bylo pozorováno, lze parametrickou vyhledávací techniku podstatně zrychlit nahrazením algoritmu simulovaného testu účinným paralelní algoritmus, například v paralelní stroj s náhodným přístupem (PRAM) model paralelního výpočtu, kde kolekce procesorů pracuje synchronně na a sdílená paměť, všichni provádějící stejnou posloupnost operací na různých adresách paměti. Pokud je testovacím algoritmem algoritmus PRAM, použije se ${ displaystyle P}$ procesory a vyžaduje čas ${ displaystyle T}$ (to znamená, ${ displaystyle T}$ kroky, ve kterých každý procesor provádí jednu operaci), pak lze každý z jeho kroků simulovat pomocí rozhodovacího algoritmu k určení výsledků nejvýše ${ displaystyle P}$ numerická srovnání. Nalezením střední nebo téměř střední hodnoty v sadě srovnání, které je třeba vyhodnotit, a předáním této jediné hodnoty rozhodovacímu algoritmu je možné eliminovat polovinu nebo téměř polovinu srovnání pouze s jediným voláním rozhodnutí algoritmus. Opakovaným snížením počtu porovnávání požadovaných simulací tímto způsobem na polovinu, dokud nezůstane žádné, je možné simulovat výsledky ${ displaystyle P}$ numerické srovnání pouze s použitím ${ displaystyle O ( log P)}$ volání rozhodovacího algoritmu. Celková doba pro parametrické vyhledávání se tedy v tomto případě stává ${ displaystyle O (PT)}$ (pro samotnou simulaci) plus čas pro ${ displaystyle O (T log P)}$ volání rozhodovacího algoritmu (pro ${ displaystyle T}$ dávky srovnání, odběr ${ displaystyle O ( log P)}$ volání na dávku). U problému, který lze vyřešit tímto způsobem, je produkt časového procesoru algoritmu PRAM často srovnatelný s časem pro algoritmus sekvenčního rozhodování a paralelní čas je polylogaritmický, což vede k celkovému času pro parametrické vyhledávání, který je pomalejší než rozhodovací algoritmus pouze pomocí polylogaritmického faktoru.

V případě příkladu problém s nalezením doby křížení mediánu ${ displaystyle n}$ pohybujících se částic, lze algoritmus sekvenčního testu nahradit paralelním třídění Algoritmus, který třídí polohy částic v době dané parametrem algoritmu, a poté používá seřazené pořadí k určení střední částice a nalezení znaménka její polohy. Nejlepší volba pro tento algoritmus (podle jeho teoretické analýzy, pokud není v praxi) je třídicí síť z Ajtai, Komlós, a Szemerédi (1983 ). To lze interpretovat jako algoritmus PRAM, ve kterém je číslo ${ displaystyle P}$ procesorů je úměrný vstupní délce ${ displaystyle n}$ a počet paralelních kroků je logaritmický. Simulace tohoto algoritmu tedy postupně vyžaduje čas ${ displaystyle O (n log n)}$ pro samotnou simulaci spolu s ${ displaystyle O ( log n)}$ dávky srovnání, z nichž každý může být zpracován ${ displaystyle O ( log n)}$ volání algoritmu rozhodování v lineárním čase. Dát tyto časové hranice dohromady dává ${ displaystyle O (n log ^ {2} n)}$ celkový čas pro parametrické vyhledávání. To není optimální čas pro tento problém - stejný problém lze vyřešit rychleji pozorováním, že doba křížení mediánu se rovná mediánu časů křížení částic - ale stejnou techniku lze použít i pro další složitější optimalizaci problémy a v mnoha případech poskytuje nejrychlejší známý silně polynomiální algoritmus pro tyto problémy.

Z důvodu velkých konstantních faktorů vznikajících při analýze třídicí sítě AKS není parametrické vyhledávání pomocí této sítě jako testovacího algoritmu praktické. Namísto, van Oostrum & Veltkamp (2002) navrhnout použití paralelní formy quicksort (algoritmus, který opakovaně rozděluje vstup do dvou podmnožin a poté každou podmnožinu rekurzivně třídí). V tomto algoritmu je krok oddílu masivně paralelní (každý vstupní prvek by měl být porovnán s vybraným otočným prvkem) a dvě rekurzivní volání lze provádět paralelně navzájem. Výsledný parametrický algoritmus je v souboru pomalejší nejhorší případ než algoritmus založený na třídicí síti AKS. Van Oostrum a Veltkamp však tvrdí, že pokud jsou uloženy výsledky předchozích rozhodovacích algoritmů (takže pouze srovnání nevyřešené těmito výsledky povedou k dalším voláním rozhodovacího algoritmu) a srovnávací hodnoty testované simulovaným testovacím algoritmem jsou dostatečně rovnoměrné distribuován, pak s postupujícím algoritmem bude počet nevyřešených srovnání generovaných v každém časovém kroku malý. Na základě této heuristické analýzy a experimentálních výsledků s implementací algoritmu tvrdí, že parametrický vyhledávací algoritmus založený na quicksortu bude praktičtější, než by naznačovala jeho nejhorší analýza.

Desynchronizované třídění

Cole (1987) dále optimalizovala techniku parametrického vyhledávání pro případy (například příklad), ve kterých je testovacím algoritmem srovnávací algoritmus třídění. Co se týče třídicí sítě AKS a některých dalších třídicích algoritmů, které lze použít místo ní, Cole poznamenává, že není nutné udržovat navzájem synchronizované simulované procesory: místo toho lze některým z nich umožnit postupovat dále třídicím algoritmem zatímco ostatní čekají, až budou stanoveny výsledky jejich srovnání. Na základě tohoto principu Cole upravuje simulaci třídicího algoritmu tak, aby udržoval soubor nevyřešených simulovaných srovnání, která nemusí všichni pocházet ze stejného paralelního časového kroku testovacího algoritmu. Stejně jako v synchronizované paralelní verzi parametrického vyhledávání je možné vyřešit polovinu těchto srovnání vyhledáním střední hodnoty porovnání a vyvoláním rozhodovacího algoritmu na této hodnotě. Poté namísto opakování tohoto postupu na polovinu, dokud se sbírka nevyřešených srovnání nevyprázdní, umožňuje Cole procesorům, které čekají na vyřešená srovnání, postupovat simulací, dokud nedosáhnou jiného srovnání, které musí být vyřešeno. Pomocí této metody Cole ukazuje, že parametrický vyhledávací algoritmus, ve kterém je testovací algoritmus třídění, lze dokončit pouze pomocí logaritmického počtu volání rozhodovacího algoritmu namísto ${ displaystyle O ( log ^ {2} n)}$ volání uskutečněná Megiddovou původní verzí parametrického vyhledávání. Místo použití třídicí sítě AKS je také možné kombinovat tuto techniku s paralelní Sloučit třídění algoritmus Cole (1988), což má za následek časové hranice s menšími konstantními faktory, které však stále nejsou dostatečně malé, aby byly praktické. Podobné zrychlení lze získat pro jakýkoli problém, který lze vypočítat v distribuované výpočetní síti s omezením stupeň (jako je třídicí síť AKS), buď Coleovou technikou nebo související technikou simulace více výpočetních cest (Fernández-Baca 2001 ).

Goodrich & Pszona (2013) kombinovat Coleovo teoretické zdokonalení s praktickým zrychlením van Oostrum & Veltkamp (2002). Místo použití paralelního rychlého řazení, jak to udělali van Oostrum a Veltkamp, používají boxsort, variantu rychlého řazení vyvinutou Reischuk (1985) ve kterém krok rozdělení rozdělí vstup náhodně ${ displaystyle O ({ sqrt {n}})}$ menší dílčí problémy místo pouze dvou dílčích problémů. Stejně jako v Coleově technice používají desynchronizované parametrické vyhledávání, při kterém je možné postupovat každému samostatnému vláknu provádění simulovaného paralelního třídicího algoritmu, dokud není potřeba určit výsledek jiného srovnání, a ve kterém je počet nevyřešených srovnání snížen na polovinu vyhledáním střední hodnoty porovnání a vyvoláním rozhodovacího algoritmu s touto hodnotou. Jak ukazují, výsledný randomizovaný parametrický vyhledávací algoritmus umožňuje s vysokou pravděpodobností pouze logaritmický počet volání rozhodovacího algoritmu, což odpovídá Coleově teoretické analýze. Rozšířená verze jejich příspěvku obsahuje experimentální výsledky implementace algoritmu, které ukazují, že celková doba běhu této metody na několika problémech s přirozenou geometrickou optimalizací je podobná jako u nejlepší synchronizované implementace parametrického vyhledávání (metoda rychlého třídění van Oostrum a Veltkamp): u některých problémů o něco rychlejší a u jiných o něco pomalejší. Počet volání do rozhodovacího algoritmu je však výrazně menší, takže tato metoda by získala větší výhody v aplikacích parametrického vyhledávání, kde je rozhodovací algoritmus pomalejší.

Na příkladu problému s nalezením střední doby křížení bodu získá Coleův algoritmus i Algoritmus Goodricha a Pszony dobu běhu ${ displaystyle O (n log n)}$ . V případě Goodricha a Pszony je algoritmus náhodný a získává tento čas vázaný s vysokou pravděpodobností.

Porovnání s binárním vyhledáváním

The metoda půlení (binární vyhledávání) lze také použít k transformaci rozhodnutí na optimalizaci. V této metodě se udržuje interval čísel, o nichž je známo, že obsahují optimální hodnotu řešení, a opakovaně zmenšuje interval voláním rozhodovacího algoritmu na jeho střední hodnotě a ponecháním pouze polovičního intervalu nad nebo pod mediánem, v závislosti na výsledku volání. Ačkoli tato metoda může najít pouze numerickou aproximaci na optimální hodnotu řešení, činí tak v řadě volání rozhodovacího algoritmu úměrných počtu bitů přesnosti přesnosti této aproximace, což má za následek slabě polynomiální algoritmy.

Místo toho, je-li to možné, najde parametrické vyhledávání silně polynomiální algoritmy, jejichž doba běhu je funkcí pouze vstupní velikosti a je nezávislá na numerické přesnosti. Parametrické vyhledávání však vede ke zvýšení časové složitosti (ve srovnání s rozhodovacím algoritmem), které může být větší než logaritmické. Protože jsou spíše než slabě polynomiální, jsou algoritmy založené na parametrickém hledání z teoretického hlediska uspokojivější. V praxi je binární vyhledávání rychlé a jeho implementace je často mnohem jednodušší algoritmické inženýrství je zapotřebí, aby bylo parametrické vyhledávání praktické. Nicméně, van Oostrum & Veltkamp (2002) napište, že „i když je jednoduchý přístup binárního vyhledávání často obhajován jako praktická náhrada parametrického vyhledávání, je v našem experimentálním srovnání, které provedli, překonán naším algoritmem [parametrické vyhledávání]“.

Aplikace

The Theil – Sen odhadce ve srovnání s jednoduchá lineární regrese

Parametrické vyhledávání bylo použito při vývoji efektivních algoritmů pro optimalizační problémy, zejména v výpočetní geometrie (Agarwal, Sharir a Toledo 1994 Zahrnují následující:

A centrální bod bodu stanoveného v a Euklidovský prostor je bod takový, že jakýkoli poloprostor obsahující středový bod také obsahuje konstantní zlomek vstupních bodů. Pro ${ displaystyle d}$ -dimenzionální prostory, optimální podíl, kterého lze dosáhnout, je vždy alespoň ${ displaystyle 1 / (d + 1)}$ . Algoritmy založené na parametrickém vyhledávání pro konstrukci dvojrozměrných středových bodů byly později vylepšeny na lineární čas pomocí jiných algoritmických technik. Toto vylepšení se však nevztahuje na vyšší dimenze. Ve třech rozměrech lze použít parametrické vyhledávání k nalezení středových bodů v čase ${ displaystyle O (n ^ {2} log ^ {4} n)}$ (Cole 1987 ).
Parametrické vyhledávání lze použít jako základ pro ${ displaystyle O (n log n)}$ časový algoritmus pro Theil – Sen odhadce, metoda v robustní statistiky pro přizpůsobení přímky k množině bodů, na které je mnohem méně citlivý odlehlé hodnoty než jednoduchá lineární regrese (Cole a kol. 1989 ).
v počítačová grafika, paprsková střelba problém (určení prvního objektu ve scéně, která je protínána danou přímkou nebo světelným paprskem) lze vyřešit kombinací parametrického hledání s datovou strukturou pro jednodušší problém, testováním, zda některá z dané sady překážek danou překážku zakrývá paprsek (Agarwal & Matoušek 1993 ).
The největší problém s holí zahrnuje nalezení nejdelší úsečky, která leží zcela v daném bodě polygon. Dá se to vyřešit včas ${ displaystyle O (n ^ {8/5 + epsilon})}$ , pro ${ displaystyle n}$ -stranné polygony a jakékoli ${ displaystyle epsilon> 0}$ pomocí algoritmu založeného na parametrickém vyhledávání (Agarwal, Sharir a Toledo 1994 ).
The prstenec který obsahuje danou množinu bodů a má nejmenší možnou šířku (rozdíl mezi vnitřním a vnějším poloměrem), lze použít jako měřítko kulatost množiny bodů. Tento problém lze opět vyřešit včas ${ displaystyle O (n ^ {8/5 + epsilon})}$ , pro ${ displaystyle n}$ -stranné polygony a jakékoli ${ displaystyle epsilon> 0}$ pomocí algoritmu založeného na parametrickém vyhledávání (Agarwal, Sharir a Toledo 1994 ).
The Hausdorffova vzdálenost mezi překládá dvou polygonů, jejichž překlad byl zvolen tak, aby se minimalizovala vzdálenost, lze najít pomocí parametrického vyhledávání v čase ${ displaystyle O ((mn) ^ {2} log ^ {3} mn)}$ , kde ${ displaystyle m}$ a ${ displaystyle n}$ jsou počty stran mnohoúhelníků (Agarwal, Sharir a Toledo 1994 ).
The Fréchetova vzdálenost mezi dvěma polygonální řetězce lze vypočítat pomocí parametrického vyhledávání v čase ${ displaystyle O (mn log mn)}$ , kde ${ displaystyle m}$ a ${ displaystyle n}$ jsou počty segmentů křivek (Alt & Godau 1995 ).
Pro ${ displaystyle n}$ body v euklidovské rovině, pohybující se konstantními rychlostmi, čas, ve kterém body získají nejmenší průměr (a průměr v té době) lze zjistit pomocí variace Coleovy techniky v čase ${ displaystyle O (n log ^ {2} n)}$ . Parametrické vyhledávání lze také použít pro další podobné problémy s hledáním času, kdy určitá míra sady pohyblivých bodů získá svou minimální hodnotu, pro míry včetně velikosti minimální obklopující koule nebo váha maximální kostra (Fernández-Baca 2001 ).

Reference

Agarwal, Pankaj K.; Matoušek, Jiří (1993), "Ray shooting and parametric search", SIAM Journal on Computing, 22 (4): 794–806, CiteSeerX 10.1.1.298.6047, doi:10.1137/0222051, PAN 1227762
Agarwal, Pankaj K.; Sharir, Micha; Toledo, Sivan (1994), „Aplikace parametrického vyhledávání v geometrické optimalizaci“, Journal of Algorithms, 17 (3): 292–318, doi:10.1006 / jagm.1994.1038, PAN 1300253, S2CID 380722.
Ajtai, M.; Komlós, J.; Szemerédi, E. (1983), „An $Ó (n log n)$ třídicí síť ", Sborník příspěvků z 15. sympozia ACM o teorii výpočtů (STOC '83), s. 1–9, doi:10.1145/800061.808726, ISBN 0-89791-099-0, S2CID 15311122.
Alt, Helmut; Godau, Michael (1995), "Výpočet Fréchetovy vzdálenosti mezi dvěma polygonálními křivkami" (PDF), International Journal of Computational Geometry & Applications, 5 (1–2): 75–91, doi:10.1142 / S0218195995000064, PAN 1331177.
Cole, Richard (1987), „Zpomalení třídicích sítí za účelem získání rychlejších třídicích algoritmů“, Deník ACM, 34 (1): 200–208, doi:10.1145/7531.7537, PAN 0882669, S2CID 2301419.
Cole, Richard (1988), „Parallel merge sort“, SIAM Journal on Computing, 17 (4): 770–785, doi:10.1137/0217049, PAN 0953293, S2CID 2416667.
Cole, Richard; Salowe, Jeffrey S .; Steiger, W. L .; Szemerédi, Endre (1989), „Algoritmus optimálního času pro výběr sklonu“, SIAM Journal on Computing, 18 (4): 792–810, doi:10.1137/0218055, PAN 1004799.
Fernández-Baca, D. (2001), „O nelineárním parametrickém vyhledávání“, Algorithmica, 30 (1): 1–11, doi:10.1007 / s00453-001-0001-2, PAN 1816864, S2CID 20320912.
Goodrich, Michael T.; Pszona, Paweł (2013), „Coleova parametrická vyhledávací technika se stala praktickou“ (PDF), Proc. 25. kanadská konference o výpočetní geometrii (CCCG 2013), arXiv:1306.3000, Bibcode:2013arXiv1306.3000G.
Megiddo, Nimrod (1983), „Aplikování paralelních výpočetních algoritmů při návrhu sériových algoritmů“, Deník ACM, 30 (4): 852–865, doi:10.1145/2157.322410, PAN 0819134, S2CID 2212007.
Reischuk, Rüdiger (1985), „Pravděpodobnostní paralelní algoritmy pro třídění a výběr“, SIAM Journal on Computing, 14 (2): 396–409, doi:10.1137/0214030, PAN 0784745.
van Oostrum, René; Veltkamp, Remco C. (2002), „Parametrické vyhledávání se stalo praktickým“, Sborník osmnáctého výročního sympozia o výpočetní geometrii (SoCG '02), New York, NY, USA: ACM, s. 1–9, doi:10.1145/513400.513401, hdl:1874/18869, ISBN 1-58113-504-1, S2CID 1551019.