Hlenky řeší Problém obchodního cestujícího neobyčejným způsobem  
Hlenky vápenky jsou jednobuněčné améby. Když se jich sleze hodně na jedno místo, tak připomínají plivance. Tyhle plivancoidní tvorové mají ale unikátní výpočetní schopnosti, které by mohly inspirovat tvůrce algoritmů pro řešení úmorných výpočetních problémů.
Výpočty hlenek. Kredit: Zhu et al. (2018), Royal Society Open Science.
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.
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.
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.

Datum: 27.12.2018
Tisk článku

Kvantový moment - Crease Robert P., Goldhaber Alfred Scharff
 
 
cena původní: 350 Kč
cena: 294 Kč
Kvantový moment
Crease Robert P., Goldhaber Alfred Scharff
Související články:

Hlenky si pamatují     Autor: Jaroslav Petr (06.02.2008)
Hlenky a jejich důmyslná strategie přežití     Autor: Dagmar Gregorová (12.07.2010)
Hlenky sahají po rostlinných sedativech     Autor: Dagmar Gregorová (17.06.2011)
V rychlostním souboji tváří v tvář zvítězil kvantový počítač     Autor: Stanislav Mihulka (10.05.2013)



Diskuze:




Pro přispívání do diskuze musíte být přihlášeni




Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace