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

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


Рис. 10.10. Кратчайшие остовы в процессе поиска, (а) Г* (А), вес 22. (б) Г* (В), вес 23. (в) Г* (С), вес 24. (г) Т* (D), вес 25-


гамильтонова негамиль- гамильтонова цель тоново цель дерево

Рис. 10.11. Поиск с деревом решений.

Найдем теперь кратчайшие остовы Т {В), Т {С) ъ Т (D), соответствующие узлам В, С ш D. Результаты изображены соответственно на рис. 10.10 (б), (в) и (г); веса этих остовов указаны вблизи узлов.

Остовы Т (В) и Т {D) являются гамильтоновыми цепями (все-dJ 2), в то время как Т (С) гамильтоновой цепью не является. Кратчайшим из этих двух остовов будет Т (В) с весом 23. Нижняя граница веса для окончательного ответа равна наименьшему из весов остовов Т (В), Т (С) и Т (D) и равна также 23. Таким



cji=Cji,-\-k, Л c\j = Cij-\-k, I

(10.10)

{для всех х^фх, Хг)

C2i = Сг} + к, ci2=Cj2-\-k, , cij = Cij-\-2k, {для всех Xj, Xj- = Xi, Xj) Cij = Ci/, {для всех Xj, Xj-rjiXj, Xj)

является решением задачи (б) с первоначальной матрицей весов.

Доказательство. Каждая гамильтонова цепь относится к одной из следующих категорий:

(1) Xi и Xj не совпадают ни с одной из ее концевых вершин;

(2) одной из ее концевых вершин является или Xi, или х^;

(3) одной концевой вершиной является Xj, а другой Xj. Вес гамильтоновой цепи с матрицей весов С больше веса этой же цепи с матрицей С на величину:

4к, если цепь относится к категории (1);

Зк, если цепь относится к категории (2);

2к, если цепь относится к категории (3).

Так как к превосходит вес любой гамильтоновой цепи, то вес (для матрицы С') самой длинной гамильтоновой цепи категории (3) меньше, чем вес самой короткой гамильтоновой цепи категории (2), а вес самой длинной гамильтоновой цепи категории (2) меньше, чем вес самой короткой цепи категории (1). Таким образом, решение задачи (а) с матрицей весов С даст кратчайшую

образом, Т {В) дает оптимальный ответ, т. е. является кратчайшей гамильтоновой цепью. Следует заметить, что в узле С не нужно производить дальнейшее ветвление, так как любая гамильтонова цепь, полученная при таком ветвлении будет иметь вес, не меньший чем 24.

Итак, алгоритм, используюш;ий дерево решений, позволил в этом частном примере получить оптимальный ответ, применяя алгоритм кратчайшего остова только 4 раза.

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

6.2.2. Решение задачи (б). В этой задаче надо найти кратчайшую гамильтонову цепь с двумя заданными концевыми вершинами Xi и х^. Эту задачу можно свести к задаче (а), используя следую-ш;ую теорему.

Теорема 2. Пусть С = [cг^J - матрица реберных весов первоначального графа G и к - достаточно большое положительное число, большее чем вес любой гамильтоновой цепи. Тогда решение задачи (а) с матрицей реберных весов С, где



гамильтонову цепь категории (3), т. е. она будет решением задачи (б) с матрицей весов С. Это доказывает теорему.

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

6.3. Алгоритм штрафования вершин

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

Теорема 3. Если матрица С преобразована в матрицу С так, что

cij = Cij + p{i) + p{}) для г, / = 1, 2, п, (10.11)

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

Доказательство. Пусть Fc-вес произвольной гамильтоновой цепи с матрицей С, имеющей концевые вершины х- п Xj. Так как каждая вершина соединена точно с двумя другими вершинами (за исключением концевых вершин, каждая из которых соединена только с одной другой вершиной), то вес Fc той же самой гамильтоновой цепи с матрицей С отличается от Fc на величину

Fc-Fc = 2 S р(/) + р(1) + р(2). (10.12)

jl, 2

Это постоянная величина, не зависящая от выбранной гамильтоновой цепи. Отсюда следует теорема.

6.3.1. Решение задачи (б). Применение алгоритма нахождения кратчайшей гамильтоновой цепи с указанными концевыми вершинами (задача (б)), основанного на теореме 3, будет продемонстрировано на примере.

Пример. Рассмотрим полный граф G с 10 вершинами, матрица весов Со которого дается табл. 10.1, и предположим, что мы хотим найти кратчайшую гамильтонову цепь с концевыми вершинами 8 и 9.



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