Книги по разным темам Pages:     | 1 |   ...   | 9 | 10 | 11 | 12 | 13 |   ...   | 26 |

G j В силу монотонности сложности для j = 1, k выполнено C C(gk ) < Ck+1. Поставим aik +1 на первое место, порядок j остальных элементов сохраним. Получим последовательную организацию G. При этом стоимость организации групп g2,, gk+1 изменится на стоимость организации соответствующих групп g2,, gk +1. То есть в P(G ) вместо величины P1 будет входить величина P2 = j=2,k +1 P(QG (gj )) = C1 + + Ck.

P(G) - P(G ) = P1 - P2 = C(gk ) - C1 0. В G k увеличилось по крайней мере на единицу, P(G ) P(G). Продолжая такие действия с G вместо G, в итоге придем к последовательной организации G*, для которой C(g ) C при j = 1, n -1. Таким j j+образом, для любой организации G Op ( f ) выполнено P(G) P(G*) = C2 + + Cn Pmin. Если на первом месте в последовательной организации стоит элемент с максимальной сложностью, то стоимость организации равна Pmin, то есть она оптимальна. Утверждение доказано.

В результате по поводу решения задачи об оптимальной организации одной группы f для функционала (I) можно сделать следующие выводы:

a. На Op ( f ) решением будет любая последовательная организация, в которой на первом месте стоит элемент максимальной сложности (см. утв. 2.7), то есть задача на этом множестве решена аналитически.

b. При 1, 1 и функции сложности вида (2.2) функционал существенно выпуклый (см. утв. 2.6). Тогда (см. теор. 1.8) ~ решение на Op ( f ) будет решением и на O( f ), O( f ), Or ( f ), ~ Or ( f ), то есть в силу пункта a) задача на этих множествах решена аналитически.

c. При 1 функционал выпуклый (см. утв. 2.6). С учетом монотонности решение на D2 ( f ) будет решением и на O( f ), ~ ~ O( f ), Or ( f ), Or ( f ) (см. следствие 2 к теор. 1.5), то есть задача на этих множествах решается с помощью алгоритмов поиска оптимального 2-дерева (см. гл. III).

d. При 1 функционал вогнут (см. утв. 2.6), следовательно (см.

теор. 1.6 и следствие) веерная организация оптимальна на O( f ) ~ и O( f ), то есть задача на этих множествах решена аналитически. В силу монотонности решение на Dr ( f ) будет решением и на Or ( f ) (см. следствие к теор. 1.4), то есть задача на этих множествах решается с помощью алгоритмов поиска оптимального r -дерева (см. гл. III).

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

По поводу решения задачи об оптимальной организации произвольного набора групп f = { f1,, fm} для функционала (I) можно сделать следующий вывод. При 1, 1 и функции сложности вида (2.2) функционал существенно выпуклый (см. утв.

2.6), следовательно (см. теор. 1.8) решение задачи на Op (f ) будет ~ ~ решением и на O(f ), O(f ), Or (f ), Or (f ), то есть задача на этих множествах решается с помощью алгоритмов поиска оптимальной последовательной организации (см. гл. IV).

На рис. 2.5 полученные результаты для функционала (I) и функции сложности вида (2.2) изображены схематично. По горизонтальной оси отложено значение, по вертикальной - значение. При 1 - область с вертикальной штриховкой - на O( f ) оптимальна веерная организация одной группы (функционал - вогнутый). При 1 - область с перекрестной штриховкой - на O(f ) оптимальна 2-организация произвольного набора групп f = { f1,, fm} (функционал - выпуклый). При 1, 1 - область с горизонтальной штриховкой - результат усиливается. В этом случае на O(f ) оптимальна последовательная организация.

Если набор f = { f } состоит из одной группы, то на O( f ) оптимальна последовательная организация, в которой на первом месте стоит элемент максимальной сложности, остальные расположены в любом порядке (правая часть графа в области с горизонтальной штриховкой).

Рис. 2.5. Оптимальные организации для функционала (I).

3. Вид оптимальной организации для функционала (II).

