Електрична амеба змогла вирішити завдання комівояжера

Дослідники з Університету Хоккайдо в Японії надихнулися поведінкою одноклітинних амеб і розробили аналоговий комп'ютер для пошуку надійного і швидкого вирішення завдання комівояжера - репрезентативного завдання комбінаторної оптимізації.

Вчені пояснили, що звичайні цифрові комп'ютери, в тому числі суперкомп'ютери, не можуть вирішити ці завдання в практично допустимий час, оскільки кількість можливих рішень, які їм необхідно оцінити, зростає в геометричній прогресії зі збільшенням розміру завдання.

Цю проблему можна уникнути, використовуючи «електронну амебу» - аналоговий комп'ютер, який натхненний одноклітинним амебоїдним організмом. Відомо, що амеба максимально ефективно засвоює поживні речовини, деформуючи своє тіло. Вона показала приблизне рішення проблеми - враховуючи карту певної кількості міст, завдання полягає в тому, щоб знайти найкоротший маршрут для відвідування кожного міста рівно один раз і повернення в стартове місто.

У водопровідній воді в США знайшли амебу, яка шкодить мозку людини

Ця знахідка надихнула професора Сейю Касая з Університету Хоккайдо на наслідування поведінки амеби в електронному вигляді з використанням аналогової схеми. Використовуючи перегородки, дослідники можуть легко змінити планування маршруту, оновивши значення опору без складної попередньої обробки.

Потім схема знайшла високоякісне рішення зі значно меншою довжиною маршруту, ніж середня довжина, отримана випадковою вибіркою. Крім того, час, необхідний для знаходження високоякісного рішення, збільшився незначно. Порівнюючи час пошуку з репрезентативним алгоритмом на основі ШІ, електронна амеба виявилася більш швидкою.