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

Величина Pj зависит только от мощности j группы g, а не от самой группы или от элементарной подгруппы {a}. То есть обозначение корректно. Для любой организации G = (V,E)Op (f) выполнено P(G) = hV \NG P(QG (h)) = hV \NG Ph, так как -QG (h) = {g,{a}} для некоторого {a} g.2 Таким образом, на стоимость последовательной организации влияют лишь величины P1,, PM -1, где M n - максимальная из мощностей групп набора f = { f1,, fm}: M = max( f1,, fm ). Все остальные значения функционала могут быть проигнорированы.

Итак, в случае функционала вида P( g1,, gk, g ) любая задача об оптимальной на Op (f ) последовательной организации произвольного набора групп f = { f1,, fm} однозначно определяется множествами f1,, fm и величинами P1,, PM -1.

Напомним, что F = 2N \ {} - множество всевозможных групп, то есть непустых подмножеств N.

Согласно замечаниям, сделанным в начале главы, рассматриваются последовательные организации без повторяющихся групп, следовательно любая неэлементарная группа h организуется из подгрупп g и {a}, {a} g.

Теорема 4.3. Для функционала вида P( g1,, gk, g ) задача об оптимальной на Op (f ) последовательной организации набора групп f = { f1,, fm} мощности три ( fi = 3) NP -полна для любых величин P1 > 0, P2 0.

Доказательство. Покажем принадлежность к классу NP. В оптимальной на Op (f ) организации элементы группы fi, i = 1, m организуются в некоторой последовательности (см. опр. 1.33).

Сгенерируем эту последовательность недетерминированной машиной Тьюринга для каждой fi. По известной последовательности элементов построим последовательную организацию Gi = (Vi, Ei ) Op ( fi ) каждой из групп fi. Затем построим последовательную организацию G набора f = { f1,, fm} с помощью объединения организаций для каждой из групп:

G = G1 Gm. При этом если группа g принадлежит как минимум двум графам, то есть g Vi, g V для i < j, то считаем, j что в G входит один экземпляр g, причем QG (g) = QGi (g), то есть в группу g в графе G входят такие же ребра, как и в одном из графов G1,,Gm. Очевидно, что стоимость любой организации, в которой все группы fi организуются в найденной последовательности, не менее P(G). То есть получили оптимальную на Op (f ) организацию. Очевидно, что сложность построения оптимальной организации по заданным последовательностям полиномиальна. Следовательно, задача решается недетерминированной машиной Тьюринга за полиномиальное время, то есть принадлежит классу NP.

Рассмотрим задачу о представителях в 2-множествах. Задано множество X = {x1,, xn} и двухэлементные подмножества Y1,,Ym X. Необходимо найти множество представителей Y X минимальной мощности, Y Yi 1 для i = 1, m.1 Задача о представителях в 2-множествах NP -полна [19]. Сведем ее к Фактически задача о представителях в 2-множествах представляет собой другую формулировку задачи о минимальном вершинном покрытии графа, то есть множестве вершин минимальной мощности, УзадевающемФ все ребра графа.

Формулировка задачи о представителях более удобна для доказательства.

поставленной в условии теоремы задаче, чем покажем ее NP -полноту.

Пусть Yi = {x, xki }, i = 1, m, 1 ji < ki n. Положим ji N = {a0, a1,, an}, fi = {a0, a, aki }, f = { f1,, fm}. Докажем, что ji множеству представителей минимальной мощности соответствует оптимальная на Op (f ) организация и наоборот. Для этого построим процедуры перехода от множества представителей к организации из Op (f ) и обратно.

