Формулировка задачи коммивояжера и алгоритмы ее решения

1.2.4. Алгоритм  Дейкстры

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

Можно предложить много процедур решения  этой задачи, например, физическое моделирование. На плоской доске рисуется карта  местности, в города, лежащие на развилке дорог, вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются верёвками, которые привязываются  к соответствующим кольцам. Чтобы  найти кратчайшее расстояние между  i и k, нужно взять I в одну руку и k в другую и растянуть. Те верёвки, которые натянутся и не дадут разводить руки шире и образуют кратчайший путь между i и k. Однако математическая процедура, которая промоделирует эту физическую, выглядит очень сложно. Известны алгоритмы попроще. Один из них – алгоритм Дейкстры, предложенный Дейкстрой ещё в 1959г. Этот алгоритм решает общую задачу:

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

Алгоритм использует три массива  из n (= числу вершин сети) чисел каждый. Первый массив a содержит метки с двумя значениями: 0 (вершина ещё не рассмотрена) и 1 (вершина уже рассмотрена); второй массив b содержит расстояния – текущие кратчайшие расстояния от v_i до соответствующей вершины; третий массив c содержит номера вершин – k-й элемент c_k есть номер предпоследней вершины на текущем кратчайшем пути из v_i в v_k. Матрица расстояний D_ik задаёт длины дуг d_ik; если такой дуги нет, то d_ik присваивается большое число Б, равное “машинной бесконечности”.

Теперь можно описать:

Алгоритм Дейкстры

1(инициализация).

В цикле от одного до n заполнить нулями массив а; заполнить числом i массив с: перенести i-тую строку матрицы D в массив b;

a[i]:=1; c[i]:=0; {i-номер стартовой вершины}

2(общий шаг).

Найти минимум среди неотмеченных (т. е. тех k, для которых a[k]=0); пусть минимум достигается на индексе j, т. е. b_j£b_k; a[j]:=1;

0	23	12	∞	∞	∞	∞	∞
23	0	25	∞	22	∞	∞	35
12	25	0	18	∞	∞	∞	∞
∞	∞	18	0	∞	20	∞	∞
∞	22	∞	∞	0	23	14	∞
∞	∞	∞	20	23	0	24	∞
∞	∞	∞	∞	14	24	0	16
∞	35	∞	∞	∞	∞	16	0
табл. 12

если b_k>b_j+d_jk то (b_k:=b_j+d_jk; c_k:=j) {Условие означает, что путь v_i..v_k длиннее, чем путь  v_i..v_j,v_k . Если все a[k] отмечены, то длина пути v_i..v_k равна b[k]. Теперь надо перечислить вершины, входящие в кратчайший путь}

3(выдача ответа).

{Путь v_i..v_k выдаётся в обратном порядке следующей процедурой:}

3.1. z:=c[k];

3.2. Выдать z;

3.3. z:=c[z]; Если z = 0, то конец, иначе перейти к 3.2.

Для выполнения алгоритма нужно  n  раз просмотреть массив b из n элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность. Проиллюстрируем работу алгоритма Дейкстры численным примером (для большей сложности, считаем, что некоторые города (вершины)  i,j не соединены между собой, т. е. D[i,j]=∞). Пусть, например, i=3. Требуется найти кратчайшие пути из вершины 3. Содержимое массивов a,b,c после выполнения первого пункта показано на табл. 12:

	1	2	3	4	5	6	7	8
a	0	0	1	0	0	0	0	0
b	12	25	0	18	∞	∞	∞	∞
c	3	3	0	3	3	3	3	3
табл. 13

 

Очевидно, содержимое таблицы меняется по мере выполнения общего шага. Это видно  из следующей таблицы:

		1	2	3	4	5	6	7	8
min bk=12	a	1	0	1	0	0	0	0	0
	b	12	25	0	18	∞	∞	∞	∞
	c	3	3	0	3	3	3	3	3
min bk=18	a	1	0	1	1	0	0	0	0
	b	12	25	0	18	∞	38	∞	∞
	c	3	3	0	3	3	4	3	3
min bk=25	a	1	1	1	1	0	0	0	0
	b	12	25	0	18	47	38	∞	60
	c	3	3	0	3	2	4	3	2
min bk=38	a	1	1	1	1	0	1	0	0
	b	12	25	0	18	47	38	62	60
	c	3	3	0	3	2	4	6	2
min bk=47	a	1	1	1	1	1	1	0	0
	b	12	25	0	18	47	38	61	60
	c	3	3	0	3	2	4	5	2
min bk=60	a	1	1	1	1	1	1	0	1
	b	12	25	0	18	47	38	61	60
	c	3	3	0	3	2	4	5	2

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

Возьмём произвольную пару вершин

j,k. Исключим непосредственное ребро C[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j..k. Пусть это расстояние включает некоторый город m. Имеем часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере – для j,m и m,k) удалим соответственное ребро и найдём кратчайшее расстояние. При этом в кратчайшее расстояние не должен входить уже использованный город.

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

 

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. Всю производственную линию будем считать одним процессором.. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке p=(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))

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

 

 

Выводы

 

1. Изучены эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.
2. Предложен собственный эффективный метод решения ЗК на основе построения выпуклого многоугольника и включения в него центральных вершин (городов).
3. Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора;  для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы (Анищенко Сергея Александровича).
4. Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.
5. Приведены тексты программ, позволяющие решить ЗК различными методами.