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

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

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

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

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