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

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

Пусть связный неориентированный граф T некоторый остов графа G, a некоторая фиксированная вершина, называемая корнем дерева T. Разместим вершины из M по этажам таким образом, чтобы корень a находился в верхнем этаже, смежные с ним вершины занимали этаж на единицу ниже, смежные с отмеченными вершинами еще на единицу ниже и т.д. (рис. 4.35). таким образом, получаем e(a) 1 этажей, где e(a) эксцентриситет вершины a.

a

1

2

3

4

рис. 4.35

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

На рис. 4.36 показана очередность обхода вершин по глубине графа, изображенного на рис. 4.35.

1

2 12

8 19

3 7 9 13 14 16

4 10 11 15

17 18

5 6

рис. 4.36

При обходе графа по ширине просмотр вершин дерева ведется по этажам, переход к вершинам следующего этажа производится только после просмотра всех вершин данного этажа. На рис. 4.37 показан порядок обхода по ширине графа, изображенного на рис. 4.35.

1

2 4

3 10

5 6 7 8 9 15

11 12 13 14

18 19

16 17

рис. 4.37

Очевидно, что при обходе всех вершин оба подхода: поиск в глубину и поиск по ширине эквивалентны. Если же достаточно найти одну вершину с определенным свойством, то целесообразность применения поиска решения по глубине или по ширине определяется структурой дерева. Если дерево является достаточно широким, а висячие вершины расположены на сравнительно близких этажах, то целесообразно вести поиск по глубине. Для глубоких узких деревьев, когда висячие вершины могут встретиться на различных этажах и их разброс по этажам достаточно велик, предпочтение отдается поиску по ширине.

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

Часто при решении задач их разбивают на несколько более простых задач, которые, в свою очередь, разбиваются на более простые подзадачи и так до тех пор, пока не появляются подзадачи, поддающиеся непосредственному решению. Такое разбиение задач можно представить в виде дерева следующим образом. Если задача A разбивается на подзадачи A(1,1),A(1,2), … …,A(1,n₁), подзадача A(1,i) на подзадачи A(2,i,1), …, …, A и т.д., то получается дерево, изображенное на рис. 4.38.

А

А(1,1) А(1,2)... А(1,n₁)

...

А(2,1,1)... А(2,1,n₂₁) А(2,n₁,1)...

............

рис. 4.38

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

Пусть матрица весов графов не имеющего петель, где . Для простоты будем считать, что все веса неотрицательны. Найдем нижнюю оценку весов гамильтоновых циклов. Для этого в матрице весов найдем минимальные числа каждой строки: , , …, . Очевидно, что вес произвольного гамильтонова цикла не меньше . Преобразуем матрицу весов, вычитая из каждой строки соответствующее число . Получаем матрицу , где . В ней найдем минимальные числа каждого столбца: , , , , и преобразуем ее, вычитая из каждого столбца соответсвующее число : , где . Для любого гамильтонова цикла X справедлива оценка веса цикла X: h, где h .

Обозначим через множество гамильтоновых циклов, в которых первые k вершин a₁,a₂, …, , a(k+1)-я вершина не принадлежит множеству . Используя введенные обозначения, можем разбить нашу задачу на две подзадачи, поделив множество гамильтоновых циклов на множества (рис. 4.39).

При рассмотрении множества отождествим в графе G вершины 1 и (обозначим новую вершину через x) и получим граф G̕ с множеством вершин и матрицей весов

.

Для графа G̕ найдем нижнюю оценку h̕ весов гамильтоновых циклов аналогично тому, как найдены оценки h. Тогда нижняя оценка h₁ весов гамильтоновых циклов множества равна h+h̕.

H

h₁

h₂

h₁₁

h₁₂

h₂₂

h₂₁

h₁₁₁

.....................

рис. 4.39

При рассмотрении множества (1) {k₁} в матрице весов W* элемент заменяется на и по полученной матрице W находится нижняя оценка h˝ весов гамильтоновых циклов графа с матрицей весов W˝. Тогда нижняя оценка h₂ весов гамильтоновых циклов множества (1) {k₁} равна h .

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

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

П р и м е р 4.9.1. рассмотрим граф с матрицей весов

.

Найдем минимальные числа строк: , где 2= .

Вычитая соответствующие числа из каждой строки, получим матрицу

.

После нахождения наименьших значений по столбцам (4,0,0,1,0,0) и вычитания из каждого столбца матрицы соответствующего числа образуется матрица

.

Суммируя элементы и получаем нижнюю оценку h=14. Так как , то множество гамильтоновых циклов разобьем на два множества (1,5) и (рис. 4.40).

H

рис. 4.40

При рассмотрении множества (1,5) получаем матрицу весов

.

графа G̕, образованного отождествлением вершин 1 и 5 графа G. Минимальные элементы строк матрицы W̕ образуют столбец

а минимальные элементы столбцов матрицы образуют нулевую строку, и значит, (W̕)*=(W̕)ˇ. Таким образом, оценка h₁ будет равна h+h̕=14+1=15.

Рассматривая множество (1) {5}, мы должны в матрице W* заменить элемент . Тогда оценка h₂ будет h+h̕=14+2=16.

Поскольку h₁<h₂, выбираем множество (1,5) и соответствующую матрицу весов (W̕)*. Теперь в силу того, что (w*)_x3=0, разобьем множество гамильтоновых циклов из множества (1,5) на множества (1,5,3) и (1,5) Рассматривая случай (1,5,3) , получаем матрицу весов

.

графа G˝, образованного отождествлением вершин x и 3 графа G̕. Оценка h₁₁ равна 15, а (W˝)* W˝. При рассмотрении множества (1,5) в матрице (W̕)* заменяем элемент (w̕)*₂₃=0 на и получаем оценку h₁₂=h₁+2=17.

Так как h₁₁< h₁₂, выберем множество (1,5,3) с матрицей весов (W˝)*=W˝. Поскольку (W˝)*_x4=0, рассмотрим множества циклов (1,5,3,4) и (1,5,3) . Для оценивания весов в множестве (1,5,3,4) отождествим вершины x и 4 в графе G˝ и получим граф G̕̕̕ с матрицей весов

.

Очевидно, что h₁₁₁= h₁₁=15, а (W˝̕)* элемент (w˝)*_x4=0 на и получаем оценку h₁₁₂= h₁₁+2=17.

Так как h₁₁₁ h₁₁₂, то переходим к рассмотрению множества (1,5,3,4) , состоящего из двух гамильтоновых циклов (1,5,3,4,2,6,1) и (1,5,3,4,6,2,1). Первый из этих циклов будет иметь вес , поскольку (W̕̕̕)₂₆= , а вес второго цикла 15, что соответствует оценке h₁₁₁=15. Поскольку оценки h₂, h₁₂ и h₁₁₂ больше h₁₁₁, соответствующие множества не содержат гамильтонова цикла веса, меньшего 15, и поэтому цикл (1,5,3,4,6,2,1) является гамильтоновым циклом минимального веса.