Ученые из Японии представили систему, которая может быстро решать проблему коммивояжера — эффективного перемещения между разными точками. Исследователи вдохновились поведением амебы.
Исследователи из Университета Хоккайдо в Японии вдохновились поведением одноклеточных амеб и разработали аналоговый компьютер для поиска надежного и быстрого решения задачи коммивояжера — репрезентативной задачи комбинаторной оптимизации.
Ученые объяснили, что обычные цифровые компьютеры, в том числе суперкомпьютеры, не могут решить эти задачи в практически допустимое время, так как количество возможных решений, которые им необходимо оценить, возрастает в геометрической прогрессии с увеличением размера задачи.
Эту проблему можно избежать, используя «электронную амебу» — аналоговый компьютер, который вдохновлен одноклеточным амебоидным организмом. Известно, что амеба максимально эффективно усваивает питательные вещества, деформируя свое тело. Она показала примерное решение проблемы — учитывая карту определенного количества городов, задача состоит в том, чтобы найти кратчайший маршрут для посещения каждого города ровно один раз и возвращения в стартовый город.
Эта находка вдохновила профессора Сейю Касая из Университета Хоккайдо на подражание поведению амебы в электронном виде с использованием аналоговой схемы. Используя перегородки, исследователи могут легко изменить планировку маршрута, обновив значения сопротивления без сложной предварительной обработки.
Затем схема нашла высококачественное решение со значительно меньшей длиной маршрута, чем средняя длина, полученная случайной выборкой. Кроме того, время, необходимое для нахождения высококачественного решения, увеличилось незначительно. Сравнивая время поиска с репрезентативным алгоритмом на основе ИИ, электронная амеба оказалась более быстрой.
Читать также
Ледник «Судного дня» оказался опаснее, чем думали ученые. Рассказываем главное
Ученые нашли быстрый путь по Солнечной системе
Найдено предполагаемое царство исчезнувших хеттов. Что обнаружили археологи?