Утверждение 2.8. Функционал (II) при 1 вогнут, а при функции сложности вида (2.2) и > 1, 1 вогнут на наборах непересекающихся групп1.

Доказательство. Рассмотрим набор групп {g1,, gk } и его произвольное разбиение на поднаборы {h1,,hi} и {hi+1,,hk }, 1 < i < k, h = h1 hi. Обозначим через P1 левую, через P2 - правую часть в неравенствах определения 1.30. Обозначим X = C(h1) + + C(hi ), Y = C(hi+1) + + C(hk ), тогда P1 = (X + Y), P2 = X + (C(h) + Y ). При 1 в силу (2.4) P1 X + Y P2.

В случае >1, 1 можно подобрать пересекающиеся группы, при которых нарушается неравенство b) в опр. 1.30, а при <1, >1 можно подобрать и непересекающиеся группы, обладающие тем же свойством. То есть утверждение неулучшаемо.

Если среди h1,,hi нет пересекающихся групп и функция сложности имеет вид (2.2), то C(h) = (C(h1)1/ + + C(hi )1/ ).

При 1 в силу (2.3) C(h) X, следовательно P2 (X + Y ) = P1.

Утверждение доказано.

Утверждение 2.9. Последовательная организация, в которой элементы расположены в порядке неубывания сложности1, оптимальна на Op ( f ) при функционале (II) с функцией сложности вида (2.2) и параметрами 1 или > 1, 1.Доказательство. Рассмотрим оптимальную на Op ( f ) организацию G. В G элементы расположены в некотором порядке ai1,,ain. Обозначим g = {ai1,, ai j }, C = C({ai j }), j = 1, n.

j j Пусть для некоторого k Ck > Ck+1. Поменяем местами aik и aik +1.

Получим последовательную организацию G. Если k = 1, то P(G ) = P(G). Иначе в P(G) входила величина P1 = (C(gk -1) + Ck ) + (C(gk-1 {aik }) + Ck+1). Вместо P1 в P(G ) входит величина P2 = (C(gk-1) + Ck+1) + (C(gk-1 {aik +1}) + Ck ).

1/ Обозначим z = C(gk-1)1/, x = Ck, y = Ck/ 1. Тогда x > y, + P1 = (z + x ) + ((z + x) + y ), P2 = (z + y ) + ((z + y) + x ).

Первое слагаемое P2 не превосходит первого слагаемого P1.

Докажем, что при 1 для вторых слагаемых выполняется то же.

Для этого достаточно показать неотрицательность величины = (z + x) + y - (z + y) - x. Рассмотрим как функцию z.

Тогда (0) = 0, (z) = (z + x) -1 - (z + y) -1. При 1 с учетом x > y имеем (z) 0. Следовательно, (z) монотонно не убывает. Имеем (z) 0, то есть P2 P1.

Остался случай < 1, 1. Для доказательства неравенства P1 P2 рассмотрим разность этих величин как функцию от y и покажем ее неотрицательность:

См опр. 1.33.

При <1, >1 можно привести пример, при котором утверждение неверно. То есть оно неулучшаемо.

(y) = (z + x ) - (z + y ) + ((z + x) + y ) - ((z + y) + x ) Вычислим производную: ( y) = (-(z + y ) -1 y -1 + + ((z + x) + y ) -1 y -1 - ((z + y) + x ) -1(z + y) -1). Первое слагаемое по модулю не меньше второго в силу z + y < (z + x) + y и условия 1. Следовательно, ( y) 0.

Выполнено (0) > 0, (x) = 0, то есть функция (y) монотонно убывает до нуля при увеличении y от нуля до x. Имеем (y) 0, то есть P2 P1.

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

В результате по поводу решения задачи об оптимальной организации одной группы f для функционала (II) можно сделать следующие выводы:

a. На Op ( f ) при функции сложности вида (2.2) и 1 или >1, 1 решением будет последовательная организация, в которой элементы расположены в порядке неубывания сложности (см.

утв. 2.9), то есть задача на этом множестве решена аналитически.

