Одна маленька амеба знайшла рішення задачі комівояжера швидше кращих алгоритмів. Що вона знає такого, що не знаємо ми?
Група дослідників з токійського університету Кейо вирішила використовувати амебу для розв’язання задачі комівояжера, відомої проблеми в галузі комп’ютерних наук. Завдання виглядає так: уявіть, що ви – комівояжер, літаючий з міста в місто і продаєте свої товари. Ви прагнете максимально підвищити свою ефективність, щоб заробити якомога більше грошей, тому хочете знайти найкоротший шлях, який дозволить вам дістатися до кожного міста на маршруті.
Немає простої математичної формули, щоб знайти найбільш ефективний маршрут для нашого продавця. Замість цього, єдиний спосіб вирішити проблему – це розрахувати довжину кожного маршруту і подивитися, який з них найбільш короткий.Що ще гірше, виконання цього обчислення стає експоненціально складніше зі збільшенням кількості міст на маршруті. З 4 містами є тільки 3 різних маршрутів для розгляду. Але з 6 містами з’являється 360 різних маршрутів, які необхідно розрахувати. Якщо у вас є маршрут з 10 або більше містами, кількість можливих маршрутів обчислюється мільйонами.
Це робить задачу комівояжера однією з широкого класу проблем, які комп’ютерні вчені називають «класом складності NP». Це проблеми, які експоненціально ускладнюються дуже швидко, що також включає проблеми, пов’язані зі зломом зашифрованих систем і майнингом криптовалют. З цілком зрозумілих причин багато людей зацікавлені в пошуку шляхів вирішення цих проблем як можна швидше.Рішення Університету Кейо відрізняється від типових алгоритмічних рішень, розроблених іншими дослідниками, тому що вчені використовували амебу Physarum polycephalum. Physarum polycephalum – це слиз, дуже простий організм, який робить дві речі: рухається до їжі і йде від світла. Мільйони років еволюції зробили Physarum аномально ефективним у цих завданнях.
Дослідники використовували цю ефективність для створення пристрою для розв’язання задачі комівояжера. Вони помістили амебу в спеціальну камеру, заповнену каналами, і в кінці кожного каналу помістили трохи їжі. Інстинктивно амеба простягає вусики в канали, щоб спробувати отримати їжу. Однак, коли це відбувається, вона вимикає світло в інших каналах.
В даному випадку кожен канал представляє місто на маршруті нашого гіпотетичного продавця разом з порядком відвідування цього міста. Коли амеба поширюється в канал, який представляє місто, це впливає на ймовірність того, що світло згасне в каналах, що представляють такі міста на маршруті. Чим далі знаходиться це місто, тим частіше світло гасне в цьому каналі. Це може здатися обхідним способом обчислення рішення задачі комівояжера, але перевага полягає в тому, що амебі не потрібно розраховувати кожен окремий шлях, як це роблять більшість комп’ютерних алгоритмів. Замість цього амеба просто пасивно реагує на умови, і сама знаходить найкраще можливе рішення. Це означає, що додавання нових міст для амеби не збільшує час, необхідний для вирішення проблеми.
Таким чином, амеба може вирішити NP-складну задачу швидше, ніж будь-який з наших комп’ютерних алгоритмів. Як це сталося? Вчені з університету Кейо точно не впевнені.
Але якщо дослідники зможуть зрозуміти, як працює амеба, вони зможуть використовувати цей прийом не тільки для допомоги комівояжерам. Це може прискорити нашу здатність вирішувати всілякі складні обчислювальні задачі та змінити підхід до безпеки.Ця маленька амеба може назавжди змінити вигляд комп’ютерів.