Математика (стр. 10 )

aji.

Задача коммивояжера является задачей дискретного программирования. Множеством W служит множество всех маршрутов, функцией j(w) служит длина маршрута w. Так как множество W описывается матрицей расстояний, то саму эту матрицу будем называть матрицей W. Решение задачи коммивояжера рассмотрим на конкретном примере.

Пример 1. Задана матрица расстояний между каждыми двумя из шести городов А1, А2, ..., А6 (матрица W). Требуется найти кратчайший из замкнутых маршрутов, проходящих ровно по одному разу через каждый из этих городов.

	А1	А2	А3	А4	А5	А6	min
А1	¾	68	73	24	70	9	9
А2	58	¾	16	44	11	92	11
А3	63	9	¾	86	13	18	9
А4	17	34	76	¾	52	70	17
А5	60	18	3	45	¾	58	3
А6	16	82	11	60	48	¾	11

Таблица 1 (матрица W)

Начальный шаг (применяемый однократно).

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

Опишем детально операцию приведения матрицы W. Сначала производится приведение по строкам: в каждой строке матрицы выбираем наименьшее число и приписываем его к строке справа (табл. 1), а затем вычитаем его из всех элементов этой строки. В результате получаем новую матрицу (табл. 2).

	А1	А2	А3	А4	А5	А6
А1	¾	59	64	15	61	0
А2	47	¾	5	33	0	81
А3	54	0	¾	77	4	9
А4	0	17	59	¾	35	53
А5	57	15	0	42	¾	55
А6	5	71	0	49	37	¾
min	0	0	0	15	0	0

Таблица 2

Далее в табл. 2 производим операцию приведения по столбцам: в каждом столбце выбираем наименьшее число, приписываем его к столбцу снизу (табл. 2) и вычитаем из всех элементов этого столбца.

	А1	А2	А3	А4	А5	А6
А1	¾	59	64	0	61	0
А2	47	¾	5	18	0	81
А3	54	0	¾	62	4	9
А4	0	17	59	¾	35	53
А5	57	15	0	27	¾	55
А6	5	71	0	34	37	¾

Таблица 3 (матрица W0)

После выполнения обеих операций приведения по строкам и столбцам получили новую матрицу (табл. 3), которую мы обозначили W0 и которая называется приведенной матрицей на множестве W. Каждая строка и каждый столбец приведенной матрицы содержит хотя бы один нулевой элемент. Числа, которые вычитались, называются постоянными приведения. Так как каждая постоянная приведения входит как слагаемое в длину любого маршрута, то длина любого маршрута не меньше суммы всех постоянных приведения. Следовательно, за нижнюю границу на множестве W можно принять сумму всех постоянных приведения. Этим способом будем вычислять нижнюю границу и в дальнейшем.