Trzmiel lepszy od superkomputera

13-11-2010 16:29

problem komiwojażera · marszrutyzacja · najkrótsza trasa · trzmiel · Queen Mary University of London · Lars Chittka · Mathieu Lihoreau

Wśród szczególnie trudnych i złożonych problemów obliczeniowych słynny jest tak zwany „problem komiwojażera", czy szerzej: problem marszrutyzacji, czyli takiego wyznaczenia trasy, żeby jak najefektywniej obejść wszystkie kluczowe punkty. Nazwa wzięła się od anegdotycznego sprzedawcy, który potrzebuje objechać wiele miast, a chciałby zrobić to jak najkrótszą trasą.

Złożoność takiego planowania rośnie tak prędko, że szybko przekracza nie tylko możliwości człowieka, ale także największych superkomputerów, które nawet nad średnio złożonymi trasami pracować muszą wiele dni. Znajdowanie rozwiązać w czasie rzeczywistym wydaje się wręcz niemożliwe. Ale nie dla... trzmieli.

Naukowcy z Queen Mary's School of Biological and Chemical Sciences (Queen Mary University of London) ze zdumieniem odkryli, że problem zatykający największe istniejące komputery nie jest w ogóle problemem dla pospolitych trzmieli, które rozwiązują go machinalnie, oblatując dostępne źródła pożywienia jak najkrótszą trasą.

W eksperymencie, jaki przeprowadzili profesor Lars Chittka i doktor Mathieu Lihoreau wykorzystano sztuczne, komputerowo kontrolowane kwiaty zawierające nektar, oraz trzmiele, których lot śledzono i analizowano. Uczeni ciekawi byli, czy przy kolejnych „rundach" owady oblatywać będą kwiaty w takiej kolejności, w jakiej znajdowały je pierwszy raz, czy też w inny sposób. Okazało się, że już przy drugim oblocie trzmiele korzystały z najkrótszej możliwej trasy.

W jaki sposób te owady radzą sobie ze złożonością problemu? Ich wyczyn zdumiewa jeszcze bardziej, gdy uświadomimy sobie, że ich mózg ma wielkość główki szpilki, a wykonuje natychmiast obliczenia, które są upiorne dla największych superkomputerów i twardym orzechem dla najlepszych matematyków.

Naukowcy teraz zastanawiają się, jak sprawdzić algorytm, jakim posługują się trzmiele i jakie struktury w ich mózgu pozwalają na takie operacje. Odtworzenie ich działania mogłoby stanowić rewolucję w informatyce. Pokazuje to także, że z pokorą należy oceniać te malutkie móżdżki.

Autor: Artur Jurgawka

Źródło: Queen Mary University of London