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

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

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

                                        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. Решение задачи коммивояжера

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

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 1. Пусть задан граф G, изображенный на рис. 16.24. Решить задачу коммивояжера для заданного графа, используя алгоритм Хелда─Карпа.

Рис. 16.24. Исходный граф

Решение: Построим матрицу расстояний заданного графа:

.

1. В соответствии с заданным алгоритмом определяем прямые пути из вершины x ₁ в вершину x_j, где j = (2, 3, 4): d ₁₂ = 3; d ₁₃ = 1; d ₁₄ = 4.

2. Теперь определяем пути из вершины x ₁ в вершину x_j через одну промежуточную вершину:

d ³₁₂ = d ₁₃ + d ₃₂ = 1 + 5 = 6; d ³₁₄ = d ₁₃ + d ₃₄ = 1 + 4 = 5; d ²₁₃ = d ₁₂ + d ₂₃ = 3 + 5 = 8;

d ²₁₄ = d ₁₂ + d ₂₄ = 3 + 6 = 9; d ⁴₁₂ = d ₁₄ + d ₄₂ = 2 + 6 = 8; d ⁴₁₃ = d ₁₄ + d ₄₃ = 2 + 4 = 6.

3. Определяем пути из вершины x ₁ в вершину x_j через две промежуточные вершины:

d ^3,4₁₂ = d ³₁₄ + d ₄₂ = d ₁₃ + d ₃₄ + d ₄₂ = 1 + 4 + 6 = 11; d ^2,4₁₃ = d ²₁₄ + d ₄₃ = d ₁₂ + d ₂₄ + d ₄₃ = 3 + 6 + 4 = 13; d ^2,3₁₄ = d ²₁₃ + d ₃₄ = d ₁₂ + d ₂₃ + d ₃₄ = 3 + 5 + 4 = 12;

d ^4,3₁₂ = d ⁴₁₃ + d ₃₂ = d ₁₄ + d ₄₃ + d ₃₂ = 2 + 4 + 5 = 11; d ^4,2₁₃ = d ⁴₁₂ + d ₂₃ = d ₁₄ + d ₄₂ + d ₂₃

= 2 + 6 + 5 = 13; d ^3,2₁₄ = d ³₁₂ + d ₂₄ = d ₁₃ + d ₃₂ + d ₂₄ = 1 + 5 + 6 = 12.

4. Теперь к полученной длине пути добавляем длину возвращения в исходный пункт:

d ₁₂ = d ^3,4₁₂ (или d ⁴³₁₂) + d ₂₁ = 11 + 3 = 14; d ₁₃ = d ²⁴₁₃ (или d ⁴²₁₃) + d ₃₁ = 13 + 1 = =14; d ₁₄ = d ²³₁₄ (или d ³²₁₄) + d ₄₁ = 12 + 2 = 14.

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

Пример 2. Пусть задан граф G = (X, U). Решить задачу о коммивояжере для заданного графа геометрическим методом.

Решение: Зададим граф G = (X, U) матрицей расстояний, а поскольку граф неориентированный, то для его однозначного задания вполне достаточно треугольной матрицы

		1	2	3	4	5	6
R =	1	¥	40	29	66	52	36	.
	2		¥	41	63	37	50
	3			¥	38	48	42
	4				¥	28	56
	5					¥	32
	6						¥

1. Определяем по матрице R элемент с максимальным весом. Это элемент r ₁₄ = 66. Вершины x ₁ и x ₄ фиксируем.

2. Строим треугольники с основанием x ₁ – x ₃ (рис. 16.25,а).

Вычисляем периметры получившихся треугольников:

П₁₂₄ = 40 + 63 = 103;

П₁₃₄ = 29 + 38 = 67;

П₁₅₄ = 52 + 28 = 80;

П₁₆₄ = 36 + 56 = 92.

3. Выбираем треугольник П₁₂₄, имеющий максимальную длину. Фиксируем вершины x ₁, x ₂, x ₄. Выделяем два звена L₁ = (x ₁ – x ₄) и L₂ = (x ₁ – x ₂ и x ₂ – x ₄) (рис. 16.25, б).

                           

      а                                                   б