a) Пусть задано множество представителей Y = {xl1,, xlq } X. Построим G = (V, E) Op (f ). Положим V = {{a0},{a1},,{an}, f1,, fm,{a0, al1},,{a0, alq }}. В E включим ребра для организации групп {a0, al1},,{a0, alq } из элементарных подгрупп. Для Yi = {x, xki } выполнено x Y или ji ji xki Y, следовательно {a0, a }V или {a0,aki }V. С помощью ji одной из этих подгрупп организуем fi, добавив в E соответствующие ребра. В результате по q -элементному множеству представителей построили последовательную организацию G групп f1,, fm стоимости qP1 + mP2.

b) Обратно, пусть задана последовательная организация G = (V, E) Op (f ). Тогда P(G) = qP1 + mP2, где q - число групп мощности два в G. Рассмотрим g = {as, at}V, 1 s < t n. Из g может выходить ребро лишь в f = {a0, as, at }. Удалим g, а f организуем из {a0,as} и {at }, добавив, если нужно, вершину {a0,as}. Продолжая такие действия, найдем последовательную организацию G = (V, E ) Op (f ), которая содержит q групп {a0, al1},,{a0, alq } мощности два, P(G ) = q P1 + mP2, q q.

Тогда рассмотрим Y ={xl1,, xlq} X. Для fi = {a0,a,aki } выполji нено {a0, a }V или {a0, aki }V. То есть существует 1 t q, ji для которого a = alt или aki = alt. Следовательно, x = xlt или ji ji xki = xlt. Тогда Yi Y 1 в силу Yi = {x, xki }. В результате по ji последовательной организации G групп f1,, fm стоимости qP + mP2 построили множество представителей из q q элементов.

Обозначим решение задачи об оптимальной на Op (f ) организации через G, P(G) = qP1 + mP2. После этого согласно пункту b) за полиномиальное время найдем множество представ ителей Y из q элементов, q q. Если бы существовало множес тво представителей из q < q элементов, то согласно пункту а) существовала бы последовательная организация G Op (f ), P(G ) = q P1 + mP2 < P(G) в силу P1 > 0, что противоречит оптимальности G. Итак, построили множество представителей Y минимальной мощности q = q. То есть, решив задачу об оптимальной на Op (f ) организации, за полиномиальное время решим задачу о представителях в 2-множествах. Теорема доказана.

Кратко идею доказательства теоремы можно пояснить следующим образом. В любую организацию G Op (f ) входят группы f1,, fm мощности три, то есть в стоимость P(G) входит величина mP2. Стоимость различных последовательных организаций из Op (f ) может изменяться за счет числа промежуточных групп мощности два. Построено соответствие, при котором каждая такая группа определяет элемент некоторого множества представителей и наоборот, что и показывает эквивалентность задачи о представителях в 2-множествах и задачи об оптимальной последовательной организации.

Итак, если P NP, то не существует полиномиального алгоритма решения задачи на Op (f ), даже если мощности всех групп набора f не превосходят трех. Следующие пункты посвящены модификации построенного в з1 алгоритма для функционалов вида P( g1,, gk, g ). Такая модификация позволяет снизить сложность, пользуясь особым видом функционала.

2. Узловые группы.

В данном пункте доказываются утверждения, позволяющие для функционала вида P( g1,, gk, g ) анализировать не все организации из Op (f ), а лишь организации, удовлетворяющие условиям утверждений 4.2 и 4.3. Опираясь на этот факт, в пункте модифицируется алгоритм решения задачи на Op (f ) для функционалов вида P( g1,, gk, g ).

Определение 4.5.Назовем узловыми группами группы множества U ={fi1 fik :1 k m, 1 i1 < ik m}\{{a1},,{an},}.

То есть под узловыми группами будем понимать неэлементарные группы, которые являются пересечением каких-либо групп набора f = { f1,, fm}. В частности, неэлементарные группы набора f принадлежат U. В примере (см. рис. 4.3) узловыми будут группы f1 = {a1, a2,a3}, f2 = {a2,a3, a4} и {a2, a3} = f1 f2.

