Перейти к содержанию
Форум интернет-конференций ВолНЦ РАН

Михаил Евгеньевич Первушин

Участники конференции
  • Публикаций

    2
  • Зарегистрирован

  • Посещение

Репутация

1 Neutral

Информация о Михаил Евгеньевич Первушин

  • Звание
    Newbie
  1. Муравьиный алгоритм - один из примеров реализации роевого интеллекта. Другой пример роевого интеллекта - алгоритм пчелиной колонии, моделирующий поведение пчел при сборе нектара. Алгоритм Беллмана-Хелда-Карпа - алгоритм динамического программирования для решения задачи коммивояжера. Был предложен в 1962 году независимо Беллманом и Хелдом и Карпом. Данный алгоритм позволяет найти точное решение задачи за время O(n^2*2^n). Это гораздо лучше, чем полный перебор, осуществляемый за время O(n!), но все еще очень медленно. Также алгоритм требует больших затрат по памяти. Данный и другие точные алгоритмы, например, формула включений-исключений за O(2^n) на практике не применяются, т.к. требуется быстро найти приемлемое решение.
  2. Здравствуйте, Дмитрий Александрович. Кроме муравьиных алгоритмов на практике часто используются следующие методы: метод ветвей и границ - метод, являющийся развитием метода полного перебора, в процессе выполняется вычисление и отсечение неэффективных подмножеств решений. генетический алгоритм - моделирует процесс естественного отбора в процессе эволюции. Поиск решения осуществляется путем подбора и комбинирования исходных параметров с помощью механизмов наследования, мутации и кроссинговера. Параллельные вычисления позволяют сократить время решения задачи. Они могут быть использованы при обычных стохастических прогонах, при использовании вероятностных методов (например метод имитации отжига), но точность получаемого решения ниже.
×