Практическое применение задачи коммивояжера

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

Задача о производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке. Поскольку производство циклическое, то краски надо производить в циклическом порядке (j₁,j₂,..,j_n,j₁). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C [ i,j ]. Очевидно, что C [ i,j ] зависит как от i, так и от j, и что, вообще говоря, C [ i,j ] ≠ C[ j,i ]. При некотором выбранном порядке придется на цикл производства красок потратить время, где t_k - чистое время производства k -ой краски (не считая переналадок). Однако вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.

Таким образом, задачи коммивояжера и задача о минимизации времени переналадки – это просто одна задача, только варианты ее описаны разными словами.

Задача о дыропробивном прессе. Дыропробивной пресс производит большое число одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины. Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент подведена нужная точка листа. Операция пробивки j-того отверстия характеризуется четверкой чисел (x_j,y_j,z_j,t_j),, где x_j,y_j - координаты нужного положения стола, z_j - координата нужного положения диска и t_j -время пробивки j -того отверстия.

Производство панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x₀, y₀) диск положении z₀ причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x₀,y₀,z₀,0). Чтобы пробить j -тое отверстие непосредственно после i -того необходимо произвести следующие действия:

1. Переместить стол по оси x из положения x_i в положение x_j, затрачивая при этом время t(x)(|x_i-x_j|)=t_i,j(x);

2. Проделать то же самое по оси y, затратив время t_i,j(y);

3. Повернуть головку по кратчайшей из двух дуг из положения z_i в положение z_j, затратив время t_i,j(z);

4. Пробить j -тое отверстие, затратив время t_j.

Конкретный вид функций t(x), t(y), t(z) зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости. Действия 1-3 (переналадка с i -того отверстия j -тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому С [ i,j ] = max(t(x), t(y), t(z)). Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к задачи коммивояжера (здесь - симметричной).

Еще одним применением задачи коммивояжера является задача обхода доски шахматным конем: надо найти последовательность ходов, которые позволят коню обойти все поля шахматной доски, попадая на каждое поле лишь один раз, и вернуться, в конце концов, на исходное поле. В этом случае роль вершин графа выполняют поля шахматной доски. Предполагается также, что ребра между двумя полями, которые являются "составными частями" хода коня, имеют нулевой вес; все остальные ребра имеют вес, равный бесконечности. Оптимальный маршрут имеет нулевой вес и должен быть маршрутом коня. Читатель, возможно, удивится, узнав, что поиск маршрутов коня с помощью хороших эвристических алгоритмов для задачи коммивояжера вообще не составляет проблемы, в то время как поиск "вручную" является весьма непростой задачей.

ЗАКЛЮЧЕНИЕ

Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики (расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал.

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

В основе метода ветвей и границ лежит следующая идея если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева).

Задача о коммивояжере имеет множество обобщений и методы её решения в различных проявлениях используются на практике.