Японскія інжынеры навучылі амёбу Physarum polycephalum рашаць праблему коміваяжора — класічную вылічальную задачу, якая дазваляе аптымізаваць маршрут паміж пунктамі на карце, наведваючы кожную з іх толькі адзін раз. Аднаклетачная жывёла рашыла праблему зусім новым спосабам, піша ScienceAlert.
Задача коміваяжора — адна з самых распаўсюджаных аптымізацыйных задач. Алгарытму неабходна знайсці аптымальны маршрут паміж гарадамі, які праходзіць праз кожны з іх як мінімум адзін раз, з вяртаннем у зыходны горад. Пры пастаноўцы задачы паказваюцца крытэрыі маршруту — самы кароткі, самы выгадны з пункту гледжання грошай, сукупны крытэр і іншыя. Складанасць задачы расце экспанентна: напрыклад, у спісе з чатырох гарадоў можна скласці тры магчымыя маршруты, з васьмі — ужо 2 520 маршрутаў.
Рашэннем задачы займалася амёба Physarum polycephalum — аднаклетачная, якая насяляе цяністыя і вільготныя месцы. Напрыклад, у гнілым лісці і дрэвах.
Даследнікі з Універсітэта Кеё ў Японіі паставілі задачу амёбе ў найпрасцейшым выглядзе, і ёй удалося справіцца. Тады навукоўцы ўскладнілі задачу і выявілі, што пры экспанентным росце складанасці час на рашэнне ў амёбы павялічваецца лінейна.
Такім чынам амёба рашыла задачу эфектыўней за камп'ютар.
Каментары