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

Вопросы

Здравствуйте, Михаил Евгеньевич. Если можно, то 2 кратеньких ответа на 2 моих вопроса:

  1. Какие ещё есть аналоги "муравьиного алгоритма" и в чём их суть / особенность (кратко, пожалуйста)?;
  2. В чём суть обозначенных в работе параллельных вычислений (я в этом не специалист, но очень интересно :))? Почему они точно также не могут быть использованы при обычных стохастических прогонах по поиску наилучшего решения, в завершении которых мы просто выберем лучший вариант (тоже кратенько; буквально пару предложений)?

Спасибо.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

4 ответа на этот вопрос

Recommended Posts

  • 0

Здравствуйте, Дмитрий Александрович. Кроме муравьиных алгоритмов на практике часто используются следующие методы: 

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

Параллельные вычисления позволяют сократить время решения задачи. Они могут быть использованы при обычных стохастических прогонах, при использовании вероятностных методов (например метод имитации отжига), но точность получаемого решения ниже.

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
  • 0

Спасибо. О подобных вещах слышал. Думал, может какая экзотика мимо меня проскочила.

Если не против, то пообщался бы с Вами еще в подобном ключе.

  1. Слышал о понятии "роевого интеллекта". Как понимаю, "муравьиный алгоритм" одна из его вариаций? А есть ли еще какие-то зарекомендовавшие себя варианты подобных методов?
  2. По задаче коммивояжера. Если память не изменяет, то ее решением, а возможно и постановкой занимался некий Беллман. И вроде как он нашел точное решение, развив вокруг этого идеи "динамического программирования". Не проясните тезисно верны ли мои знания? И если верны, то использование альтернативных итерационных методов для ее решения сопряжено только с вычислительными возможностями современных машин или есть еще камни преткновения?

Спасибо.

Поделиться сообщением


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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
  • 0

Мой интеллектуальный аппетит всё сильнее и сильнее разыгрывается, но ... надо и честь знать. Спасибо за ответы. Если есть интерес, то продолжил бы с Вами общение вне рамок мероприятия. Моя почта: alferev_1991@mail.ru. Успехов Вам в ваших стремлениях. Ещё раз спасибо.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Пожалуйста, войдите, чтобы комментировать

Вы сможете оставить комментарий после входа в



Войти

×