Геометрический метод решения

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

Сформулируем «Правило треугольника»: Длина оптимального маршрута коммивояжера не может быть меньше удвоенной величины максимального веса ребра, выбранного среди множества всех ребер графа:

                                        L1 + L2 > 2 r_{i , j} ^max.                                 (16.2)

Приведем словесное описание алгоритма. Примем по умолчанию, что L1 – расстояние между вершинами x_i и x_k, а L2 – расстояние между вершинами x_k и x_j.

1°. Определим максимальный элемент матрицы R и вершины x_k, x_h, расстояние между которыми max.

2°. Строятся треугольники с основанием k – h с вершинами i Î I = {1, 2,..., n}, i ¹ k, i ¹ h. Таких треугольников будет n - 2. Вычисляем их периметры по формуле:

                                 П _kih = r (k, i) + r (i, h) + r (k, h)                      (16.3)

3°. Находим П_max = П _klh. Фиксируем вершины x_k, x_l, x_h и выделяем звенья L1 – (k – h), L2 – (k – l), (l – h). Далее оставшиеся n – 3 вершины включаются либо в L1, либо в L2.

4°. Для каждого фиксированного i ¹ l, i ¹ k, i ¹ h вычисляем

DR(k, h) = r (k, i) + r (I, h) – r (k, h).

DR(k, l) = r (k, i) + r (I, l) – r (k, l).

DR(l, h) = r (k, i) + r (I, h) – r (l, h).

Наименьшая DR определит принадлежность x_i соответствующему отрезку и x_i принадлежит k – l.

5°. Отрезки a – b заменяем согласно 4° отрезками a – c и c – b. Если все вершины просмотрены, то к 7°.

6°. Если две вершины x_a, x_b отнесены к одному отрезку k – h ® k – a, a – h и делают k – b – a или a – b – h.

7°. Определяем длину маршрута.

Например, пусть имеется 6 городов, расстояния между которыми известны. Матрица смежности графа запишется следующим образом:

	1	2	3	4	5	6
1	¥	30	65	40	62	28
	30	¥	40	20	40	60
R = 3	65	40	¥	30	55	60	.
4	40	20	30	¥	30	32
5	62	40	55	30	¥	36
6	28	60	60	32	36	¥

Согласно 1° определим пару вершин, расстояние между которыми максимально (наибольший элемент матрицы R).

r_{i , j} ^max = max(r (i, j)) = r _1,3 = 65.

Фиксируем вершины x ₁, x ₃ и для отрезка 1 – 3 строим треугольники с вершинами в точках 2, 4, 5 и 6.

2°. Вычисляем периметры построенных треугольников (рис. 162.22) по формуле (16.3). При этом слагаемое r _1,3 можно пропустить, поскольку оно одинаково для всех выражений.

П₁₂₃ = 30 + 40 = 70,

П₁₄₃ = 40 + 30 = 70,

П₁₅₃= 62 + 55 = 117,

П₁₆₃ = 28 + 60 = 88.

3°. Выбираем треугольник с максимальной величиной периметра П₁₅₃ и фиксируем вершины x ₁, x ₅, x ₃. Выделяем два звена: L1 – (x ₁ – x ₃) и L2 - (x ₁ – x ₅ и x ₅ – x ₃) (см. рис. 16.22).

Рис. 16.22. Построение пути коммивояжера

4°. Оставшиеся незадействованными вершины x ₂, x ₄, x ₆ отнесем по принадлежности к отрезкам 1 – 3, 1 – 5, 5 – 3. Для этого с учетом правила треугольника, гласящего, что сумма длин двух сторон треугольника всегда больше длины третьей стороны

r (i, j) + r (j, k) > r (i, k), r (i, k) + r (k, j) > r (i, j), r (k, i) + r (i, j) > r (k, j),

используем следующую формулу:

                                   DR(l, h) = r (l, i) + r (i, h) - r (l, h)               (16.4)

Начнем с вершины x ₂. При этом получим, что k = 1, h = 3, l = 5, i = 2. Тогда имеем:

DR_1,3 = r _1,2 + r _2,3 – r _1,3 = 30 + 40 - 65 = 5,

DR_1,5 = r _1,2 + r _2,5 – r _1,5 = 30 + 40 - 28 = 42,

DR_3,5 = r _3,2 + r _2,5 – r _3,5 = 40 + 40 - 55 = 25.

Так как из всех полученных значений DR_1,3 = 5 является наименьшим, то вершину x ₂ отнесем к отрезку 1 – 3.

Аналогичные вычисления выполняем для вершин x ₄ и x ₆. Так, для вершины x ₄: k = 1, h = 3, l = 5, i = 4. Тогда

DR_1,3 = r _1,4 + r _4,3 – r _1,3 = 40 + 30 - 65 = 5,

DR_1,5 = r _1,4 + r _4,5 – r _1,5 = 40 + 30 - 28 = 42,

DR_3,5 = r _3,4 + r _4,5 – r _3,5 = 30 + 30 - 55 = 5.

Вершину x ₄ можно отнести как к отрезку 1 – 3, так и к отрезку 3 – 5. Отнесем ее к отрезку 3 – 5, так как к отрезку 1 – 3 мы уже отнесли вершину x ₂.

Для вершины x ₆: k = 1, h = 3, l = 5, i = 6. Тогда

DR_1,3 = r _1,6 + r _6,3 – r _1,3 = 28 + 60 ─ 65 = 23,

DR_1,5 = r _1,6 + r _6,5 – r _1,5 = 28 + 36 ─ 62 = 2,

DR_3,5 = r _3,6 + r _6,5 – r _3,5 = 60 + 36 ─ 55 = 41.

Следовательно, вершину x ₆ отнесем к отрезку 1 – 5. Теперь производим включение каждой вершины в маршрут.

5°. Отрезок 1 – 3 заменяем двумя отрезками 1 – 2 и 2 – 3. Аналогично отрезок 3 – 5 заменяем отрезками 3 – 4 и 4 – 5, а отрезок 1 – 5 – отрезками 1 – 6 и 6 – 5.

Если все вершины включены в маршрут, то алгоритм закончен, надо вычислить только длину маршрута и перейти к пункту 7°. В противном случае переход к п. 6°.

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

6°. Все вершины отнесены к отрезкам k – l, k – h и l – h. Пусть, например, для отрезка k – h зафиксированы две вершины x_i и x_j. Тогда надо отнести вершину x_j к одному из отрезков k – i или i – h.

Для этого вычисляем значения

DR _ki = r (k, j) + r (j, i) – r (k, i), DR _ih = r (i, j) + r (j, h) - r (i, h).

Минимальная из этих двух величин определяет принадлежность вершины x_j к отрезку k – i или отрезку i – h. Аналогично определяем принадлежность всех остальных вершин для других отрезков и переходим к п. 5°.

7°. Построен следующий маршрут коммивояжера: x ₁ – x ₂ – x ₃ – x ₄ – x ₅ – x ₆ – x ₁. Его длина равна 194.

На рис. 16.23 показан ГЦ с весами на ребрах, когда сумма весов пройденных ребер минимальна.

Рис. 16.23. Решение задачи коммивояжера

Алгоритм справедлив только для графа, у которого выполняется правило треугольника.