Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 [ 88 ] 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

В разд. 6 ЭТОЙ главы мы исследуем путь, основанный на лютоде (II), а в в разд. 7 будет рассмотрен метод (I). Следует, однако, помнить, что хотя задача о назначениях определена для графов с произвольной структурой весов, кратчайший остов определяется только для неориентированных графов, т. е. для графов с симметричной {Cij = Cji) матрицей весов. Для несимметричных матриц весов (т. е. ориентированных графов) в гл. 7 было введено понятие древесности - аналог понятия остова. Таким образом, то, что было сказано о связи между задачей коммивояжера и кратчайшим остовом для неориентированных графов, имеет точный эквивалент, относяш,ийся к связи между задачей коммивояжера и кратчайшей древесностью в случае ориентированных графов. В следуюш,ем разделе, однако, мы ограничимся симметричной задачей, так как распространение на более обш,ий случай производится очевидным способом.

6. Задача коммивояжера и задача о кратчайшем остове

Как уже отмечалось в предыдуш,ем разделе, симметричная задача коммивояжера тесно связана с задачей о кратчайшем остове графа G, и открытая задача коммивояжера (т. е. задача нахождения кратчайшей гамильтоновой цепи в графе) практически эквивалентна задаче нахождения кратчайшего остова графа G, с тем ограничением, что никакая вершина не должна иметь степень, большую чем 2. Ввиду того, что открытая задача коммивояжера несколько более сильно связана с задачей о кратчайшем остове, чем замкнутая, мы начнем с рассмотрения сначала этой задачи, отложив на конец раздела обсуждение тех небольших изменений, которые необходимо сделать в замкнутой (обычной) задаче коммивояжера.

Задача нахождения кратчайшей гамильтоновой цепи была впервые исследована Део и Хакими [13], давшими ее формулировку на языке линейного программирования. Для полного графа с п вершинами их формулировка содержит п [п -\-\) переменных ТА п {п -\- 3)/2 -f 1 ограничений, которые формулируются явно. Наряду с этим имеется очень большое число ограничений, которые нельзя сформулировать явно, но которые рассматриваются неявно, причем за один раз (после каждого итерационного применения симплекс-метода) вводятся немногие из них. Хотя метод линейного программирования и дает всегда решение, он не будет здесь больше обсуждаться, так как обладает врожденной громоздкостью и неэффективностью .



6.1. Определения

Пусть G = {X, А) - реберно-взвешенный неориентированный граф, а - степень вершины Х; в графе G. Число вершин в G будет обозначаться через п = \ X \.

Если задан остов Т = (Х, А^) графа G и степень вершины в дереве Т обозначена через dj, можно определить близость этого остова к гамильтоновой цепи одним из следующих двух способов:

ет= S (4-2) (10.8(a))

dT>2

er=S 1-21-2. (10.8(6))

Выражение (10.8)(а) учитывает близость только по тем вершинам, для которых df > 2, в то время как (10.8)(б) принимает во внимание и вершины степени 1. Оба эти выражения для гамильтоновой цепи дают = О и можно считать, что чем больше е^, тем сильнее дерево Т отличается от гамильтоновой цепи.

Теперь мы рассмотрим две следующие задачи.

Задача (а). Кратчайшая гамильтонова цепь. Найти кратчайший остов Т* ~ (Х, А*) графа G, такой, что степени всех вершин не превышают 2.

За-дача (б). Кратчайшая гамильтонова цепь с отмеченными концевыми вершинами. Заданы две вершины и х^ (ж^, х^, X), найти кратчайший остов 7*1,2 = {X, 1,2), такой, что степени всех вершин не превышают 2, а степени вершин х^ и х^ равны 1.

Теперь нужно проверить подразумеваемое в сформулированных задачах утверждение о том, что дерево Т, все вершины которого имеют степень, не больше чем 2, является на самом деле гамильтоновой цепью. Действительно, так как Т - дерево, то степень никакой его вершины не может быть равной нулю и, следовательно, = 1 или 2 для всех i. Пусть q вершин имеют степень 1, а п - q имеют степень 2. Число ребер в дереве равно

п

mr-dL (10.9)

так как при суммировании каждое ребро считается дважды, по одному разу для каждой из его конечных вершин. Из уравнения (10.9) получим

mr = 4[? + 2(n-g)] = --!-.



Так как число ребер в дереве равно п - 1, то q - 2 ш поэтому ровно две вершины имеют степень 1, а п - 2 вершин - степень 2, т. е. Т является гамильтоновой цепью.

6.2. Алгоритм поиска, использующий дерево решений

6.2.1. Решение задачи (а). Мы рассмотрим сначала задачу (а) и объясним суть алгоритма, использующего дерево решений, на одном примере.

Пример. В качестве примера возьмем полный граф с 6 вершинами из работы Део и Хакими [13] со следующей матрицей весов:

с помощью метода гл. 7 легко найти кратчайший остов этого графа (без ограничений на dj); он показан на рис. 10.10 (а). Из этого рисунка видно, что = 3, а так как нам нужен кратчайший остов, для которого dj2, то можно сказать, что в окончательном ответе должно отсутствовать по крайней мере одно из ребер (2,1), (2,6) или (2,5). Таким образом, решение первоначальной задачи является решением по крайней мере одной из следующих трех частных задач, изображаемых узлами В, С и D дерева решений на рис. 10.11. На этом рисунке узел А представляет первоначальную задачу, а узлы В, С ш D отвечают задачам, матрицы весов которых те же самые, что и матрица весов задачи А, но только ребрам (2,1), (2,6) или (2,5) соответственно приписан бесконечный вес.

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



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 [ 88 ] 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95