Опишем геометрический метод решения задачи о коммивояжере. Решение задачи геометрическим методом возможно при условии, что в графе любые две вершины смежны и выполняется правило треугольника.
Сформулируем «Правило треугольника»: Длина оптимального маршрута коммивояжера не может быть меньше удвоенной величины максимального веса ребра, выбранного среди множества всех ребер графа:
L1 + L2 > 2 ri , j max. (16.2)
Приведем словесное описание алгоритма. Примем по умолчанию, что L1 – расстояние между вершинами xi и xk, а L2 – расстояние между вершинами xk и xj.
1°. Определим максимальный элемент матрицы R и вершины xk, xh, расстояние между которыми 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. Фиксируем вершины xk, xl, xh и выделяем звенья 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 определит принадлежность xi соответствующему отрезку и xi принадлежит k – l.
5°. Отрезки a – b заменяем согласно 4° отрезками a – c и c – b. Если все вершины просмотрены, то к 7°.
6°. Если две вершины xa, xb отнесены к одному отрезку 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).
ri , j max = max(r (i, j)) = r 1,3 = 65.
Фиксируем вершины x 1, x 3 и для отрезка 1 – 3 строим треугольники с вершинами в точках 2, 4, 5 и 6.
2°. Вычисляем периметры построенных треугольников (рис. 162.22) по формуле (16.3). При этом слагаемое r 1,3 можно пропустить, поскольку оно одинаково для всех выражений.
П123 = 30 + 40 = 70,
П143 = 40 + 30 = 70,
П153= 62 + 55 = 117,
П163 = 28 + 60 = 88.
3°. Выбираем треугольник с максимальной величиной периметра П153 и фиксируем вершины x 1, x 5, x 3. Выделяем два звена: L1 – (x 1 – x 3) и L2 - (x 1 – x 5 и x 5 – x 3) (см. рис. 16.22).
Рис. 16.22. Построение пути коммивояжера
4°. Оставшиеся незадействованными вершины x 2, x 4, x 6 отнесем по принадлежности к отрезкам 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 2. При этом получим, что k = 1, h = 3, l = 5, i = 2. Тогда имеем:
DR1,3 = r 1,2 + r 2,3 – r 1,3 = 30 + 40 - 65 = 5,
DR1,5 = r 1,2 + r 2,5 – r 1,5 = 30 + 40 - 28 = 42,
DR3,5 = r 3,2 + r 2,5 – r 3,5 = 40 + 40 - 55 = 25.
Так как из всех полученных значений DR1,3 = 5 является наименьшим, то вершину x 2 отнесем к отрезку 1 – 3.
Аналогичные вычисления выполняем для вершин x 4 и x 6. Так, для вершины x 4: k = 1, h = 3, l = 5, i = 4. Тогда
DR1,3 = r 1,4 + r 4,3 – r 1,3 = 40 + 30 - 65 = 5,
DR1,5 = r 1,4 + r 4,5 – r 1,5 = 40 + 30 - 28 = 42,
DR3,5 = r 3,4 + r 4,5 – r 3,5 = 30 + 30 - 55 = 5.
Вершину x 4 можно отнести как к отрезку 1 – 3, так и к отрезку 3 – 5. Отнесем ее к отрезку 3 – 5, так как к отрезку 1 – 3 мы уже отнесли вершину x 2.
Для вершины x 6: k = 1, h = 3, l = 5, i = 6. Тогда
DR1,3 = r 1,6 + r 6,3 – r 1,3 = 28 + 60 ─ 65 = 23,
DR1,5 = r 1,6 + r 6,5 – r 1,5 = 28 + 36 ─ 62 = 2,
DR3,5 = r 3,6 + r 6,5 – r 3,5 = 60 + 36 ─ 55 = 41.
Следовательно, вершину x 6 отнесем к отрезку 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 зафиксированы две вершины xi и xj. Тогда надо отнести вершину xj к одному из отрезков 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).
Минимальная из этих двух величин определяет принадлежность вершины xj к отрезку k – i или отрезку i – h. Аналогично определяем принадлежность всех остальных вершин для других отрезков и переходим к п. 5°.
7°. Построен следующий маршрут коммивояжера: x 1 – x 2 – x 3 – x 4 – x 5 – x 6 – x 1. Его длина равна 194.
На рис. 16.23 показан ГЦ с весами на ребрах, когда сумма весов пройденных ребер минимальна.
Рис. 16.23. Решение задачи коммивояжера
Алгоритм справедлив только для графа, у которого выполняется правило треугольника.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Пример 1. Пусть задан граф G, изображенный на рис. 16.24. Решить задачу коммивояжера для заданного графа, используя алгоритм Хелда─Карпа.
Рис. 16.24. Исходный граф
Решение: Построим матрицу расстояний заданного графа:
.
1. В соответствии с заданным алгоритмом определяем прямые пути из вершины x 1 в вершину xj, где j = (2, 3, 4): d 12 = 3; d 13 = 1; d 14 = 4.
2. Теперь определяем пути из вершины x 1 в вершину xj через одну промежуточную вершину:
d 312 = d 13 + d 32 = 1 + 5 = 6; d 314 = d 13 + d 34 = 1 + 4 = 5; d 213 = d 12 + d 23 = 3 + 5 = 8;
d 214 = d 12 + d 24 = 3 + 6 = 9; d 412 = d 14 + d 42 = 2 + 6 = 8; d 413 = d 14 + d 43 = 2 + 4 = 6.
3. Определяем пути из вершины x 1 в вершину xj через две промежуточные вершины:
d 3,412 = d 314 + d 42 = d 13 + d 34 + d 42 = 1 + 4 + 6 = 11; d 2,413 = d 214 + d 43 = d 12 + d 24 + d 43 = 3 + 6 + 4 = 13; d 2,314 = d 213 + d 34 = d 12 + d 23 + d 34 = 3 + 5 + 4 = 12;
d 4,312 = d 413 + d 32 = d 14 + d 43 + d 32 = 2 + 4 + 5 = 11; d 4,213 = d 412 + d 23 = d 14 + d 42 + d 23
= 2 + 6 + 5 = 13; d 3,214 = d 312 + d 24 = d 13 + d 32 + d 24 = 1 + 5 + 6 = 12.
4. Теперь к полученной длине пути добавляем длину возвращения в исходный пункт:
d 12 = d 3,412 (или d 4312) + d 21 = 11 + 3 = 14; d 13 = d 2413 (или d 4213) + d 31 = 13 + 1 = =14; d 14 = d 2314 (или d 3214) + d 41 = 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 14 = 66. Вершины x 1 и x 4 фиксируем.
2. Строим треугольники с основанием x 1 – x 3 (рис. 16.25,а).
Вычисляем периметры получившихся треугольников:
П124 = 40 + 63 = 103;
П134 = 29 + 38 = 67;
П154 = 52 + 28 = 80;
П164 = 36 + 56 = 92.
3. Выбираем треугольник П124, имеющий максимальную длину. Фиксируем вершины x 1, x 2, x 4. Выделяем два звена L1 = (x 1 – x 4) и L2 = (x 1 – x 2 и x 2 – x 4) (рис. 16.25, б).
а б
Рис. 16.25. Построение пути коммивояжера а – шаг 1; б – шаг 2
4. Подсчитываем значения DR для вершин x 3, x 5, x 6.
а) Для вершины x 3:
DR12 = r 13 + r 32 - r 12 = 29 + 41 - 40 = 30;
D R 14 = r 13 + r 34 - r 14 = 29 + 38 - 66 = 1;
DR24 = r 23 + r 34 - r 24 = 41 + 38 - 63 = 16.
б) Для вершины x 5:
DR12 = r 15 + r 52 - r 12 = 52 + 37 - 40 = 49;
DR14 = r 15 + r 54 - r 14 = 52 + 28 - 66 = 24;
D R24 = r 25 + r 54 - r 24 = 37 + 28 - 63 = 2.
в) Для вершины x 6:
DR12 = r 16 + r 62 - r 12 = 36 + 50 - 40 = 46;
D R 14 = r 16 + r 64 - r 14 = 36 + 56 - 66 = 26;
DR24 = r 26 + r 64 - r 24 = 50 + 56 - 63 = 43.
5. В результате проведенных подсчетов получилось, что вершина x 5 должна быть отнесена к отрезку x 2 – x 4, вершины x 3 и x 6 относятся к отрезку x 1 – x 4. Следовательно, заменяем отрезок x 2 – x 4 двумя отрезками x 2 – x 5 и x 5 – x 4. Сравниваем полученные значения DR14 для вершин x 3 (DR14 = 1) и x 6 (DR14 = 26). Вершину (x 3), соответствующую меньшему из двух значению DR14, оставляем, а через вершину x 6 строим обход x 1 – x 6 и x 6 – x 4 (рис. 16.25, в). После чего переходим к пункту 6.
6. Для вершины x 3 подсчитываем значения DR16 и DR64, для того чтобы определить к какому из этих двух отрезков она должна быть отнесена (рис. 16.25,г).
Для вершины x 3:
DR16 = r 13 + r 36 – r 16 = 29 + 42 – 36 = 35;
D R 64 = r 63 + r 34 – r 64 = 42 + 38 – 56 = 24.
Вершину x 3 отнесем к отрезку x 4 – x 6. После этого шага все вершины графа рассмотрены.
в г
Рис. 16.25. Построение пути коммивояжера в – шаг 3; г – шаг 4
7. В результате мы получили решение задачи о коммивояжере (рис. 16.25, д).
Длина построенного маршрута коммивояжера равна:
r 12 + r 25 + r 54 + r 43 + r 36 + r 61 = 40 + 37 + 28 + 38 + 42 + 36 = 221.
д
Рис. 16.25. Построение пути коммивояжера д – результат
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1. В каких задач науки и практики может быть использована задача коммивояжера?
2. Дайте определение задачи коммивояжера?
3. В чем состоит идея алгоритма Хелда–Карпа?
4. На чем основан геометрический метод решения задачи коммивояжера?
5. Какие методы решения задачи коммивояжера вы знаете?
6. Какова сложность алгоритма Хелд–Карпа?
7. В чем состоит «правило треугольника»? Сформулируйте его.
8. Каким образом строятся треугольники в графе при решении задачи коммивояжера?
9. В чем заключаются недостатки и преимущества алгоритма Хелда–Карпа?
10. В чем заключаются недостатки и преимущества геометрического метода решения задачи коммивояжера?