b. При 1 или при функции сложности вида (2.2) и > 1, функционал вогнут (см. утв. 2.8), следовательно в силу монотонности (см. теор. 1.6 и следствие) веерная организация ~ оптимальна на O( f ), O( f ), то есть задача на этих множествах решена аналитически.

c. В силу монотонности решение на D( f ) и Dr ( f ) будет соответственно решением на O( f ) и Or ( f ) (см. теор. 1.4 и следствие), то есть задача на этих множествах решается с помощью алгоритмов поиска оптимальных деревьев (см. гл.III).

d. При функции сложности вида (2.2) и = 1, = 1 функционал (II) совпадает с функционалом (2.1) (см. п.2 з1), если положить C(ai ) = pi. Условие i=1,n pi = 1 не ограничивает общности, так как (II) однороден (см. опр. 2.3) и решение задачи об оптимальной иерархии не зависит от масштаба сложностей. То есть при произвольных сложностях элементов можно положить pi = C(ai ) /(C(a1) + + C(an )). Таким образом, функционал (II) описывает, в частности, алфавитное кодирование. В силу монотонности решение на Dr ( f ) будет решением и на Or ( f ), то есть задача на этих множествах решается с помощью алгоритмов теории кодирования со сложностью порядка n log n (см. п.2 з1). Априори представляется разумным использовать эти алгоритмы и в качестве эвристических при 1 или 1.

Рис. 2.6. Оптимальная организация для функционала (II).

На рис. 2.6 полученные результаты для функционала (II) и функции сложности вида (2.2) изображены схематично. По горизонтальной оси отложено значение, по вертикальной - значение. В случае 1 или > 1, 1 - область с вертикальной штриховкой - на O( f ) оптимальна веерная организация одной группы (функционал - вогнутый). В этой же области на Op ( f ) оптимальна последовательная организация, в которой элементы расположены в порядке неубывания сложности (от УменьшегоФ к УбольшемуФ). При < 1, > 1 - белая область - функционал не является ни выпуклым, ни вогнутым1.

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

4. Вид оптимальной организации для функционала (III).

Утверждение 2.10. Функционал (III) - существенно выпуклый при 1. Доказательство. Сначала докажем выпуклость. Рассмотрим произвольный набор групп {g1,, gk }, k 3 и его разбиение на поднаборы {h1, h2} = {g1, g2}, {h3,,hk } = {g3,, gk }. Без ограничения общности считаем C(g1) = max(C(g1),,C(gk )).Обозначим h = h1 h2; x = C(g1 gk ) ; y = C(h); z = C(h1).

Сложность монотонна, следовательно z y x. Через Pобозначим левую, через P2 - правую часть в неравенствах определения 1.30. Тогда P1 = (x / z -1), P2 = (y / z -1) + + (x / y -1) (y / z -1+ x / y -1) в силу (2.3) и 1.4 Для доказательства неравенства P2 P1 достаточно показать, что:

x / z -1- y / z +1- x / y +1 = (xy + yz - y2 - xz) / yz = (x - y)(y - z)/ yz 0, что, очевидно, верно. Таким образом, функционал (III) - выпуклый.

Рассмотрим набор неэлементарных групп {g1, g2}. Пусть C(g1) C(g2 ). Обозначим x = C(g1 g2 ), z = C(g2 ), P1 и P2 - Можно подобрать сложности, при которых нарушаются оба неравенства в опр.

1.30.

При <1 можно подобрать сложности, при которых нарушается неравенство а) в опр. 1.30. То есть утверждение неулучшаемо.

Иначе можно изменить нумерацию групп g1,, gk.

При z = 0 P1 = + по определению функционала (III), следовательно выполнено неравенство P1 P2. Далее считаем z > 0.

соответственно левая и правая части неравенства a) определения 1.32. Имеем P1 = P(g1, g2 ) = (x / z -1). Рассмотрим a g1, тогда P2 =P(g1 \{a},g2)+P((g1 \{a})g2,{a}). Обозначим y =C((g1 \{a})g2), тогда P2 = ( y / z -1) + (x / y -1). Выше было показано, что P1 P2 при z y x, что выполнено в силу монотонности функции сложности. В случае C(g1) C(g2 ) выполнение неравенства b) определения 1.32 доказывается аналогично с точностью до замены g1 на g2. Следовательно, функционал (III) - существенно выпуклый. Утверждение доказано.

