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

Обозначим f = N = {a1,, an} и рассмотрим произвольное r -дерево D = (V, E) Dr ( f ). Для всех вершин g V \ ND проделаем следующую операцию. Пусть QD (g) = {g1,, gk }, k r. Сопоставим каждому из ребер (g1, g),Е,(gk, g) символ (букву) выходного алфавита, причем разным ребрам сопоставим разные символы. Полученное r -дерево будем называть помеченным (такие деревья описаны, например, в работе [42]).

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

Утверждение 2.2. Существует изоморфизм, при котором каждому префиксному коду соответствует одно и только одно помеченное r -дерево D Dr ( f ), причем длина li кодового слова wi равна длине пути из {ai} в f = {a1,, an} в соответствующем дереве.

Доказательство. Пусть задан некоторый префиксный код.

Построим соответствующее ему r -дерево D Dr ( f ). В корне r -дерева находится группа из всех символов входного алфавита, а в листьях - группы из одиночных символов. В каждую вершину r -дерева входит не более r ребер (r - число символов выходного алфавита). На первом шаге построения считаем, что дерево D состоит из одной изолированной вершины f. Построим множества g1,, gr следующим образом. В группу gi включим те символы a из f, для которых первая буква кодового слова wj j равна bi. То есть в первое множество включаем символы, кодовые слова которых начинаются с первой буквы выходного алфавита, во вторую - со второй, и так далее. Некоторые множества из g1,, gr могут быть пустыми (если нет слов, начинающихся на данную букву). Добавим в r -дерево D непустые группы gi и ребра (gi, f ), поставив в соответствие ребру (gi, f ) букву bi. В силу равенств f = g1 gr и gi g = получим, что f в D j организуется из непересекающихся подгрупп QD ( f ). Для добавленных подгрупп g проделаем то же самое, что и для f, только разбиение множества символов g проводим не по первой букве кодовых слов, а по второй. После этого в D добавятся новые группы, для них проводим разбиение по третьей букве кодовых слов и так далее. Подгруппы для g не добавляются (процесс прекращается), если хотя бы для одного символа ai g исчерпано кодовое слово wi. Покажем, что в результате действительно получим r -дерево D Dr ( f ).

Предположим, что на очередном шаге получили неэлементарную группу g и необходимо разбить ее на подгруппы по l -ой букве кодового слова. Процесс останавливается, если некоторому символу ai g соответствует кодовое слово wi с длиной, меньшей l, то есть li < l. В силу неэлементарности g существует символ a g, ai a. По предыдущим построениям j j первые l -1 букв в словах wi и wj совпадают, следовательно wi является началом слова wj, что противоречит префиксности кода.

То есть для всех ai g выполнено li l и разбиение по l -ой букве провести можно. Процесс может остановиться только на элементарной группе. Разбиение g может быть тривиальным, то есть содержать g и пустые группы, если все l -ые буквы совпадают (при этом в r -дереве D появятся повторяющиеся группы, в частности, если g = {ai} и конец слова wi еще не достигнут). В силу конечности кодовых слов через некоторое число шагов процесс закончится, причем будет ровно n начальных вершин {a1},,{an} (повторяться начальные группы не могут, так как по построению нет пересечений). По утверждению 1.D Dr ( f ), то есть является r -деревом организации группы f.

Обратно, рассмотрим произвольное помеченное дерево D Dr ( f ). Из каждой начальной вершины {ai} существует ровно один путь в f. Пройдем этот путь от конца к началу, последовательно выписывая буквы, соответствующие проходимым ребрам. Получим слово wi длины li, которая равна длине пути из {ai} в f. Если бы wi было началом слова wj, то путь из {a } в f содержал бы путь из {ai} в f, то есть вершина j {a } была бы подчинена {ai}, что невозможно. То есть получили j префиксный код w1,, wn. Утверждение доказано.

Для произвольных групп g1,, gk 2N \ {} определим структурный функционал стоимости следующим образом:

(2.1) P(g1,, gk ) = a g pi, i где g = g1 gk. То есть стоимость организации группы g равна сумме вероятностей появления тех символов, которые входят в g, независимо от подгрупп, из которых организуется g.

Тогда для любого r -дерева D = (V, E) D( f ) выполнено P(D) = gV \ND P(QD (g)) =gV \ND a g pi =p1l1 + + pnln, где i li - количество неначальных групп, в которые входит элемент ai, то есть длина пути из {ai} в f.

Таким образом, при функционале (2.1) стоимость P(D) r -дерева D, соответствующего префиксному коду, равна средней длине кодового слова. Следовательно, имея r -дерево минимальной стоимости на Dr ( f ) и пометив ребра некоторым образом, найдем оптимальный код, и обратно, имея оптимальный код, построим r -дерево D Dr ( f ) минимальной стоимости1. То есть задача об оптимальном дереве на Dr ( f ) с функционалом (2.1) эквивалентна задаче об оптимальном алфавитном коде с входным алфавитом f = {a1,, an}, набором вероятностей p1,, pn и выходным алфавитом {b1,,br }.