Рис. 16.25. Построение пути коммивояжера а – шаг 1; б – шаг 2

4. Подсчитываем значения DR для вершин x ₃, x ₅, x ₆.

а) Для вершины x ₃:

DR₁₂ = r ₁₃ + r ₃₂ - r ₁₂ = 29 + 41 - 40 = 30;

D R ₁₄ = r ₁₃ + r ₃₄ - r ₁₄ = 29 + 38 - 66 = 1;

DR₂₄ = r ₂₃ + r ₃₄ - r ₂₄ = 41 + 38 - 63 = 16.

б) Для вершины x ₅:

DR₁₂ = r ₁₅ + r ₅₂ - r ₁₂ = 52 + 37 - 40 = 49;

DR₁₄ = r ₁₅ + r ₅₄ - r ₁₄ = 52 + 28 - 66 = 24;

D R₂₄ = r ₂₅ + r ₅₄ - r ₂₄ = 37 + 28 - 63 = 2.

в) Для вершины x ₆:

DR₁₂ = r ₁₆ + r ₆₂ - r ₁₂ = 36 + 50 - 40 = 46;

D R ₁₄ = r ₁₆ + r ₆₄ - r ₁₄ = 36 + 56 - 66 = 26;

DR₂₄ = r ₂₆ + r ₆₄ - r ₂₄ = 50 + 56 - 63 = 43.

5. В результате проведенных подсчетов получилось, что вершина x ₅ должна быть отнесена к отрезку x ₂ – x ₄, вершины x ₃ и x ₆ относятся к отрезку x ₁ – x ₄. Следовательно, заменяем отрезок x ₂ – x ₄ двумя отрезками x ₂ – x ₅ и x ₅ – x ₄. Сравниваем полученные значения DR₁₄ для вершин x ₃ (DR₁₄ = 1) и x ₆ (DR₁₄ = 26). Вершину (x ₃), соответствующую меньшему из двух значению DR₁₄, оставляем, а через вершину x ₆ строим обход x ₁ – x ₆ и x ₆ – x ₄ (рис. 16.25, в). После чего переходим к пункту 6.

6. Для вершины x ₃ подсчитываем значения DR₁₆ и DR₆₄, для того чтобы определить к какому из этих двух отрезков она должна быть отнесена (рис. 16.25,г).

Для вершины x ₃:

DR₁₆ = r ₁₃ + r ₃₆ – r ₁₆ = 29 + 42 – 36 = 35;

D R ₆₄ = r ₆₃ + r ₃₄ – r ₆₄ = 42 + 38 – 56 = 24.

Вершину x ₃ отнесем к отрезку x ₄ – x ₆. После этого шага все вершины графа рассмотрены.

                       

          в                                                   г

Рис. 16.25. Построение пути коммивояжера в – шаг 3; г – шаг 4

7. В результате мы получили решение задачи о коммивояжере (рис. 16.25, д).

Длина построенного маршрута коммивояжера равна:

r ₁₂ + r ₂₅ + r ₅₄ + r ₄₃ + r ₃₆ + r ₆₁ = 40 + 37 + 28 + 38 + 42 + 36 = 221.

 д

Рис. 16.25. Построение пути коммивояжера д – результат

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. В каких задач науки и практики может быть использована задача коммивояжера?

2. Дайте определение задачи коммивояжера?

3. В чем состоит идея алгоритма Хелда–Карпа?

4. На чем основан геометрический метод решения задачи коммивояжера?

5. Какие методы решения задачи коммивояжера вы знаете?

6. Какова сложность алгоритма Хелд–Карпа?

7. В чем состоит «правило треугольника»? Сформулируйте его.

8. Каким образом строятся треугольники в графе при решении задачи коммивояжера?

9. В чем заключаются недостатки и преимущества алгоритма Хелда–Карпа?

10. В чем заключаются недостатки и преимущества геометрического метода решения задачи коммивояжера?