Утверждение 4.2. Для функционала вида P( g1,, gk, g ) существует оптимальная на Op (f ) последовательная организация G, в которой любая вершина g с двумя или более выходящими ребрами ( RG (g) 2) является либо узловой, либо элементарной.

Доказательство. Пусть G = (V, E) - некоторая оптимальная на Op (f ) организация. Пусть из g V \ NG, g U выходят по крайней мере два ребра в h1 и l1, причем из g не существует пути ни в одну вершину, обладающую такими же свойствами. Через h1 - h2 - - hn1 обозначим путь из h1 в УближайшуюФ узловую группу hn1 U. Через l1 - l2 - - ln2 обозначим путь из l1 в УближайшуюФ узловую группу ln2 U. То есть единственными узловыми вершинами обоих путей будут последние вершины.

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

Из каждой вершины hi, i = 1,n1 -1, l, j = 1,n2 -1 выходит j ровно одно ребро по определению g. Рассмотрим группу g = hn1 ln2. Имеем g g, следовательно g неэлементарна.

Тогда g U и выполнено строгое вложение g g, так как g U.

Группы набора f не содержатся среди h1,, hn1-1, l1,,ln2-1.

Удалим эти вершины и инцидентные им ребра. Пусть g \ g = {ai1,,aik }. Добавим в G вершины g = g {ai1,, ai j }, j j = 1, k и ребра (g, g ), ({ai j }, g ), где g0 = g. Аналогично j-1 j j последовательным образом УдостроимФ g до hn1 и ln2. В результате получим последовательную организацию G Op (f ).

Пути h1 - h2 - - hn1 и l1 - l2 - - ln2 не имеют общих вершин, так как в противном случае общая вершина организовывалась бы из неэлементарных подгрупп, что противоречит определению последовательной организации. Вместо вершин h1,,hk и l1,,lk в G входят вершины g1,, gk такой же мощности. То есть P(G ) P(G). Мы не добавили в G ни одной неузловой вершины, из которой выходило бы более одного ребра.

Из g в G выходит на одно ребро меньше, чем в G. Проделываем вышеперечисленные действия до тех пор, пока из g не будет выходить одно ребро. В результате построим оптимальную на Op (f ) организацию, в которой число неузловых неэлементарных вершин с более чем одним выходящим ребром на одну меньше, чем в G. Продолжая такие действия, получим искомую оптимальную последовательную организацию. Утверждение доказано.

Утверждение 4.3. Для функционала вида P( g1,, gk, g ) существует оптимальная на Op (f ) организация G, удовлетворяющая утверждению 4.2 и следующим условиям:

a) если в G найдется путь из узловой вершины g1 в узловую вершину g2, не содержащий других узловых вершин, то в U не существует УпромежуточнойФ узловой группы g3 U, g1 g3 g2;

b) если в G узловой вершине g2 не подчинена никакая другая узловая вершина, то в U не существует УвложеннойФ узловой группы g3 U, g3 g2.

Доказательство. Рассмотрим оптимальную на Op (f ) организацию G = (V, E), для которой выполняются условия утверждения 4.2, и некоторый путь h1 - - hk в G, k 2, hk U, h1 U, h2,, hk -1 U. Каждая следующая вершина пути h1 - - hk представляет собой предыдущую, к которой добавлен некоторый элемент. Путь назовем неправильным, если в U существует группа g U, для которой h1 g hk. Также рассмотрим путь вида h1 = {al1},h2 = {al1al2 },, hk = {al1al2 alk } из элементарной вершины h1 в узловую вершину hk U, не содержащий других узловых вершин. Такой путь назовем неправильным, если в U существует группа g U, для которой g hk. В этом случае также выполнено h1 g hk.