Докажем две вспомогательные леммы и утверждение 2.11 с целью выяснения вопроса об оптимальной на Op ( f ) последовательной организации одной группы для функционала (III).

емма 2.2. При функционале (III) с функцией сложности вида (2.2) существует оптимальная на Op ( f ) последовательная организация одной группы f, в которой элементы расположены в таком порядке ai*,, ai*,1 что при k = 1,n -1 выполнено 1 n C({ai* }) C({ai*,, ai* }).

k +1 1 k Доказательство. Пусть G Op ( f ) - оптимальная на Op ( f ) организация с порядком элементов ai1,,ain. Обозначим g = {ai1,, ai j }, y = C(g ), C = C({ai j }), j =1,n. Найдем j j j j минимальное k, для которого yk < Ck+1. Если такого k нет, то G - искомая организация. Иначе для j = 1,k -1 выполнено y C.

j j+/ Обозначим x =C1+ 1. В P(G) входит величина P = j=2,k+1P(Q (gj))= k 1 G = (y2 / y1 -1) + (y3 / y2 -1) + + (yk / yk -1 -1) + ((x + y1/ ) / x -1).

k Переставим элемент aik +1 на первое место, порядок остальных сохраним. Получим последовательную организацию G. С учетом монотонности сложности выполнено Ck +1 > yk y C для j j См. опр. 1.33.

j = 1,k. Следовательно, вместо P1 в P(G ) входит следующая 1/ 1/ величина: P2 = ((x + y1 ) / x -1) + ((x + y1/ ) /(x + y1 ) -1) + + + ((x + y1/ ) /(x + y1/ 1 ) -1).

k k Покажем, что P2 P1 индукцией по k. При k =1 выполнено P2 = P1. Обозначим P1 и P2 при k = q через P1(q) и P2 (q).

Предположим, что выполнено P2 (q) P1(q). Докажем, что P2 (q +1) P1(q +1). Можно записать P2(q +1) = P2(q) + + ((x + y1/ 1) /(x + y1/ ) -1), P(q +1) = P(q) +((x + y1/ 1) / x -1) - q+ q 1 1 q+ - ((x + y1/ ) / x -1) + ( yq+1 / yq -1). Обозначим y = y1/ 1, q q+ z = y1/, тогда выполнено z y.1 Необходимо показать:

q ((x + y) /(x + z) -1) ((x + y) / x -1) - ((x + z) / x -1) + ( y / z -1), ((x + z) / x -1) + ((x + y) /(x + z) -1) ((x + y) / x -1) + ( y / z -1).

Первое слагаемое слева не превосходит первого справа в силу z y. Неравенство для вторых слагаемых можно записать следующим образом (x + y) /(x + z) y / z. Упростим выражение:

xz + yz xy + zy, что выполнено в силу z y.

Итак, P2 P1, следовательно G оптимальна на Op ( f ).

Рассмотрим G вместо G. Тогда y C при j = 1,k. Повторяя j j+ при необходимости вышеуказанные действия с числом k > k, в итоге придем в искомой организации. Лемма доказана.

Лемма 2.3. Для произвольных величин 1 u v при 1 и 12 выполнено неравенство:

(u -1) + ((1 + (v -1) / u) -1) (v -1) + ((1+ (u -1) / v) -1).

Доказательство. Рассмотрим разность правой и левой частей как функцию от u : f (u) = (v -1) - (u -1) + + ((1+ (u -1) / v) -1) - ((1+ (v -1) / u) -1). Тогда выполнено f (1) = f (v) = 0. Докажем вогнутость функции f (u), то есть При z = 0 последнее слагаемое P1 равно + по определению функционала (III), следовательно выполнено неравенство P1 P2. Ниже считаем z > 0.

Pages:     | 1 |   ...   | 9 | 10 | 11 | 12 | 13 |   ...   | 26 |    Книги по разным темам