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

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.23),- несколько модифицированные, чтобы можно было решать обобщенные р-медианные задачи, возникающие на практике при размещении складов (пунктов обслуживания), -встречаются также в работах [29, 30, 15, 7, 28].

5.4. Приближенный алгоритм

Тэйтц и Барт [32] предложили эвристический метод для нахождения р-медианы. Метод состоит в следующем: случайным образом выбираются р вершин, они и образуют начальное множество S, аппроксимирующее р-медианное множество Хр. Затем выясняется, может ли некоторая вершина Xj X - S заменить вершину Xi 6 S (как медианная вершина), для чего строится новое множество S = (5 и {xj}) - {xi} и сравниваются передаточные числа о {S) и а {S). Если а {S) <аа (S), то вершина ж,- замещается вершиной Xj и из множества S получается множество S, которое лучше аппроксимирует р-медианное множество Хр. Затем исследуется уже множество S, аналогично тому как исследовалось 5 ИТ. д., пока не будет построено множество S, такое, что ни одну его вершину нельзя заместить вершиной из X - S ж получить при этом множество с меньшим передаточным числом, чем а (S). Множество S берется в качестве требуемого приближения к множеству Хр.

5.4.1. Описание алгоритма

Шаг 1. Выбрать некоторое множество 5 из р вершин в качестве начального приближения к р-медиане. Назовем все вершины Xj $ неопробованными .

Шаг 2. Взять произвольную неопробованную вершину и для каждой вершины Xi S вычислить приращение А,-;, соответствующее замене вершины Xi вершиной Х], т. е. вычислить

А,; = а (5) -О ((5 и {Xj)) - {Xi}). (6.24)

Шаг 3. Найти А,- =а max [А;;].

(i) Если Ajj- О, о назвать вершину Х) опробованной и перейти к шагу 2.

(ii) Если Ау> О, то 5 ч-(5 [J {xj}) - {х,} назвать вершину Х] опробованной и перейти к шагу 2.





Рис. 6.1. Контрпример к приближенному алгоритму разд. 5.4.

Шаг 4. Повторять шаги 2 и 3 до тех пор, пока все вершины из X - не будут опробованы. Эта процедура оформляется как цикл. Если при выполнении последнего цикла совсем не будет замещений вершин на шаге 3 (i), то перейти к шагу 5. В противном случае, т. е. если осуществлено некоторое замещение, назвать все вершины неопробованными и вернуться к шагу 2.

Шаг 5. Стоп. Текущее множество S является подходящей аппроксимацией р-медианного множества Хр.

Очевидно, что приведенный выше алгоритм не во всех случаях дает оптимальный ответ [18]. Действительно, рассмотрим неориентированный граф, изображенный на рис. 6.1. Числа, стоящие около ребер, равны соответствующим реберным стоимостям. Считаем, что все вершины имеют единичные веса. Если искать 2-медиану и в качестве начального множества S взять (хд, Xg) с передаточным числом ст (5) = 8, то никакое замещение только одной вершины не приводит к множеству с меньшим передаточным числом. Однако множество (хд, xJ не является 2-медианой данного графа. Существуют два 2-медианных множества: {xi, х4} и {xg, Хв} с передаточными числами А {Х^) = 7.

Алгоритм, описанный в настоящем разделе, является в действительности лишь одним из целого семейства алгоритмов, базирующихся на локальной оптимизации и на идее А-оптимальности, впервые введенной Лином [22] для задачи коммивояжера, а впоследствии развитой и использованной в других работах [3, 4, 19] при исследовании различных комбинаторных проблем.

Вернемся к нашей задаче. Множество S тия р вершин называется А-оптимальным {к-р), если замена любых % вершин из



множества S любыми к вершинами, не принадлежащими S, не может породить нового множества с передаточным числом, меньшим, чем у S. Очевидно, что если S является р-медианным множеством Хр рассматриваемого графа, то S р-оптимально. Совершенно очевидно также, что если S является А,-оптимальным множеством а S - Я-оптимальное множество, то а (S ) а {S) при к > к'.

Согласно приведенным выше определениям решение, полученное с помощью алгоритма из разд. 5.4.1, можно назвать 1-опти-мальным. Подобные алгоритмы можно дать и для порождения 2-оптимальных, 3-оптимальных и т. д. решений. Чтобы убедиться в Я-оптимальности множества S, нужно выполнить

I р\ п~р

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

6. Задачи

1 Доказать, что каково бы ни было множество Yp, состоящее из р точек, лежащих на ребрах или являющихся вершинами графа G, найдется хотя бы одно подмножество Хр cz X, удовлетворяющее условию: I Хр I = р и а {Хр) а (р).

2. Для графа, изображенного на рис. 6.2 найти медианы, 2-меДианы, 3-медианы и 4-медианы.

Рис. 6.2,



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