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

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

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

L1 + L2 > 2r_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 вычисляем

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

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

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

Наименьшая R определит принадлежность 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),

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

R(l, h) = r(l, i) + r(i, h) - r(l, h) (16.4)

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

R_1,3 = r_1,2 + r_2,3 – r_1,3 = 30 + 40 - 65 = 5,

R_1,5 = r_1,2 + r_2,5 – r_1,5 = 30 + 40 - 28 = 42,

R_3,5 = r_3,2 + r_2,5 – r_3,5 = 40 + 40 - 55 = 25.

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

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

R_1,3 = r_1,4 + r_4,3 – r_1,3 = 40 + 30 - 65 = 5,

R_1,5 = r_1,4 + r_4,5 – r_1,5 = 40 + 30 - 28 = 42,

R_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. Тогда

R_1,3 = r_1,6 + r_6,3 – r_1,3 = 28 + 60 ─ 65 = 23,

R_1,5 = r_1,6 + r_6,5 – r_1,5 = 28 + 36 ─ 62 = 2,

R_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.

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

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

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

R_ki = r(k, j) + r(j, i) – r(k, i), R_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. Решение задачи коммивояжера

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