Книги по разным темам Pages:     | 1 |   ...   | 17 | 18 | 19 | 20 | 21 |   ...   | 26 |

Количество ребер H, за исключением ребер вида (,{a}), можно вычислить следующим образом: n(n -1)/ 2 + i=2,nCi (n -i) = n = n(2n-1 - (n +1) / 2) (последнее равенство получено с учетом i i соотношения iCn = nCn-1). То есть алгоритм должен -анализировать не менее n(2n-1 - (n +1) / 2) значений функционала.

Алгоритм, который решает задачу, анализируя стоимости всех ребер, кроме ребер вида (,{a}), строится очевидным образом.

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

Следствие 2 дает алгоритм решения задачи об оптимальной на Op ( f ) последовательной организации одной группы, требующий n(2n-1 - (n +1) / 2) вычислений функционала стоимости, и показывает, что более эффективного алгоритма не существует.

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

2. Нормализация графа задачи.

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

Определение 4.4. Нормализованным графом задачи H = (Vnorm, Enorm ) назовем граф, который получается из графа norm задачи H = (VH, EH ) в результате следующей процедуры. Пусть g VH, k = R(g) 3, R(g) = {g1,, gk }, где через R(g) обозначено множество вершин, в которые идут ребра из g в графе H. Удалим ребра (g, gi ), i = 1,k. Добавим k1 = +1) / (k вершин, обозначив их g1,, g11, и ребра (g1(i+1) / 2, gi ), i = 1,k, вес которых k равен весу удаленных ребер (g, gi ). Если k1 3, то добавим 2 k2 = +1) / 2 вершин, обозначив их g1,, gk2, и ребра (k (g(i+1) / 2, g1,), i = 1,k1 нулевого веса. И так далее, на очередном i q q q q шаге добавим две вершины g1, g2 и ребра (g, g1 ), (g, g2 ) нулевого веса. Проделав такие шаги для всех g VH, R(g) 3, придем к графу H, из вершин которого выходит не более двух norm ребер. Для H = (Vnorm, Enorm ) определим задачу об norm оптимальном поддереве аналогично определению 4.3.

Рис. 4.2. Приведение к нормализованному графу задачи.

Описанное перестроение для k = 2q+1 изображено на рис. 4.2.

Суть его состоит в следующем. УВилкуФ из k 3 ребер, выходящих из g, мы заменяем на УвилкуФ из двух ребер, идущих в дополнительные вершины, из которых в свою очередь выходит не более двух ребер, и так далее, в итоге УдойдемФ до вершин g1,, gk, в которые в первоначальном графе шли ребра из g. То есть каждое ребро (g, gi ), i = 1,k заменилось на некоторый путь из g в gi, проходящий через добавленные вершины. Причем вес пути равен весу первоначального ребра (g, gi ).

Утверждение 4.1. Задача об оптимальном поддереве в H эквивалентна задаче об оптимальном поддереве в нормализованном графе задачи H.

norm Доказательство. Рассмотрим поддерево D = (VD, ED ) графа H = (VH, EH ). Построим поддерево D = (VD, ED ) графа H = (Vnorm, Enorm ). Добавим в VD все вершины из VD. Для norm g VD, R(g) 2 добавим в ED выходящие из g ребра. Рассмотрим g VD, R(g) = {g1,, gk }, k 3. Тогда в H есть вершины norm g1j,, gkjj, j = 1,q (см. опр. 4.4). Пусть в поддереве D из g выход ят l k ребер в gi1,, gil. Добавим в VD вершины g1(is +1) / 2, а в ED ребра (g1(is +1) / 2, gis ), s = 1,l. Для добавленных вершин добав им ведущие в них в графе H ребра 1 и соответствующие верnorm шины, и так далее, пока не добавим идущие из g ребра. Получим поддерево D графа H, причем по построению (D ) = (D).

norm Обратно, рассмотрим поддерево D = (VD, ED ) графа H.

norm Построим поддерево D = (VD, ED ) графа H. Добавим в VD все вершины из VD VH. Для g VD VH, R(g) 2 добавим в D ребра, выходящие из g в D. Для g VD VH, R(g) = {g1,, gk }, k 3 некоторые 0 l k вершин gi1,, gil принадлежат VD.

Тогда добавим в ED ребра (g, gis ), s = 1,l. Получим поддерево D графа H, причем по построению (D ) = (D).

Итак, каждому поддереву H соответствует поддерево H norm такого же веса и наоборот, что и доказывает утверждение.

В каждую такую вершину ведет ровно одно ребро по построению H.

norm 3. Построение алгоритма. Оценка сложности.

Доказательство следующей теоремы представляет собой алгоритм решения задачи об оптимальном поддереве в нормализованном графе H = (Vnorm, Enorm ). Как и для графа norm задачи H, через R(g) будем обозначать вершины H, в norm которые идут ребра из g Vnorm.

Теорема 4.2. Существует алгоритм, решающий задачу об оптимальном поддереве в H = (Vnorm, Enorm ) путем сравнения norm менее V2 (Hnorm )3m весов различных поддеревьев, где V2 (H ) = {g Vnorm : R(g) = 2} - число вершин H, из norm norm которых выходит ровно два ребра.

Доказательство. Искомое поддерево должно содержать все группы набора f = { f1,, fm}. Обозначим L = 2f \ {}. То есть L - множество непустых поднаборов набора { f1,, fm}. Поднаборы будем обозначать через s L. Рассмотрим s L и g Vnorm. Через (g,s) обозначим минимальный вес поддерева графа H с norm корнем в g, которое содержит все вершины набора s, листья которого содержатся среди вершин s. Если соответствующего дерева не существует, положим (g,s) = +.

Пусть R(g) = 0, то есть из g ребер не выходит. Если g f, то (g,s) = + для любого s L. Если g f, то (g,{g}) = 0, (g,s) = + для любого s {g}.

Пусть R(g) = 1, то есть из g выходит одно ребро e = (g, h).

Если g f, то для любого s L имеем (g,s) = (h,s) + (e).

Соответствующее (g,s) поддерево строится как объединение ребра e и поддерева веса (h,s). Если g f, то для любого s L, g s имеем (g,s) = (h,s) + (e); а для любого s L, g s, s {g} имеем (g,s) = (h,s\{g}) + (e), так как g уже содержится в корне дерева. Для оставшегося случая s = {g} имеем (g,{g}) = 0.

Пусть R(g) = 2, то есть из g выходит два ребра e1 = (g,h1) и e2 = (g, h2 ). Рассмотрим s L. В поддереве, соответствующем величине (g,s), некоторый набор s1 s содержится в поддереве с корнем в h1, набор s2 = s \ s1 (или s2 = s \ (s1 {g}), если g s ) содержится в поддереве с корнем в h2. Если s1, s2, то (g,s) = (h1,s1) + (e1) + (h2,s2 ) + (e2 ). Если s1 =, s2, то (g,s) = (h2,s2 ) + (e2 ). Если s1, s2 =, то (g,s) = (h1,s1) + (e1). Если s1 =, s2 =, то s = {g} и s (g,s) = (g,{g}) = 0. Сравнив не более 2 вариантов разбиения s на s1 и s2, найдем минимальное значение (g,s). Для всех s L сравним не более i=1,mCi 2i < 3m вариантов.

m Для вершин, из которых ребра не выходят, для любого s L известны (g,s) и соответствующие поддеревья. Будем говорить, что для таких вершин задача о поддеревьях решена. В силу ацикличности H найдется g Vnorm, такая что ребра из g идут norm в вершины, для которых задача о поддеревьях решена. Тогда решим задачу для g, что потребует менее 3m сравнений весов поддеревьев. И так далее, в итоге решим задачу для всех вершин g Vnorm. Тогда (,f ) и соответствующее поддерево являются искомыми, что и доказывает теорему.

Следствие 1.1 Для структурного функционала общего вида существует алгоритм, решающий задачу об оптимальной последовательной организации путем сравнения менее (n +1)2n3m весов поддеревьев графа H = (Vnorm, Enorm ).

norm Доказательство. Для любой вершины g VH графа задачи H = (VH, EH ), k = R(g) 3 добавим в H не более 2k вершин norm (см. опр. 4.4). Из вершины мощности i в H выходит n - i ребер, i = 2, n - 3.2 Для всех вершин мощности i добавим в H не norm i более 2Cn (n - i) вершин. Из вершины {a }, j = 1,n -1 графа H j выходит n - j ребер. Для всех вершин мощности один добавим в H не более j=1,n-12(n - j) вершин. Для вершины добавим norm в H не более 2n вершин. Всего добавим вершин не более norm i=2,n-32Ci (n - i) + j=1,n-12(n - j) + 2n. С учетом равенства n Следствие 2 будет доказано ниже в пункте 3 з2.

Из вершин мощности n - 2 и n - 1 выходит не более двух ребер, следовательно для них дополнительные вершины в H не добавляются.

norm i i iCn = nCn-1, оценим последнее выражение величиной n2n. Так как -VH = 2n, то V2(Hnorm) Vnorm (n +1)2n, что и доказывает следствие.

Доказательство теоремы 4.2 дает алгоритм поиска оптимальной на Op (f ) последовательной организации произвольного набора групп f для структурного функционала общего вида. Пример найденной алгоритмом оптимальной организации приведен на рис. 5.3.

Следствие 1 дает верхнюю оценку сложности в худшем случае. Вершины графов H и H, которые не вложены ни в norm одну из групп набора f = { f1,, fm}, не могут входить ни в одно поддерево, так как все листья поддерева содержатся среди групп набора f. Таким образом, при поиске оптимального поддерева можно рассматривать не весь граф H, а только те его norm вершины, которые вложены хотя бы в одну из групп набора f. С учетом этой оговорки, оценим сложность в среднем следующим образом.

m \ n 45 6 2 78153 331 2 73724 101235 4 425710 1 104 5 17131 378263 6 3 0004 127 6 404 16 51054 766304 8 21 97529 949 40 149 76 173149 033424 10 186 598255 754 317 294 577 674837 763 1 576 12 - 2 232 954 2 799 913 4 729 690 6 465 469 8 650 14 - 19 327 169 24 272 855 39 182 355 55 710 417 71 441 16 - 172 996 106 217 376 355 346 835 503 479 629 550 615 392 18 - 1 551 740 086 1 942 858 319 3 114 855 925 4 317 150 636 5 466 045 20 - 13 952 535 549 17 446 863 109 28 016 474 70638 502 846 30748 954 320 Таблица 4.1. Оценка сложности алгоритма в среднем.

Сгенерируем случайным образом набор групп. Каждый элемент входит в группу с вероятностью 0,5. Вычислим количество вершин графа H, из которых выходит два ребра и norm которые вложены хотя бы в одну из групп набора f. По теореме 4.2 оценим сложность в среднем по 100 тестам. Результат приведен в таблице 4.1. В строках приведены значения для различных m от 2 до 20. В столбцах - для различных n от 4 до 15.

Если m, n 15, то сложность остается приемлемой.

Рассмотрим пример, поясняющий материал данного параграфа. Решим задачу об оптимальной на Op (f ) последовательной организации набора f = { f1, f2} из двух групп f1 = {a1, a2, a3} и f2 = {a2, a3, a4}. Имеем N = f1 f2 = {a1, a2, a3, a4}. Построим граф задачи H (см. опр. 4.1). При этом ни в одно из поддеревьев H не входят группы, содержащие элементы a1 и a4, так как такие группы не являются подмножествами ни f1, ни f2. Интересующая нас часть графа H изображена на рис. 4.3.

{a1,a2,a3} {a2,a3,a4} {a1,a2} {a1,a3} {a2,a3} {a2,a4} {a3,a4} {a1} {a2} {a3} {a4} Рис. 4.3. Пример графа задачи H.

Согласно теореме 4.1, имея оптимальное поддерево H с корнем в и листьями в f1 и f2, построим соответствующую ему оптимальную последовательную организацию. Предположим, что веса всех ребер, кроме нижних, равны единице (все значения функционала равны единице). Тогда вес поддерева равен числу входящих в него ребер, не считая нижних. Очевидно, что в любое поддерево входят не менее трех таких ребер. В поддерево D = (VD, ED ) с множеством вершин VD = {,{a2},{a2,a3}, f1, f2} входят ровно три таких ребра, то есть оно оптимально. Вес D равен трем ( (D) = 3). Построим соответствующую оптимальную организацию G такой же стоимости2. Граф G содержит единственную промежуточную вершину {a2, a3}, которая используется как для организации f1, так и для организации f2 (см. рис. 4.4).

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

Процедура построения последовательной организации по поддереву графа задачи H описана в доказательстве теоремы 4.1.

{a1, a2, a3} {a2,a3,a4} {a2, a3} {a1} {a2} {a3} {a4} Рис. 4.4. Оптимальная последовательная организация.

В общем случае оптимальное поддерево H строится с помощью нормализации графа. В примере на рис. 4.3 только из вершины выходит более двух ребер. Следовательно, при нормализации будут добавлены две вершины g1 и g1, в которые будут идти ребра из. Из g1 будут идти два ребра в {a1} и {a2}, из g1 - два ребра в {a3} и {a4} (см. опр. 4.4). По утверждению 4. поддереву D в H соответствует одно и только одно поддерево D в H такой же стоимости (например, если ребро (,{a1}) входит norm 1 в D, то вместо него в D входит путь (, g1), (g1,{a1}) и наоборот).

Задачу об оптимальном поддереве в H решает алгоритм norm теоремы 4.2. Поясним его на примере. Имеем L = 2f \{} = = {{ f1},{ f2},{ f1, f2}}. Для вершин f1 и f2, из которых не выходит ребер (см. рис. 4.3), задача о поддеревьях решена: ( f1,{ f1}) = 0, ( f2,{ f2}) = 0, остальные значения равны +, так как поддеревом с корнем f1 можно покрыть только вершину f1 (то же верно и для f2). Решим задачу о поддеревьях с корнем в {a2, a3}. Найдем ({a2,a3},{ f1, f2}) следующим образом. Из {a2, a3} выходят два ребра в вершины f1 и f2. Часть набора { f1, f2} должна покрываться деревом с корнем f1, оставшаяся часть - деревом с корнем f2. Очевидно, что единственный вариант разбиения { f1, f2}, стоимость которого не равна +, использует поддеревья, соответствующие величинам ( f1,{ f1}) и ( f2,{ f2}). То есть ({a2,a3},{ f1, f2}) = ( f1,{ f1}) +1+ ( f2,{ f2}) +1 = 2 (стоимости ребер равны единице). Аналогичным образом найдем ({a2,a3},{ f1}) = 1 и ({a2, a3},{ f2}) = 1. После этого задача о поддеревьях для {a2, a3} будет решена. Для остальных вершин H задача о поддеревьях решается аналогично.

norm з2. Оценка сложности задачи при функционале вида P( g1,, gk, g ). Алгоритм решения.

1. NP -полнота задачи.

В случае функционала вида P( g1,, gk, g ) оценим объем начальных данных задачи об оптимальной на Op (f ) последовательной организации произвольного набора групп f = { f1,, fm}. Во-первых, начальными данными будут сами множества fi N, i = 1, m, где N = {a1,,an} - множество элементов. Во-вторых, значения функционала. Для оценки их количества введем следующее обозначение.

Для j = 1, n -1 через Pj обозначим стоимость организации подгруппы g F мощности j с элементарной подгруппой {a} g, не входящей в g : Pj = P(g,{a}) = P( g, {a}, g {a}) = = P( j,1, j +1).

Pages:     | 1 |   ...   | 17 | 18 | 19 | 20 | 21 |   ...   | 26 |    Книги по разным темам