Задача коммивояжера
имое таблицы меняется по мере выполнения общего шага. Это
видно из следующей таблицы:
Одним из возможных недостатков такого алгоритма является необходимость
знать не матрицу расстояний, а координаты каждого города на плоскости. Если
нам известна матрица расстояний между городами, но неизвестны их
координаты, то для их нахождения нужно будет решить n систем квадратных
уравнений с n неизвестными для каждой координаты. Уже для 6 городов это
сделать очень сложно. Если же, наоборот, имеются координаты всех городов,
но нет матрицы расстояний между ними, то создать эту матрицу несложно. Это
можно легко сделать в уме для 5-6 городов. Для большего количества городов
можно воспользоваться возможностями компьютера, в то время как
промоделировать решение системы квадратных уравнений на компьютере довольно
сложно.
На основе вышеизложенного можно сделать вывод, что мой алгоритм,
наряду с деревянным алгоритмом и алгоритмом Дейкстры, можно отнести к
приближённым (хотя за этим алгоритмом ни разу не было замечено выдачи
неправильного варианта).
1.2.6. Анализ методов решения задачи коммивояжера
Для подведения итогов в изучении методов решения ЗК протестируем
наиболее оптимальные алгоритмы на компьютере по следующим показателям:
количество городов, время обработки, вероятность неправильного ответа.
Данные занесём в таблицу.
|Алгоритм лексического перебора |
|Кол-во |Время обработки,|Вероятность неправильного |Тип |
|городов |c |ответа, % |алгоритма |
|10 |41 |0 |точный |
|12 |12000=3ч.20мин |0 | |
|32 |-* |0 | |
|100 |-* |0 | |
|Метод ветвей и границ |
|10 |~0 |0 |точный |
|32 |~0.0001 |0 | |
|100 |1.2 |0 | |
|Мой алгоритм решения ЗК |
|10 |0.001 |0 |приближенный|
|32 |2.5 |0 | |
|100 |6 |0 | |
*- ЗК с таким количеством городов методом лексического перебора
современный компьютер не смог бы решить даже за всё время существования
Вселенной.
Как видим по результатам этой таблицы, алгоритм лексического перебора
можно применять лишь в случае с количеством городов 5..12. Метод ветвей и
границ, наряду с моим методом, можно применять всегда. Хотя мой метод я
отнёс к приближённым алгоритмам, он фактически является точным, так как
доказать обратное ещё не удалось.
1.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]. При некотором выбранном порядке
придется на цикл производства красок потратить время
[pic]
Где 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. Изучены эвристический, приближенный и точный алгоритмы решения ЗК.
Точные алгоритмы решения ЗК – это полный перебор или
усовершенствованный перебор. Оба они, особенно первый, не эффективны
при большом числе вершин графа.
2. Предложен собственный эффективный метод решения ЗК на основе
построения выпуклого многоугольника и включения в него центральных
вершин (городов).
3. Проведён анализ наиболее рациональных методов решения ЗК и определены
области их эффективного действия: для малого числа вершин можно
использовать точный метод лексического перебора; для большого числа
вершин рациональнее применять метод ветвей и границ или метод автора
работы (Анищенко Сергея Александровича).
4. Изучены практические применения ЗК и задачи с переналадками, сводимые
к ЗК.
5. Приведены тексты программ, позволяющие решить ЗК различными методами.
Литература
1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. -
М., «Мир», 1965, 174 с.
2. В. П. Сигорский. Математический аппарат инженера. - К., «Техніка»,
1975, 768 с.
3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое
программирование: учебное пособие. 2-е изд. перераб. и доп. - М.;
Высшая школа, 1980, 300 с., ил.
4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах
многофакторного эксперимента. – М., Наука, 1979, 345 с.
5. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32
с.
6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы
программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368
с.
7. Ф. А. Новиков Дискретная математика для программистов. - Санкт-
Петербург, Питер, 2001, 304 с., ил.
| |  скачать работу |
Задача коммивояжера |