Пусть h1 - - hk - неправильный путь. Тогда ему соответствует g U, h1 g hk. По утверждению 4.2 из каждой вершины h2,,hk -1 выходит ровно одно ребро в следующую вершину пути. Удалим вершины h2,,hk-1 из G. Пусть j g \ h1 = {ai1,,ais }. Добавим в G вершины h = h1 {ai1,, ai j }, j-j = 1, s, организовав hj из h и {aij }, где h0 = h1. Аналогично последовательным образом УдостроимФ g до hk. Получим новую организацию G Op (f ), причем P(G ) = P(G). Если неправилен путь из h1 в g, или из g в hk, то проделаем описанную процедуру для этих подпутей. И так далее. В итоге получим оптимальную на Op (f ) организацию, в которой любой подпуть пути из h1 в hk правилен. Следовательно, число неправильных путей по сравнению с G уменьшилось на единицу. Повторяя вышеописанные действия, получим оптимальную на Op (f ) организацию G*, в которой все пути правильны.

Рассмотрим в G* путь из узловой вершины g1 в узловую вершину g2, не содержащий других узловых вершин. Он правилен, следовательно в U не существует УпромежуточнойФ узловой группы g3 U, g1 g3 g2. То есть выполнено условие a).

Если в G* узловой вершине g2 не подчинена никакая другая узловая вершина, то существует путь вида h1 = {al1}, h2 = {al1al2 },, hk = {al1al2 alk } = g2, не содержащий других узловых вершин, кроме hk = g2. Путь правилен, следовательно в U не существует УвложеннойФ узловой группы g3 U, g3 g. То есть выполнено условие b). Утверждение доказано.

3. Модификация алгоритма для функционала вида P( g1,, gk, g ). Оценка сложности.

Для функционала вида P( g1,, gk, g ) приведем определение, аналогичное определениям 4.1 и 4.2 для функционала общего вида.

Определение 4.6. Графом задачи об оптимальной на Op (f ) последовательной организации для функционала вида ~ ~ ~ P( g1,, gk, g ) назовем ориентированный граф H = (VH, EH ):

~ ~ VH = U {}, ребро e = (g1, g2 ) принадлежит EH тогда и только ~ ~ тогда, когда g1, g2 VH, g1 g2 и не существует g3 VH, для ~ которой g1 g3 g2. Для любого ребра e = (g1, g2 ) EH положим (e) = Pg1 + Pg1 +1 + + Pg2 -1, где P0 = 0, P1,, Pn-1 - величины, введенные в пункте 1.

~ Таким образом, ребро в H идет из одной узловой группы gв другую узловую группу g2 при условии, что в U нет УпромежуточнойФ узловой группы g3: g1 g3 g2. Ребро из в g2 идет в том случае, если в g2 не вложены другие узловые группы. Стоимость ребра e = (g1, g2 ) равна стоимости последовательной УдостройкиФ g1 до g2. При этом порядок присоединения элементов при такой УдостройкеФ не влияет на стоимость, так как функционал имеет вид P( g1,, gk, g ).

~ В примере (см. рис. 4.3) в H будут входить узловые группы f1 = {a1,a2, a3}, f2 = {a2,a3,a4}, {a2,a3} = f1 f2 и вершина.

Граф задачи, который в общем случае изображен на рис. 4.3, значительно упрощается (см. рис. 4.5). В нем остаются только узловые вершины, а последовательность УдостройкиФ одной узловой вершины до другой не играет роли.

~ Задача об оптимальном поддереве в графе H определяется точно так же, как и задача об оптимальном поддереве в графе H ~ (см. опр. 4.3). То есть под поддеревом H подразумевается поддерево с корнем в, содержащее неэлементарные группы набора f = { f1,, fm}, листья которого содержатся среди групп набора f. Докажем теорему, аналогичную теореме 4.1.

{a1,a2,a3} {a2,a3,a4} P2 P {a2,a3} P ~ Рис. 4.5. Пример графа задачи H для функционала вида P( g1,, gk, g ).

Теорема 4.4. Для функционала вида P( g1,, gk, g ) задача об оптимальной последовательной организации эквивалентна~ задаче об оптимальном поддереве в графе задачи H.

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