Процедуры построения дерева по коду и кода по дереву описаны в доказательстве утверждения 2.2.

На рис. 2.4 приведен пример оптимального префиксного кода с входным алфавитом {a, b, c,d}, вероятностями появления символов 0,4; 0,3; 0,2; 0,1 и выходным алфавитом {0,1}. Как видно из рисунка, длины путей (кодовых слов) равны 1, 2, 3, 3. Средняя длина пути, стоимость r -дерева и средняя длина кодового слова равны 1,9. Символу a, который встречается наиболее часто, соответствует кратчайшее кодовое слово 0. Остальным - более длинные кодовые слова. Если бы вероятности появления всех символов совпадали, то оптимальным было бы симметричное 2-дерево и все кодовые слова состояли бы из двух букв.

{a,b,c,d} a 0 {b,c,d} b 10 0 0 {c,d} c 110 0 d 111 {a} {b} {c} {d} Рис. 2.4. Оптимальный бинарный код и соответствующее 2-дерево.

Разработанные в главе III общие алгоритмы поиска оптимального r -дерева могут быть использованы для построения оптимальных кодов. Разумеется, в теории кодирования созданы гораздо более эффективные алгоритмы: для r = 2 - это алгоритм Хаффмана построения оптимального бинарного кода [48], для произвольного r 2 обобщение алгоритма Хаффмана описано, например, в [42]. Алгоритмы имеют порядок сложности n log n и позволяют, таким образом, решать задачи на Dr ( f ) для функционала (2.1).

Утверждение 2.3. Функционал (2.1) вогнут.

Доказательство. Рассмотрим набор групп {g1,, gk } и произвольное разбиение на поднаборы {h1,, hi} и {hi+1,,hk } (см. опр. 1.30), k 3, 1 < i < k. Обозначим g = g1 gk, h = h1 hi. Тогда g = h hi+1 hk, то есть P(g1,, gk ) = = a g pi = P(h,hi+1,, hk ). Следовательно, верно неравенство i P(g1,, gk ) P(h1,, hi ) + P(h,hi+1,, hk ). Утверждение доказано.

Таким образом, по следствию к теореме 1.6 оптимальным деревом на D( f ) будет веерная организация стоимости 1. Она же будет оптимальной на Dr ( f ) при r n, так как в этом тривиальном случае каждому символу входного алфавита соответствует слово из одной буквы выходного алфавита.

3. Оптимальная структура управления сетью доставки материальных потоков.

В различных работах (см., например, [10, 37]) приводится следующая задача1. Задана сеть доставки материальных потоков T = (N, ET ), то есть ориентированный граф с множеством вершин N и дуг ET, связывающий источники материальных потоков с потребителями через промежуточные точки ветвления. Каждая дуга (u,v) ET характеризуется потоком заявок частоты (u,v) на материальные потоки и величиной материального потока (u,v).Рассмотрим дерево D = (V, E) D( f ), где f = N. Для любой вершины h V \ ND частота заявок (h) и суммарный материальный поток (h), с которыми Уимеет делоФ центр, управляющий группой h, вычисляются следующим образом (см. [37]):

