Алгоритм

ТЕМА 2-1.

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

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

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

Пример.

¥

¥

¥

¥

¥

¥

¥

В клеточке іі стоит знак "¥", а не "0", т.к. в алгоритме используется эвристическая процедура слежения за "0" (за минимальным расстоянием, равным 0). В плане использования этой процедуры клетка іі никакой информации не несёт, следовательно можно поставить "¥".

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

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

Справа от матрицы строится дополнительный столбец, куда заносится это минимальное число. Затем числа в столбце складываются.

¥

¥

¥

¥

¥

¥

¥

б). Приведение по столбцам. В каждом столбце матрицы, приведенной по строкам, выбирается минимальное число. Оно вычитается из числа, записанного в каждой клетке рассматриваемого столбца.

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

¥

¥

¥

¥

¥

¥

¥

Затем складываются суммарные результаты строки и столбца. Полученное число есть нижняя граница самого короткого маршрута коммивояжера, т.е. все маршруты, найденные в ходе решения ³96.

2. В приведенной матрице выбираются все нулевые клетки. Каждая такая клетка обеспечивает минимальное расстояние, равное "0" для соответствующей пары. Среди нулевых клеток выбирается такая, которая при замене "0" на "¥" позволит вычесть из своей строки и столбца наибольшее суммарное число.

Указанная процедура тоже является эвристической. Если образуется несколько клеток с одинаковым суммарным результатом, то решение разбивается на несколько параллельных ветвей.

Нулевые клетки	Число, вычитаемое из	Суммарный результат
строки	столбца
(1,2)
(2,1)
(3,5)
(4,6)
(5,6)
(6,1)
(6,7)
(7,2)
(7,3)
(7,4)

Выбор клетки (4,6) означает, что выбран фрагмент маршрута от вершины 4 к вершине 6.

Так как клетка (4,6) выбрана, то вершина 4 больше в маршруте не участвует как вершина выезда, а вершина 6 более не участвует как вершина въезда, поэтому нужно вычеркнуть строку 4 и столбец 6, а в (6,4) поставить знак "¥", т.к. коммивояжер никогда не поедет обратно из 6 в 4.

Матрица примет вид:

¥

¥

¥

¥

¥

¥

Её мы снова приводим по строкам:

¥

¥

¥

¥

¥

¥

Приведение по столбцам в последней матрице невозможно (но нужно).

Сумма, полученная в дополнительном столбце, складывается с нижней границей маршрута и получается новая граница 3+96=99.

Нулевые клетки	Число, вычитаемое из	Суммарный результат
строки	столбца
(1,2)
(2,1)
(3,5)
(5,1)
(6,1)
(6,7)
(7,2)
(7,3)
(7,4)

Снова вычёркиваем строку и столбец, в ячейку (5,3) ставим символ "¥". Полученную матрицу приводим по строкам и столбцам.

¥

¥

¥

¥

¥

Но её привести невозможно (все нули уже есть), поэтому снова составляем таблицу.

Нулевые клетки	Число, вычитаемое из	Суммарный результат
строки	столбца
(1,2)
(2,1)
(5,1)
(6,1)
(6,7)
(7,2)
(7,3)
(7,4)

Вычёркиваем строку 2 и столбец 1. При этом не забывая поставить знак "¥" в ячейку (1,2).

		¥
			¥
				¥
					¥

Приведём по строкам:

¥

¥

¥

¥

Дальнейшее приведение по столбцам невозможно. Нижняя граница вновь изменилась и составила 99+9+4=112.

В полученной матрице вновь выбираем все нулевые клетки и строим таблицу:

Нулевые клетки	Число, вычитаемое из	Суммарный результат
строки	столбца
(1,4)
(5,4)
(6,7)
(7,2)
(7,3)
(7,4)

В последней матрице вычеркиваем строку 1 и столбец 4. В клетке (4,1) мы должны поставить "¥", но такой клетки нет! Если она отсутствует, то используется следующее эвристическое правило:

"Если дуга, добавляемая к построенному пути, идёт из і_n в j_1, а построенный путь состоит из i₁®i₂®i₃®...®i_n и j₁®j₂®...®j_v, то в матрице коммивояжера не должно быть дуги из j_v в i₁, т.к. иначе образуется контур, не являющийся гамильтоновым."

В нашем случае символ "¥" нужно ставить в (6,2).

Тогда матрица примет вид:

			¥
		¥
				¥

После приведения:

¥

¥

¥

Дальнейшее приведение по столбцам невозможно. Нижняя граница вновь изменилась и составила 112+14=126. Выбираем нулевые клетки и строим таблицу:

Нулевые клетки	Число, вычитаемое из	Суммарный результат
строки	столбца
(5,2)
(6,7)
(7,2)
(7,3)

Удаляем строку 6 и столбец 7. В соответствии с правилом в (7,2) ставим "¥".

			¥
		¥

Оставшиеся клетки равноценны. На их основе добавляем недостающие дуги.

Граф примет вид:

Дата добавления: 2015-01-03