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

Учитывая сказанное, определим нижнюю границу маршрутов, за даваемых матрицей W:

j = 9 + 11 + 9 + 17 + 3 + 11 + 15 = 75.

Отметим важный факт: если для любого маршрута вычислить его длину L по матрице W и его же длину L0 по матрице W0, то они связаны соотношением L = L0 + j

где j — сумма всех постоянных приведения. Рассмотрим, например, маршрут А1 ® А3 ® А5 ® А2 ® А4 ® А6 ® А1 По матрице длина L = 73 + 13 + 18 + 44 + 70 + 16 = 234, а по приведенной матрице длина L = 64+4+15+18+53+5 = 159 и L - L0 = = 75 = j. Таким образом, мы выполнили начальный шаг и перейдем теперь к выполнению общего шага.

Общий шаг (повторяющийся многократно)

Определим способ ветвления для задачи коммивояжера. Операция ветвления в этой задаче производится следующим образом. Выбирается некоторая дуга хixj (на ее выборе остановимся ниже), и все множество W разбивается на два непересекающихся подмножества: подмножество маршрутов W2 = W2(хixj) содержащих дугу xixj и подмножество W1= W1 (xixj) ее не содержащих. Символически это изображено на рис. 3.

Мы должны составить матрицы расстояний для полученных множеств. Начнем с множества W1, попутно обсуждая правило выбора дуги хixj для ветвления. Множество W1 получается из множества W исключением маршрутов, содержащих дугу xixj. Исключение этой дуги эквивалентно замене соответствующего ей расстояния аij в матрице прочерком “—“. Например, если выбрана дуга x1x4 то в

W

W1 W2

xixj xixj

Рис. 3

в матрице W0 (табл. 3) вместо элемента а14 ставим прочерк “—“ и получаем матрицу W1(х1х4) (табл. 4).

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

Таблица 4 (матрица W1(х1х4))

Очевидно, что в матрице W1(х1х4) можно проделать операцию приведения с положительной суммой постоянных 0 + 18 = 18. Следовательно, нижняя граница j1 множества W1(х1х4) будет больше нижней границы j = 75 множества на эту величину, то есть

j1= j+ 18 = 75+18 = 93.

Дуга для ветвления выбирается так, чтобы нижняя граница множества W1 = W1(хixj) была, по возможности, большей, то есть чтобы при исключении этой дуги была большей сумма возникающих при этом постоянных приведения. Ясно, что положительные постоянные приведения появятся лишь в случае, когда после исключения дуги хixj в одном из соответствующих ей рядов (строк или столбцов) матрицы расстояний нет нулевых элементов. Поэтому в исходной приведенной матрице ей должен соответствовать нулевой элемент, а в соответствующих ей строке и столбце (хотя бы в одном из этих рядов) не должно быть, по возможности, нулевых элементов. В нашем случае это дуги х1х4, х1х6, х2х5, х3х2, х4х1, х5х3, х6х3. Выпишем в качестве примера матрицу W1 (х4х1), в которой исключена дуга х4х1 (табл. 5).

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

Таблица 5 (матрица W1 (х4х1))

В матрице W1 (х4х1) можно провести операцию приведения с положительной суммой 5+17 = 22. При этом нижняя граница множества W1 (х4х1) будет следующей:

j1 = j + 22 = 75 + 22 = 97

Итак, для матриц W1 (х1х4) и W1 (х4х1) суммы постоянных приведения равны соответственно 18 и 22.

Аналогично можно составить матрицы, в которых исключены дуги х1х6, х2х5, х3х2, х4х1, х5х3, х6х3. Им будут соответствовать следующие суммы постоянных приведения:

W1 (х1х6) : 9, W1 (х2х5) : 9, W1 (х3х2) : 19, W1 (х5х3) : 15, W1 (х6х3) : 5.

Следовательно, для ветвления выберем дугу х4х1 для которой сумма постоянных приведения, равная 22, оказалась наибольшей.

Описанный выше способ выбора дуги основывается на следующих двух соображениях:

1) большее значение нижней границы для W1 позволяет надеяться, что в дальнейшем это множество будет отсечено;

2) включение дуги нулевой длины во все маршруты W2 делает их в какой-то степени “более перспективными”. Поэтому в первую очередь рассматривают множество W2

Все маршруты матрицы W2 содержат выбранную дугу, которой отвечает клетка, расположенная на пересечении i-й строки и j-го столбца матрицы W0. Следовательно, дуги, отвечающие остальным клеткам i-й строки j-го столбца, не войдут ни в один из маршрутов, а тогда эти ряды необходимо удалить из матрицы W0. Кроме того, так как все маршруты матрицы W2 содержат дугу xixj, то они не могут содержать дугу xjxi. В противном случае получился бы контур хi ® xj ® xi который не удовлетворяет поставленной задаче. Поэтому дуга хjxi в W2 должна быть исключена, то есть в матрице W0 элемент aji должен быть заменен прочерком “—“.

Окончательно для получения матрицы расстояний W2(xixj) следует: 1) исключить из матрицы W0 строку, соответствующую началу включаемой дуги, и столбец, соответствующий концу этой дуги; 2) исключить противоположную дугу xjxi, то есть заменить элемент аji матрицы W0 прочерком “—“.

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

Продолжим нашу задачу. Для получения матрицы W2 следует из матрицы W0 (табл. 3) удалить четвертую строку и первый столбец и исключить элемент а14 = 0, то есть элемент а14 = 0 заменить прочерком “—“. Проделав указанные действия, получим матрицу W2 (табл. 6).

Таблица 6 (матрица W2)

	А2	А3	А4	А5	А6	min
А1	59	64	¾	61	0	0
А2	¾	5	18	0	81	0
А3	0	¾	62	4	9	0
А5	15	0	27	¾	55	0
А6	71	0	34	37	¾	0
min	0	0	18	0	0

В табл.6 и в последующих таблицах перенумерация строк и столбцов производиться не будет, то есть номера строк и столбцов в этих матрицах будут соответствовать номерам строк и столбцов матрицы W0.