(h) = (h, N \ h) + (N \ h,h) + h \ h ), (h)(h, h QD (h) = (h, N \ h) + (N \ h,h) + ( h)(h, h \ h), h QD где для любых групп g, g, g g = через (g, g ) = =,v) и u g(,ug (g, g) = (u,v)ET g(v,gv) соответственно (u,v)ET,u v,u, обозначены поток заявок и материальный поток из группы g в группу g. Таким образом, через центр, управляющий группой h, проходит поток заявок из h во все остальные элементы N (первое слагаемое), из всех остальных элементов N в h (второе слагаемое) и потоки заявок между подгруппами из QD (h), которые непосредственно подчинены группе h (третье слагаемое). То же самое касается и материальных потоков. Общие потери (затраты), связанные с работой системы управления, определяются С точностью до обозначений.

Сеть представляет собой частный случай технологического графа (см. п.1), но функционал стоимости определяется по-другому.

следующим образом:

P(D) = N[ (h) ( (h),c(h)) + c(h)], hV \ D где c(h) - стимулирование работы центра, управляющего группой h, ( (h),c(h)) - доля материального потока, которая теряется изза ошибок в управлении.

При заданном стимулировании функционал P(D) структурен, так как для любой группы h V \ ND величины (h), (h), c(h) определяются только самой группой h и группами из QD (h), которые непосредственно подчинены h, то есть набором подчиненных групп. Таким образом, для поиска оптимальной структуры управления, то есть дерева D D( f ), минимизирующего потери P(D), можно использовать алгоритмы поиска оптимального дерева, разработанные в главе III. При этом неважно, какая сеть рассматривается - однопродуктовая или многопродуктовая, так как величины и могут быть как числами, так и векторами. В [37] отмечается, что задача в общем случае весьма сложна. В [10] для однопродуктовой сети и функции (,) специального вида рассмотрена комбинированная задача выбора стимулирования (правил функционирования) и структуры управления.

4. Оптимальная структура управления однородными элементами.

В работе [21] рассмотрена следующая задача. Задано множество N элементов нулевого уровня, n = N. Каждый элемент нулевого уровня должен быть связан с одним элементом первого уровня, в свою очередь элемент первого уровня - с одним элементом второго, и т.д. Элементы уровня l -1 связываются с единственным элементом уровня l. С каждым элементом уровня j связан, по крайней мере, один элемент уровня j -1. Обозначим через n количество элементов на j -ом уровне управления, j j = 0, n. Тогда 1 = nl nl-1 n1 n0 = n. Обозначим через x 1 количество элементов уровня j -1, которые подчинены ji i -му элементу уровня j, j = 1,l, i = 1,n, i=1,n x = n.

j ji j-j j Предполагается, что затраты K (x ) 01 на создание пункта ji управления зависят только от количества подчиненных x и от ji уровня j. То есть все элементы одного уровня предполагаются однородными, так что затраты зависят лишь от количества подчиненных элементов, но не от их состава. Задача построения оптимальной структуры управления заключается в поиске чисел l,n, x, которые удовлетворяют вышеуказанным ограничениям и j ji n l j минимизируют суммарную величину затрат K j (x ). При ji j=1 i=этом количество уровней не должно превосходить некоторой предельной величины: l L.

Очевидно, что рассматриваемые структуры представляют собой деревья из D( f ), где f = N. Длина пути из начальной вершины в f не должна превосходить L. Обозначим множество таких деревьев через DL ( f ) D( f ). Кроме того, накладывается ограничение на подчиненность: длина пути в вершину g из любой подчиненной начальной вершины {a} g одинакова и равна уровню g.2 Обозначим множество таких деревьев через D ( f ) DL ( f ). На множестве D ( f ) задан функционал L L стоимости дерева D = (V, E) D ( f ) : P(D) = L gV \ ND K j ( QD (g) ).

В общем случае функционал неструктурен, так как зависит не только от групп, непосредственно подчиненных группе g, но и от уровня j группы g, то есть от длины пути из начальной вершины в g. Таким образом, рассмотренная задача представляет собой задачу об оптимальной организации с неструктурным функционалом стоимости. Очевидно, что функционал P можно продолжить на DL ( f ) по вышеуказанной формуле. Тогда верно следующее утверждение.

1 j В работе [21] условие неотрицательности затрат K (x ) 0 явно не выписано, ji но подразумевается при построении методов решения.

То есть одной вершине не могут быть подчинены вершины разных уровней.

j Утверждение 2.4. Если для любого j выполнено K (1) = 0, то оптимальное на D ( f ) дерево будет оптимальным и на DL ( f ).

L Доказательство. Рассмотрим произвольное дерево D = (V, E) DL ( f ). Для произвольной вершины g V через l(g) обозначим длину максимального пути из подчиненных начальных вершин {a} g в g. Рассмотрим g V \ ND. Пусть QD (g) = {g1,, gk } и l = max(l(g1),,l(gk )). Если для некоторой вершины gi выполнено l(gi ) < l, то проделаем следующее.

Добавим в D q = l - l(gi ) экземпляров группы gi,1 обозначив их через gi,, giq. Удалим ребро (gi, g). Вместо него создадим цепь gi - g1 - - giq - g, то есть добавим ребра (gi, gi ), i (g1, gi2),Е,(giq-1, giq ), (giq, g). После этого для всех вершин i h QD (g) величина l(h) будет одинакова и равна l. Проделав такие преобразования для всех вершин g V \ ND, получим дерево D D ( f ), в котором длина пути в вершину g из любой L подчиненной начальной группы {a} g одинакова. В силу j K (1) = 0 такое преобразование не изменит стоимости. Тогда оптимальному на DL ( f ) дереву D* соответствует дерево D* D ( f ), для которого P(D*) = P(D*). В силу L D ( f ) DL( f ) дерево D* оптимально на D ( f ). Утверждение L L доказано.

Таким образом, решив задачу об оптимальном дереве на D ( f ), найдем решение и на DL ( f ). Обратно, решив задачу на L DL ( f ), преобразуем решение в оптимальное дерево на D ( f ) так, L как указано в доказательстве утверждения 2.4. То есть при j K (1) = 0 задачи на D ( f ) и DL ( f ) эквивалентны. В этом случае L разработанные в [21] методы могут быть использованы для решения задачи на DL ( f ) с неструктурным функционалом P (при достаточно большом L эти же методы решают задачу и на D( f )).

Множество V может содержать повторения, то есть добавляемые группы не отождествляются.

Поставленная задача в [21] называется однородной, если j функция затрат одинакова на всех уровнях: K () = K(). В этом случае функционал стоимости структурен. Разработанные в главе III общие алгоритмы поиска оптимального дерева на D( f ) могут быть модифицированы для решения задачи на DL ( f ) (см.

соответствующие сноски главы III). Тогда при K (1) = 0 общие алгоритмы позволяют решать однородную задачу. Но, разумеется, алгоритмы, разработанные в [21] для конкретного функционала стоимости, более эффективны.

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