antony_w (antony_w) wrote,
antony_w
antony_w

Category:

Электрическая амеба смогла решить задачу коммивояжера



Ученые из Японии представили систему, которая может быстро решать проблему коммивояжера — эффективного перемещения между разными точками. Исследователи вдохновились поведением амебы.

Исследователи из Университета Хоккайдо в Японии вдохновились поведением одноклеточных амеб и разработали аналоговый компьютер для поиска надежного и быстрого решения задачи коммивояжера — репрезентативной задачи комбинаторной оптимизации.

Ученые объяснили, что обычные цифровые компьютеры, в том числе суперкомпьютеры, не могут решить эти задачи в практически допустимое время, так как количество возможных решений, которые им необходимо оценить, возрастает в геометрической прогрессии с увеличением размера задачи.

Эту проблему можно избежать, используя «электронную амебу» — аналоговый компьютер, который вдохновлен одноклеточным амебоидным организмом. Известно, что амеба максимально эффективно усваивает питательные вещества, деформируя свое тело. Она показала примерное решение проблемы — учитывая карту определенного количества городов, задача состоит в том, чтобы найти кратчайший маршрут для посещения каждого города ровно один раз и возвращения в стартовый город.

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

Затем схема нашла высококачественное решение со значительно меньшей длиной маршрута, чем средняя длина, полученная случайной выборкой. Кроме того, время, необходимое для нахождения высококачественного решения, увеличилось незначительно. Сравнивая время поиска с репрезентативным алгоритмом на основе ИИ, электронная амеба оказалась более быстрой.

Tags: исследования
Subscribe

Posts from This Journal “исследования” Tag

promo antony_w august 17, 2014 11:48 18
Buy for 10 tokens
Есть блог, в котором написано много постов про роботов: ссылка И там есть несколько статей о замене рабочих мест человека роботами: Уже к 2018 году роботы отберут у человека часть профессий Рабский труд без зарплаты Армия роботов: зачем она нужна обильной людьми Поднебесной и кому может…
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment