Sciencemag.cz
Doporučujeme
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)
Click to access 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ě…
