Задача коммивояжера

Эйлеров цикл в графе существует тогда и только тогда, когда (1) граф связный и (2) все его вершины  имеют четные степени.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2. Деревянный алгоритм

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

Вначале обсудим  свойство спрямления. Рассмотрим какую-нибудь цепь, например, на рис.5. Если справедливо  неравенство треугольника, то

Сложив эти два неравенства, получим  . По неравенству треугольника получим . Окончательно     

Итак, если справедливо  неравенство треугольника, то для  каждой цепи верно, что расстояние от начала до конца цепи меньше (или  равно) суммарной длины всех ребер цепи. Это обобщение расхожего убеждения, что прямая короче кривой.

Вернемся к ЗК и опишем решающий ее деревянный алгоритм.

Построим на входной сети ЗК кратчайшее остовное дерево и удвоим все его  ребра. Получим граф – связный и с вершинами, имеющими только четные степени.

Построим эйлеров цикл , начиная с вершины 1, цикл задается перечнем вершин.

Просмотрим перечень вершин, начиная  с 1, и будем зачеркивать каждую вершину, которая повторяет уже  встреченную в последовательности. Останется тур, который и является результатом алгоритма.

Пример 1. Дана полная сеть, показанная на рис.5. Найти тур жадным и деревянным алгоритмами.

 

 

 

 

 

 

 

 

 

                                                             рис. 5

 

-	1	2	3	4	5	6
1	-	6	4	8	7	14
2	6	-	7	11	7	10
3	4	7	-	4	3	10
4	8	11	4	-	5	11
5	7	7	3	5	-	7
6	14	10	10	11	7	-
табл. 1

 

 

 

                                                             рис. 6

 

Решение. Жадный алгоритм (иди в ближайший город из города 1) дает тур , где без скобок показаны номера вершин, а в скобках – длины ребер. Длина тура равна 39, тур показана на рис. 5.

2. Деревянный алгоритм  вначале строит остовное дерево, показанное на рис. 6 штриховой линией, затем эйлеров цикл , затем тур длиной 43, который показан сплошной линией на рис. 6.

Теорема. Погрешность  деревянного алгоритма равна 1.

Доказательство. Возьмем  минимальный тур длины  и удалим из него максимальное ребро. Длина получившейся гамильтоновой цепи меньше . Но эту же цепь можно рассматривать как остовное дерево, т. к. эта цепь достигает все вершины и не имеет циклов. Длина кратчайшего остовного дерева меньше или равна . Имеем цепочку неравенств

(6)

Но удвоенное дерево – оно  же эйлеров граф – мы свели к  туру посредством спрямлений, следовательно, длина полученного по алгоритму  тура удовлетворяет неравенству

(7)

Умножая (6) на два и  соединяя с (7), получаем цепочку неравенств

(8)

Т.е.

Теорема доказана.

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

Известно еще несколько простых алгоритмов, гарантирующих в худшем случае . Для того, чтобы найти среди них алгоритм поточнее, зайдем с другого конца и для начала опишем «brute-force enumeration» - «перебор животной силой», как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что ЗК с n городами требует при полном переборе рассмотрения

 Туров в симметричной задаче и Туров в несимметричной, а факториал, как показано в следующей таблице, растет удручающе быстро:

5!	10!	15!	20!	25!	30!	35!	40!	45!	50!
~102	~106	~1012	~1018	~10125	~1032	~1040	~1047	~1056	~1064

Чтобы проводить полный перебор  в ЗК, нужно научиться (разумеется, без повторений) генерировать все  перестановки заданного числа m элементов. Это можно сделать несколькими способами, но самый распространенный (т.е. приложимый для переборных алгоритмов решения других задач) – это перебор в лексикографическом порядке.

Пусть имеется некоторый алфавит  и наборы символов алфавита (букв), называемые словами. Буквы в алфавите упорядочены: например, в русском алфавите порядок букв аµбµя (символ читается «предшествует)». Если задан порядок букв, можно упорядочить и слова. Скажем, дано слово

 –  состоящее из букв - и слово

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

Рассмотрим, скажем, перестановки из пяти элементов, обозначенных цифрами  . Лексикографически первой перестановкой является , второй – последней – . Нужно осознать общий алгоритм преобразования любой перестановки в непосредственно следующую.

