Výpočty hlenek. Kredit: Zhu et al. (2018), Royal Society Open Science.

Představte si, že existuje daný počet měst. A mezi nimi jsou silnice o daných délkách. Vaším úkolem je najít nejkratší možnou trasu, vycházející z jednoho z měst, procházející všemi městy a vracející se nazpět do výchozího města. To je Problém obchodního cestujícího (TSP, podle anglického Travelling Salesman Problem) v kostce.

Zní to docela jednoduše. Ve skutečnosti je to ale obtížný optimalizační problém, který patří mezi takzvané NP-těžké úlohy. Pro malý počet měst je to velice snadné, prostě prozkoumáte všechny možnosti a najdete nejkratší cestu. S rostoucím počtem měst ale velice rychle vzrůstá počet možných řešení a záhy dojdou výpočetní síly i dnešním superpočítačům. Pro představu, pro čtyři města existují tři možné cesty. Pro osm měst už ale počet možných cest vzroste na 2520.

Masashi Aono. Kredit: ELSI.

Jak říká Wikipedie, u takových úloh není obecně známo jak pro každý vstup nalézt přesné řešení v rozumném čase, ani to, zda vůbec může existovat algoritmus, který takové řešení najde v čase úměrném nějaké mocnině počtu uzlů. Takové úlohy se v praxi řeší pouze přibližně, heuristickými algoritmy, které rezignují na optimální řešení.

Vápenka mnohohlavá. Kredit: Eigenes Werk / Wikimedia Commons.

Masashi Aono z japonské Keio University v Tokiu a jeho tým pojali šílený nápad, že nechají Problém obchodního cestujícího počítat hlenky. Ve skutečnosti k tomu samozřejmě měli dobré důvody a navazovali na dřívější výzkum, ale z pohledu nadšeného laika je to pozoruhodná šílenost. K výzkumu si najali hlenky vápenky mnohohlavé (Physarum polycephalum), tedy mikroskopické eukaryotní organismy s komplikovaným životním cyklem, které tráví život v podobě améb, plazmódií, cyst i bičíkovců. Ve vlhkých koutech lesů bývají viditelné pouhým okem a připomínají oranžové plivance.

Aby Aono a spol. mohli zapojit do výzkumu hlenky, tak samozřejmě museli postavit důmyslně uspořádaný experiment. Vápenky se účastnily experimentu v podobě plazmódia o hmotnosti cca 12 mg, které si pochutnávalo na ovesných vločkách a sedělo ve speciálním čipu. Díky tomuto experimentu vědci zjistili, že hlenky najdou rozumný, tedy optimálnímu řešení blízký výsledek Problému obchodního cestujícího velmi rychle. Když vzroste počet měst v TSP problému ze čtyř na osm, tak čas, který hlenky potřebují k řešení, vzroste jen lineárně.

Je pravda, že konvenční počítače při tomhle počtu měst také naleznou heuristická řešení v lineárním času. Hlenky to ale dělají úplně jinak, než tradiční lidské algoritmy. Počítače řeší Problém obchodního cestujícího mnohem rychleji než améby, zvláště pro malý počet měst. Postup, který používají hlenky, je ale pozoruhodný, a mohl by se stát základem pro nové algoritmy a výpočetní postupy, s nimiž bude možné hledat přibližná řešení výpočetně náročných problémů v lineárním, čili rozumném čase.

Video:  Physarum: Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism


Video:  Traveling Salesman Problem - Visualized Algorithms


Literatura
Phys.org 20. 12. 2018, Royal Society Open Science online 19. 12. 2018.