НГр=89
Маршрут коммивояжера включает
в себя дуги:, (6, 3), (2, 5), (1, 4), (4, 1), (3, 2), (3, 6),
(5, 2).
Глава 3. Практическое
применение задачи коммивояжера
Задача коммивояжера имеет
ряд практических применений. Как следует
из самого названия задачи, ее можно использовать
для составления маршрута человека, который
должен посетить ряд пунктов и, в конце
концов, вернуться в исходный пункт. Например,
задача коммивояжера использовалась для
составления маршрутов лиц, занимающихся
выемкой монет из таксофонов. В этом случае
вершинами являются места установки таксофонов
и "базовый пункт". Стоимостью каждого
ребра (отрезка маршрута) является время
в пути между двумя точками (вершинами)
на маршруте.
Задача о производстве красок.
Имеется производственная линия для производства
n красок разного цвета; обозначим эти
краски номерами 1,2… n . Всю производственную
линию будем считать одним процессором..
Будем считать также, что единовременно
процессор производит только одну краску,
поэтому краски нужно производить в некотором
порядке. Поскольку производство циклическое,
то краски надо производить в циклическом
порядке (j1 ,j2 ,..,jn ,j1 ). После окончания
производства краски i и перед началом
производства краски j надо отмыть оборудование
от краски i . Для этого требуется время
C [i,j ]. Очевидно, что C [i,j ] зависит как от
i , так и от j , и что, вообще говоря,C [i,j ]
≠ C[j,i ]. При некотором выбранном порядке
придется на цикл производства красок
потратить время, где tk - чистое время
производства k -ой краски (не считая переналадок).
Однако вторая сумма в правой части постоянна,
поэтому полное время на цикл производства
минимизируется вместе с общим временем
на переналадку.
Таким образом, задачи коммивояжера
и задача о минимизации времени переналадки
– это просто одна задача, только варианты
ее описаны разными словами.
Задача о дыропробивном прессе.
Дыропробивной пресс производит большое
число одинаковых панелей – металлических
листов, в которых последовательно по
одному пробиваются отверстия разной
формы и величины. Схематически пресс
можно представить в виде стола, двигающегося
независимо по координатам x , y , и вращающегося
над столом диска, по периметру которого
расположены дыропробивные инструменты
разной формы и величины. Каждый инструмент
присутствует в одном экземпляре. Диск
может вращаться одинаково в двух направлениях
(координата вращения z ). Имеется собственно
пресс, который надавливает на подвешенный
под него инструмент тогда, когда под инструмент
подведена нужная точка листа. Операция
пробивки j-того отверстия характеризуется
четверкой чисел (xj ,yj ,zj ,tj ),, где xj ,yj
- координаты нужного положения стола,
zj - координата нужного положения диска
и tj -время пробивки j -того отверстия.
Производство панелей носит
циклический характер: в начале и конце
обработки каждого листа стол должен находиться
в положениях (x0 , y0 ) диск положении
z0 причем в этом положении отверстие
не пробивается. Это начальное состояние
системы можно считать пробивкой фиктивного
нулевого отверстия. С параметрами (x0 ,y0
,z0 ,0). Чтобы пробить j -тое отверстие
непосредственно после i -того необходимо
произвести следующие действия:
1. Переместить стол по
оси x из положения xi в положение
xj , затрачивая при этом время t(x)(|xi
-xj |)=ti ,j(x);
2. Проделать то же самое
по оси y , затратив время ti ,j(y);
3. Повернуть головку по
кратчайшей из двух дуг из
положения zi в положение zj , затратив
время ti ,j(z) ;
4. Пробить j -тое отверстие,
затратив время tj .
Конкретный вид функций t(x),
t(y), t(z) зависит от механических свойств
пресса и достаточно громоздок. Явно выписывать
эти функции нет необходимости. Действия
1-3 (переналадка с i -того отверстия j -тое)
происходит одновременно, и пробивка происходит
немедленно после завершения самого длительного
из этих действий. Поэтому С [i,j ] = max(t(x),
t(y), t(z)). Теперь, как и в предыдущем случае,
задача составления оптимальной программы
для дыропробивного пресса сводится к
задачи коммивояжера (здесь - симметричной).
Еще одним применением задачи
коммивояжера является задача обхода
доски шахматным конем: надо найти последовательность
ходов, которые позволят коню обойти все
поля шахматной доски, попадая на каждое
поле лишь один раз, и вернуться, в конце
концов, на исходное поле. В этом случае
роль вершин графа выполняют поля шахматной
доски. Предполагается также, что ребра
между двумя полями, которые являются
"составными частями" хода коня, имеют
нулевой вес; все остальные ребра имеют
вес, равный бесконечности. Оптимальный
маршрут имеет нулевой вес и должен быть
маршрутом коня. Читатель, возможно, удивится,
узнав, что поиск маршрутов коня с помощью
хороших эвристических алгоритмов для
задачи коммивояжера вообще не составляет
проблемы, в то время как поиск "вручную"
является весьма непростой задачей.
Заключение
Задача коммивояжера является
одной из знаменитых задач теории комбинаторики
и пользуется популярностью благодаря
тому, что к ней сводится большое количество
практических задач.
Среди современных практических
приложений задачи можно выделить: доставку
продуктов в магазин со склада, работу
почтальона по разноске корреспонденции,
мониторинг объектов (нефтяные вышки,
базовые станции сотовых операторов),
изготовление отверстий на специализированном
станке.
Для решения задачи коммивояжера
используют различные группы простейших
методов: полный и случайный перебор, жадный
и деревянный алгоритмы, метод имитации
отжига. Широкое применение получили различные
модификации более эффективных методов,
таких как метод ветвей и границ, генетических
алгоритмов, а также алгоритм муравьиных
колоний.
Изучение особенностей задачи
коммивояжера позволило сделать следующий
вывод: актуальным в настоящее время остается
поиск точных и приближенных способов
решения этой задачи как с теоретической,
так и с практической точек зрения. Более
того, темпы современной жизни меняют
отношение человека ко времени, сегодня
пользователь не любит ждать, изыскивает
возможности сократить время ожидания,
найти оптимальное решение в кратчайшие
сроки. Все это свидетельствует о росте
в будущем потребности в эффективном решении
задач коммивояжера и иных родственных
им оптимизационных задач, которые позволили
бы существенно сэкономить ограниченные
ресурсы организаций.
Список используемой
литературы:
1. О. Оре Графы и их применение.
Пер. с англ. под ред. И.М. Яглома. - М., «Мир»,
1995, 174 с.
2. В.П. Сигорский. Математический
аппарат инженера. - К., «Техніка», 1999, 768
с.
3. Ю.Н. Кузнецов, В.И. Кузубов,
А.Б. Волощенко. Математическое программирование:
учебное пособие. 2-е изд. перераб. и доп.
- М.; Высшая школа, 1987, 300 с.
4. Е.В. Маркова, А.Н. Лисенков.
Комбинаторные планы в задачах многофакторного
эксперимента. - М., Наука, 1990, 345 с.
5. Е.П. Липатов. Теория графов
и её применения. - М., Знание, 1996, 32
с.
6. В.М. Бондарев, В.И. Рублинецкий,
Е.Г. Качко. Основы программирования. -
Харьков, Фолио; Ростов на Дону, Феникс,
1998, 368 с.
7. Ф.А. Новиков Дискретная
математика для программистов. -
Санкт-Петербург, Питер, 2001, 304 с.