Правило такое: скажем, дана перестановка . Нужно двигаться по перестановке справа налево, пока впервые не увидим число, меньшее, чем предыдущее (в примере это 3 после 5). Это число, надо увеличить, поставив вместо него какое-то число из расположенных правее, от до . Число большее, чем , несомненно, найдется, так как . Если есть несколько больших чисел, то, очевидно, надо ставить меньшее из них. Пусть это будет . Затем число и все числа от до , не считая нужно упорядочить по возрастанию. В результате получится непосредственно следующая перестановка, в примере – . Потом получится (тот же алгоритм, но упрощенный случай) и т.д.

Нужно понимать, что в ЗК с n городами не нужны все перестановки из n элементов. Потому что перестановки, скажем, и (последний элемент соединен с первым) задают один и тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединять к нему все перестановки из остальных элементов. Этот перебор даст разных туров, т.е. полный перебор в несимметричной ЗК (мы по-прежнему будем различать туры и ).

Данный алгоритм описан на языке Паскаль (см. Приложения).

Пример 2. Решим ЗК, поставленную в Примере 1 лексикографическим перебором. Приведенная выше программа напечатает города, составляющие лучший тур: и его длину 36.

Желательно усовершенствовать  перебор, применив разум. В следующем пункте описан алгоритм, который реализует простую, но широко применимую и очень полезную идею.

 

 

 

 

 

 

 

 

2.3. Метод ветвей и границ

К идее метода ветвей и границ приходили  многие исследователи, но Литтл с  соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.

Общая идея тривиальна: нужно разделить  огромное число перебираемых вариантов  на классы и получить оценки (снизу  – в задаче минимизации, сверху –  в задаче максимизации) для этих классов, чтобы иметь возможность  отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

Изложим алгоритм Литтла на примере 1 предыдущего раздела.. Повторно запишем матрицу:

-	1	2	3	4	5	6
1	-	6	4	8	7	14
2	6	-	7	11	7	10
3	4	7	-	4	3	10
4	8	11	4	-	5	11
5	7	7	3	5	-	7
6	14	10	10	11	7	-
табл. 1

 

 

 

 

 

 

 

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

Кроме очевидного применения ЗК на практике, существует ещё ряд задач, сводимых к решению ЗК.

Задача о  производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами Всю производственную линию будем считать одним процессором. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке. Поскольку производство циклическое, то краски надо производить в циклическом порядке . После окончания производства краски и перед началом производства краски j надо отмыть оборудование от краски . Для этого требуется время Очевидно, что зависит как от , так и от , и что, вообще говоря, . При некотором выбранном порядке придется на цикл производства красок потратить время.

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

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

Операция пробивки j-того отверстия характеризуется  четверкой чисел ( , где - координаты нужного положения стола, - координата нужного положения диска и - время пробивки -того отверстия.

Производство  панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях диск в положении причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами .

Чтобы пробить -тое отверстие непосредственно  после i-того необходимо произвести следующие  действия:

1. Переместить  стол по оси x из положения  в положение , затрачивая при этом время

Проделать то же самое по оси y, затратив время 

Повернуть головку  по кратчайшей из двух дуг из положения  в положение zj, затратив время

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

Конкретный  вид функций  зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости

Действия 1-3 (переналадка  -того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому

Теперь, как  и в предыдущем случае, задача составления  оптимальной программы для дыропробивного пресса сводится к ЗК (здесь - симметричной).

 

 

 

 

 

 

 

 

Заключение

Изучены эвристический, приближенный и точный алгоритмы  решения ЗК.Точные алгоритмы решения  ЗК – это полный перебор или  усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.

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

Проведён анализ наиболее рациональных методов решения  ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора; для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы (Анищенко Сергея Александровича).

Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы

1.О. Оре. Графы и  их применение. Пер. с англ. под  ред. И.М. Яглома. - М., «Мир», 1965, 174 с.

2.Ю. Н. Кузнецов, В.  И. Кузубов, А. Б. Волощенко.  Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.

3.Е. В. Маркова, А.  Н. Лисенков. Комбинаторные планы  в задачах. – М., Наука, 1979, 345 с.