|  | 30 марта 2013 | Информационные технологии

Программируемая липкая субстанция самостоятельно решает сложные математические задачи

Решение задачи


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

Двое исследователей из университета Западной Англии (University of the West of England) подошли к решению задачи странствующего коммивояжера достаточно нетрадиционным образом. Они создали математическую модель некоей гипотетической липкой субстанции, которая при сокращении сама находит самые короткие маршруты между двумя пунктами.

Эндрю Адаматцки (Andrew Adamatzky) и Джефф Джонс (Jeff Jones) почерпнули идею решения задачи у живой природы, в которой существуют колонии одноклеточных организмов, называемые слизевиками. В естественных условиях эти колонии в поисках пищи все время занимаются решением математических задач, таких как поиски выхода из лабиринта и других подобных задач. Созданная исследователями математическая модель почти точно копирует поведение слизевиков, которые координируют свои движения с помощью химических сигналов. И как колония микроорганизмов, математическая модель и не подозревает, что своими действиями она решает сложнейшую математическую задачу.

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

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











Ключевые слова:
Липкая, Субстанция, Математическая, Модель, Решение, Задача, Странствующий, Коммивояжер, Суперкомпьютер

Первоисточник

Другие новости по теме:
  • Математическая модель популяции муравьев позволила найти решения древнейшей ...
  • Волшебная электрическая "шапка" может сделать Вас более умным и более тво ...
  • Программа SimPortland компании IBM - математическая симуляция реального гор ...
  • Процессор на основе мемристоров находит путь через лабиринт, используя мощь ...
  • Бактерии научили решать сложные задачи.




  • 30 марта 2013 05:32
    #1 Написал: FomaNeverujuwij

    Публикаций: 0
    Комментариев: 3857
    Интересно. Все это подтверждает еще раз, что у природы есть свои более простые методы решения задач, которые ставят на колени любую вычислительную технику.


    --------------------
        
    30 марта 2013 08:30
    #2 Написал: volod

    Публикаций: 0
    Комментариев: 1489
    FomaNeverujuwij, но никто ведь не мешал придумать этот алгоритм не подсматривая у природы, это уже дело консерватизма и привычки тупо оцифровать и поставить на мощный компьютер.
        

    Информация

    Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.