Foto: kentoh / Dollar Photo Club

Na optimalizace paralelně

Nový algoritmus má slibovat až exponenciální zrychlení pro řešení určitých optimalizačních problémů, a to včetně známého problému obchodního cestujícího.

Vědci z Harvard John A. Paulson School of Engineering and Applied Sciences popisují svůj nový algoritmus následujícím způsobem. Tradičně algoritmy tohoto typu, které se de facto objevily už v 70. letech, vycházejí ze sekvenčního zpracování dat, což znamená velkou výpočetní náročnost v závislosti na rostoucím vstupu. Nový přístup (dle jeho autorů algoritmus Singer-Balkanski) má namísto toho fungovat paralelně. V každém kroku je vybrána velká množina nehodících se „cest“ a ta pak zahozena a dále už nezkoumána. Tím se výrazně zmenšuje prohledávaný stavový prostor.
Postup je ilustrován na algoritmu, která má doporučovat filmy podobné filmu X. Sekvenční algoritmus by prostě skákal film po filmu a na základě předdefinovaných atributů přidával ty vhodné (respektive prohledané filmy nějak řadil). Nový algoritmus při vyřazení filmu najde vždy ty jemu podobné (hledá je v souboru rozděleném na části – to je zřejmě ten paralelismus?) a dále pak zkoumá/seřadí/vybere až to, co zbude. Autoři uvádějí, že na souboru milionu hodnocení 6 000 uživatelů 4 000 filmů jejich algoritmus dosahuje cca 20násobného zrychlení proti klasickému sekvenčnímu zpracování. S množstvím dat zrychlení roste.
Jako další možné oblasti využití nového přístupu se uvádí výpočetní biologie/návrhy léků, počítačové vidění, analýzy sítí nebo fungování aukcí. Práce má mít také vztah ke strojovému učení, když nový algoritmus dokáže rychle odhadnout, jak je použitý model strojového učení přesný (?).
Zdroj: Eurekalert.org
Jde o tiskovou zprávu na základě příspěvku na ACM Symposium on Theory of Computing
arXiv (technický článek)
https://arxiv.org/pdf/1804.06355.pdf

Poznámky:
Je to tak, že nehledáme nejlepší řešení, ale rychle dosažitelné, dostatečně uspokojivé řešení? Tak jako v optimalizaci tohoto typu funguje třeba i (kvantové) žíhání?
Jak konkrétně toto může fungovat třeba při řešení problému obchodního cestujícího? Co vlastně z množiny možností se bude zahazovat? (Všechny cesty obsahující např. cestu B-C?)
Ono deklarované paralelní zpracování funguje tak, jak naznačeno výše? To nevypadá nijak revolučně…

O kostkách ledu ve sklenici: Trochu překvapivý pohled na entropii

Neměli bychom druhou větu termodynamiky chápat spíše tak, že entropie roste směrem do budoucnosti, ale …

Používáme soubory cookies pro přizpůsobení obsahu webu a sledování návštěvnosti. Data o používání webu sdílíme s našimi partnery pro cílení reklamy a analýzu návštěvnosti. Více informací

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close