Лекция, 24 февраля 2013, 15:30

Алгоритмы для задачи коммивояжера

бесплатно
Описание встречи

Задача коммивояжера — классическая NP-трудная задача с достаточно простой формулировкой: даны города и попарные расстояния между ними, необходимо найти кратчайший маршрут, проходящий по всем городам ровно по одному разу. Практические применения данной задачи включают в себя разработку микросхем, планирование, сборку генома. Трудность задачи объясняется тем, что с ростом количества городов количество потенциальных маршрутов растет очень быстро. Например, даже для пятнадцати городов количество таких маршрутов равно 43 589 145 600. Если считать, что компьютер может перебрать миллиард маршрутов в секунду, то искать решение для задачи с сотней городов ему придется больше триллиона лет.

В то же время в задачах, возникающих на практике, количество городов обычно составляет десятки тысяч. К счастью, есть методы, позволяющие решать такие примеры на практике. Например, в 2004 году был найден оптимальный цикл по 24 978 городам Швеции, а в 2006 был вычислен оптимальный маршрут лазера при построении интегральной схемы через 85 900 точек.

В докладе будут рассмотрены методы практического и теоретического решения задачи коммивояжера: метод ветвей и границ, локальный поиск, метод имитации отжига, динамическое программирование, перебор с возвратом, приближенные алгоритмы, формула включений-исключений, матрицы Татта и проверка равенства нулю многочлена.

Преподаватели
Посетили
Показать Всех
Смотрите также