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

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

Данные занесм в таблицу. Алгоритм лексического перебораКол-во городовВремя обработки, cВероятность неправильного ответа, Тип алгоритма10410точный12120003ч.20мин032-0 100-0Метод ветвей и границ1000точный320.000101001.20Мой алгоритм решения ЗК100.0010приближенный322.5010060- ЗК с таким количеством городов методом лексического перебора современный компьютер не смог бы решить даже за вс время существования Вселенной.

Как видим по результатам этой таблицы, алгоритм лексического перебора можно применять лишь в случае с количеством городов 5 12. Метод ветвей и границ, наряду с моим методом, можно применять всегда. Хотя мой метод я отнс к приближнным алгоритмам, он фактически является точным, так как доказать обратное ещ не удалось. 1.3 Практическое применение задачи коммивояжера Кроме очевидного применения ЗК на практике, существует ещ ряд задач, сводимых к решению ЗК. Задача о производстве красок.

Имеется производственная линия для производства n красок разного цвета обозначим эти краски номерами 1,2 n. Всю производственную линию будем считать одним процессором Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке j1,j2 jn, j1. После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время Ci, j. Очевидно, что Ci, j зависит как от i, так и от j, и что, вообще говоря, Ci, jCj, 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, затрачивая при этом время txxi-xjti, jx 2. Проделать то же самое по оси y, затратив время ti, jy 3. Повернуть головку по кратчайшей из двух дуг из положения zi в положение zj, затратив время ti, jz . 4. Пробить j-тое отверстие, затратив время tj. Конкретный вид функций tx, ty, tz зависит от механических свойств пресса и достаточно громоздок.

Явно выписывать эти функции нет необходимости Действия 1-3 переналадка с i-того отверстия j-тое происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому Сi, j maxtx, ty, tz Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к ЗК здесь - симметричной.