Главная страница
Навигация по странице:

  • Приложение

  • Доказательство теоремы 1.

  • Доказательство теоремы 2.

  • Сбалансированные деревья - Губко М.В.. 1 сбалансированные деревья


    Скачать 233.1 Kb.
    Название1 сбалансированные деревья
    АнкорСбалансированные деревья - Губко М.В..pdf
    Дата04.05.2017
    Размер233.1 Kb.
    Формат файлаpdf
    Имя файлаСбалансированные деревья - Губко М.В..pdf
    ТипЗадача
    #2072
    КатегорияЭкономика. Финансы

    1
    СБАЛАНСИРОВАННЫЕ
    ДЕРЕВЬЯ
    Губко М.В., к.т.н.
    (Институт проблем управления РАН, Москва)
    mgoubko@mail.ru
    Введение
    В настоящей статье рассматривается задача построения опти- мальной иерархической структуры над заданным множеством конечных исполнителей. Подобные задачи возникают при построе- нии оптимальной организационной структуры, а также при разра- ботке схем организации параллельных вычислений.
    В статье вводится понятие сбалансированного дерева и пока- зывается, что оптимальная иерархия представляет собой сбаланси- рованное дерево одного из двух типов.
    1.
    Постановка
    задачи
    и
    общие
    закономерности
    Рассмотрим задачу построения оптимальной иерархии над не- которым конечным множеством исполнителей
    }
    ,...,
    1
    {
    n
    N
    =
    Иерархия состоит из множества менеджеров
    }
    ,...,
    {
    1
    q
    v
    v
    M
    =
    , каждый из которых контролирует некоторое множество исполните- лей и/или других менеджеров.
    Группой исполнителей
    N
    s
    Í
    назовем любое непустое под- множество множества исполнителей. Множество исполнителей, которыми непосредственно или через цепочку своих подчиненных управляет менеджер v из иерархии H, назовем подчиненной группой
    исполнителей и обозначим
    N
    v
    s
    H
    Í
    )
    (
    В иерархии должен присутствовать топ-менеджер, который контролирует группу N из всех исполнителей.
    Более формально определение иерархии выглядит так:
    Определение 1 [1]. Ориентированный граф
    )
    ,
    (
    E
    M
    N
    H
    È
    =
    с множеством ребер подчиненности
    M
    M
    N
    E
    ´
    È
    Í
    )
    (
    назовем ие-
    2
    рархией, управляющей множеством исполнителей N, если граф H ацикличен, любой менеджер имеет подчиненных и найдется ме- неджер, которому подчинены все исполнители. Через
    )
    (N
    W
    обо- значим множество всех иерархий.
    Если множество исполнителей считается заданным, то количе- ство менеджеров в разных иерархиях может отличаться.
    Далее будем считать, что каждый исполнитель характеризует- ся своей мерой – положительным числом
    i
    m
    ,
    N
    i
    Î
    . Содержатель- но, мера исполнителя означает сложность управления им, которая может зависеть от сложности работы, выполняемой данным испол- нителем или от его индивидуальных качеств.
    Содержание менеджеров иерархии требует затрат. Таким обра- зом, каждой иерархии
    )
    (N
    H
    W
    Î
    можно поставить в соответствие неотрицательное число – стоимость иерархии. Оптимальной
    иерархией, управляющий множеством исполнителей N, называется иерархия из
    )
    (N
    W
    , имеющая минимальную стоимость.
    Далее предполагается, что стоимость иерархии
    )
    (H
    C
    склады- вается из стоимостей менеджеров этой иерархии, то есть
    å
    =
    =
    m
    i
    i
    v
    c
    H
    C
    1
    )
    (
    )
    (
    , а стоимость произвольного менеджера
    M
    v
    Î
    можно записать в виде
    ))
    (
    (
    ))
    (
    (
    )
    (
    2 1
    v
    r
    c
    v
    c
    v
    c
    +
    =
    m
    , где
    )
    (v
    m
    – сум- марная мера исполнителей группы
    )
    (v
    s
    H
    , подчиненной менеджеру
    v,
    )
    (v
    r
    – количество непосредственных подчиненных менеджера v, а (.)
    1
    c
    и (.)
    2
    c
    – неотрицательные монотонные функции.
    Приведенная функция стоимости иерархии является частным случаем определяемой в [1] секционной функции стоимости иерар- хии, в которой стоимость менеджера может зависеть только от состава групп, которыми управляют его непосредственные подчи- ненные. Задача, таким образом, состоит в поиске оптимальной иерархии над множеством исполнителей N.
    В [1] формулируются условия, при которых в оптимальной ие- рархии отсутствует двойное подчинение – каждый менеджер имеет ровно одного начальника (кроме топ-менеджера, у которого на- чальников нет), то есть оптимальная иерархия является деревом. В

    3 частности, это верно, если функция стоимости является группо-
    монотонной [1]. Для рассматриваемой функции затрат это означа- ет, что затраты менеджера v возрастают при увеличении меры
    )
    (v
    m контролируемой им группы и при увеличении количества его непосредственных подчиненных
    )
    (v
    r
    . Легко видеть, что так как функции
    (.)
    1
    c
    и
    (.)
    2
    c
    монотонны, функция затрат менеджера группо-монотонна и оптимальная иерархия является деревом.
    Также в [1] формулируется понятие расширяющей функции стоимости и доказывается, что для расширяющей функции опти- мальна веерная иерархия, состоящая из одного менеджера, который непосредственно контролирует всех исполнителей.
    Лемма 1.
    Если для любых целых
    2
    ''
    ,'
    ³
    r
    r
    )
    1
    ''
    '
    (
    )
    ''
    (
    )
    '
    (
    2 2
    2
    -
    +
    ³
    +
    r
    r
    c
    r
    c
    r
    c
    , то функция стоимости расширяющая и оптимальна веерная иерархия.
    Доказательство леммы вынесено в приложение.
    В частности, условия леммы выполнены, если функция
    (.)
    2
    c
    вогнута. Таким образом, имеет интерес рассматривать только случай, когда функция
    (.)
    2
    c
    не вогнута, так как в противном слу- чае по лемме 1 оптимальна веерная иерархия и задача не представ- ляет интереса.
    Лемма 2. Если в оптимальном дереве менеджер
    i
    v подчинен менеджеру
    j
    v , то
    )
    (
    )
    (
    j
    i
    v
    r
    v
    r
    £
    Доказательство леммы вынесено в приложение.
    Лемма 2 говорит о том, что в рассматриваемой модели количе- ство подчиненных у менеджера более высокого уровня не может быть меньше, чем у любого из его подчиненных, то есть количество непосредственных подчиненных не убывает «вверх» по иерархии.
    2.
    Два
    вида
    сбалансированных
    деревьев
    Данный раздел посвящен построению оптимального дерева в случае, когда фиксированы количество менеджеров и количество непосредственных подчиненных у каждого менеджера. Показыва- ется, что в оптимальное дерево обладает свойством сбалансирован-
    4
    ности, то есть каждый менеджер стремится разделить контроли- руемых им исполнителей между своими непосредственными под- чиненными на группы примерно одинаковой меры. Тем не менее, в зависимости от того, выпукла функция
    (.)
    1
    c
    или вогнута, это стремление проявляется по-разному, в результате чего при выпук- лой и вогнутой функции (.)
    1
    c
    оптимальными оказываются разные деревья.
    Зафиксируем количество менеджеров q и количество подчи- ненных
    )
    (
    i
    v
    r
    у каждого менеджера
    q
    i
    ,...,
    1
    =
    . Легко показать, что в любом дереве величины
    )
    (
    i
    v
    r
    связаны соотношением
    1
    )
    (
    1
    -
    +
    =
    å
    =
    q
    n
    v
    r
    q
    i
    i
    и для любых
    )
    (
    i
    v
    r
    , удовлетворяющих этому равенству, можно построить дерево.
    Вопрос состоит в том, как подчинять таких менеджеров друг другу, чтобы получить дерево минимальной стоимости.
    Без ограничения общности будем считать, что менеджеры упо- рядочены по возрастанию
    )
    (
    i
    v
    r
    , то есть
    )
    (
    )
    (
    j
    i
    v
    r
    v
    r
    j
    i
    ³
    Þ
    >
    Рассмотрим следующий алгоритм построения дерева, являю- щийся обобщением алгоритма Хаффмана [2] построения опти- мального бинарного дерева кодирования.
    Шаг
    0.
    Определим множество мер исполнителей
    }
    ,...,
    {
    :
    1
    n
    m m
    =
    M
    . Возьмем менеджера
    1
    =
    j
    Шаг 1. Назначим j-му менеджеру группу
    M
    Í
    j
    g
    из
    )
    (
    j
    v
    r
    подчиненных с минимальными мерами. Удалим этих исполните- лей из множества M и добавим туда менеджера j с мерой
    å
    Î
    =
    j
    g
    i
    i
    j
    v
    m m
    )
    (
    Шаг j от 2 до q. Повторим для j-го менеджера шаг 1.
    В результате получим дерево, которое будем называть деревом
    Хаффмана. Очевидно, это дерево минимизирует лексикографиче- ски вектор
    ))
    (
    ),...,
    (
    (
    1
    q
    v
    v
    m m
    мер управляемых менеджерами групп.
    Пусть функция
    (.)
    1
    c
    линейна. Тогда для фиксированных q,
    )
    (
    i
    v
    r
    ,
    q
    i
    ,...,
    1
    =
    стоимость дерева линейно зависит от суммы

    5
    å
    =
    q
    i
    i
    v
    1
    )
    (
    m мер всех групп дерева. Оказывается, что в этом случае дерево Хаффмана оптимально. Докажем сначала вспомогательный результат.
    Определение 2. Цепочкой менеджеров называется последова- тельность
    l
    v
    v ,...,
    1
    менеджеров, в которой каждый последующий менеджер является подчиненным предыдущего.
    Лемма 3. Если функция (.)
    1
    c
    линейна, то любое оптимальное дерево можно перестроить так, что в начале самой длинной цепоч- ки менеджеров будет находиться группа из
    )
    (
    1
    v
    r
    исполнителей минимальной меры.
    Доказательство леммы приведено в приложении.
    Теорема 1. Пусть функция (.)
    1
    c
    линейна. Тогда для фиксиро- ванных q,
    )
    (
    i
    v
    r
    ,
    q
    i
    ,...,
    1
    =
    дерево Хаффмана имеет минимальную стоимость.
    Доказательство теоремы приведено в приложении.
    Этот результат остается верным и для произвольной вогнутой функции (.)
    1
    c
    Теорема 2. Пусть функция (.)
    1
    c
    вогнута. Тогда для фиксиро- ванных q,
    )
    (
    i
    v
    r
    ,
    q
    i
    ,...,
    1
    =
    дерево Хаффмана имеет минимальную стоимость.
    Доказательство теоремы приведено в приложении.
    Из теории кодирования [2] известно, что в дереве Хаффмана непосредственные подчиненные любого менеджера контролируют группы примерно равных размеров, то есть менеджер делит кон- тролируемую им группу примерно поровну между своими подчи- ненными, так что дерево Хаффмана можно назвать сбалансирован- ным.
    Для вычисления дерева Хаффмана имеются эффективные ал- горитмы сложности порядка
    n
    n ln
    . Тогда для фиксированного количества менеджеров q задача поиска оптимального количества непосредственных подчиненных каждого менеджера сводится к задаче дискретной оптимизации функции
    )
    ,...,
    (
    1
    q
    r
    r
    c
    (вычислимой в
    6 среднем за
    n
    nln операций) при условиях
    1
    )
    (
    1
    -
    +
    =
    å
    =
    q
    n
    v
    r
    q
    i
    i
    ,
    2 1
    ³
    r
    ,
    i
    i
    r
    r
    ³
    +
    1
    для всех
    1 1
    -
    =
    q
    i
    Пусть теперь функция (.)
    1
    c
    не вогнута, а, например, выпукла.
    Тогда легко подобрать пример, в котором дерево Хаффмана уже не будет оптимальным.
    Рисунок 1. Иерархии над множеством из шести исполнителей.
    Пример 1. Рассмотрим случай с
    6
    =
    n
    исполнителями еди- ничной меры и
    5
    =
    q
    менеджерами, у каждого из которых по два подчиненных. Дерево Хаффмана для такого примера имеет вид, представленный на рисунке 1 а) (конечные исполнители изображе- ны черными кружками, менеджеры – белыми). Менеджеры 1, …, 5 контролируют группы размеров 2, 2, 2, 4, 6 соответственно.
    Легко проверить, что в дереве изображенном на рисунке 1 б), менеджеры контролируют группы размеров 2, 2, 3, 3, 6. Поэтому при выпуклой функции (.)
    1
    c
    это дерево имеет не большую стои- мость, чем дерево Хаффмана.
    ·
    Для выпуклой функции (.)
    1
    c
    не удается построить эффектив- ного алгоритма построения оптимального дерева. Тем не менее, оптимальное дерево также должно быть сбалансированным в том смысле, что каждый менеджер делит контролируемую им группу
    «примерно поровну», насколько это возможно. Ниже этот результат устанавливается более формально.
    Лемма 4. Пусть функция (.)
    1
    c
    строго выпукла, и у некоторого менеджера в оптимальном дереве есть два менеджера-заместителя v

    7 и '
    v
    , контролирующие группы мер m и '
    m
    соответственно. Пусть '
    m
    m
    <
    , тогда
    m
    m
    m
    -
    ³
    '
    ''
    , где ''
    m – разница между мерой любого из непосредственных подчиненных менеджера '
    v и мерой любого меньшего непосредственного подчиненного менеджера v.
    Доказательство леммы вынесено в приложение.
    Таким образом, меры групп, контролируемых заместителями одного менеджера, в оптимальном дереве стремятся выровняться.
    Лемму 4 можно обобщить на случай, когда
    v и '
    v не имеют общего непосредственного начальника. Дадим некоторые опреде- ления.
    Определение 3. Пусть в дереве выбраны две цепочки менед- жеров:
    )
    ,...,
    (
    1
    l
    v
    v
    s
    =
    и
    )
    '
    ,...,
    '
    (
    '
    '
    1
    l
    v
    v
    s
    =
    , контролирующие группы мер
    l
    m
    m ,...,
    1
    и '
    ,...,
    '
    '
    1
    l
    m
    m
    , причем менеджеры
    1
    v и '
    1
    v имеют общего непосредственного начальника и 'l
    l
    £
    . Степень разбалансирован-
    ности
    )
    '
    ,
    ( s
    s
    D
    этих цепочек определим как максимальную меру, которую можно добавить к каждому члену последовательности
    l
    m
    m ,...,
    1
    так, чтобы для всех
    l
    i
    1
    =
    выполнялись неравенства '
    )
    '
    ,
    (
    i
    i
    m
    s
    s
    m
    £
    D
    +
    , то есть
    ]
    '
    [
    min
    )
    '
    ,
    (
    1
    i
    i
    l
    i
    m
    m
    s
    s
    -
    =
    D
    =
    Для остальных пар цепочек менеджеров степень разбалансиро- ванности не определена.
    Определение 4. Пусть непосредственные подчиненные ме- неджеров v и '
    v контролируют группы мер
    r
    m
    m ,...,
    1
    и '
    ,...,
    '
    '
    1
    r
    m
    m
    соответственно. Минимальным скачком
    )
    '
    ,
    ( v
    v
    d называется мини- мальная положительная разница между суммой элементов произ- вольного подмножества
    }
    '
    ,...,
    '
    {
    '
    1
    r
    m
    m
    и суммы элементов подмноже- ства
    }
    ,...,
    {
    1
    r
    m
    m
    такого же размера.
    Пример 2. Возьмем некоторых менеджеров v и '
    v , подчинен- ные которых контролируют группы мер
    }
    4
    ,
    7
    ,
    11
    {
    ,
    }
    18
    ,
    1
    {
    соответст- венно. Для них минимальный скачок
    )
    '
    ,
    ( v
    v
    d равен 1, так как
    1
    )
    7 11
    (
    18 1
    =
    +
    -
    +
    , остальные же разницы больше.
    ·
    Теорема 3. Пусть функция
    (.)
    1
    c
    строго выпукла и в опти- мальном дереве степень разбалансированности
    )
    '
    ,
    ( s
    s
    D
    цепочек
    8
    )
    ,...,
    (
    1
    l
    v
    v
    s
    =
    и
    )
    '
    ,...,
    '
    (
    '
    '
    1
    l
    v
    v
    s
    =
    больше нуля. Тогда минимальный скачок
    )
    '
    ,
    (
    'l
    l
    v
    v
    d не меньше степени разбалансированности
    )
    '
    ,
    ( s
    s
    D
    Доказательство теоремы аналогично доказательству леммы 4.
    Утверждение теоремы позволяет преобразовать изображенное на рисунке 1 а) дерево Хаффмана к оптимальному дереву, изобра- женному на рисунке 1 б). Для этого достаточно передать менеджера
    2 из подчинения менеджера 4 менеджеру 3, заменив его конечным исполнителем 6.
    Из теоремы видно, что задача построения оптимального дерева является усложненной модификацией известной «задачи о камнях»
    (в общем случае NP-полной), что делает проблематичным поиск эффективных алгоритмов решения задачи об оптимальном дереве для выпуклой функции (.)
    1
    c
    3.
    Заключение
    В статье рассмотрена задача построения оптимальной иерар- хии над заданным множеством конечных исполнителей в случае, когда стоимость узла иерархии (менеджера) зависит от суммарной меры контролируемой группы исполнителей и от количества непо- средственных подчиненных менеджера.
    Найдены случаи, когда оптимальной является иерархия с единственным менеджером. Показано, что в оптимальной иерархии количество непосредственных подчиненных не убывает «вверх» по иерархии.
    Введено понятие сбалансированного дерева и показано, что оптимальная иерархия представляет собой сбалансированное дерево одного из двух типов. Для ряда случаев построен эффектив- ный алгоритм построения оптимальной иерархии с заданным количеством менеджеров и заданным количеством подчиненных у каждого менеджера.
    Приложение
    Доказательство леммы 1. Пусть в оптимальном дереве ме- неджер
    i
    v подчинен менеджеру
    j
    v . Удалим менеджера
    i
    v и пере-

    9 подчиним его подчиненных менеджеру
    j
    v . Стоимость дерева уменьшится на
    ))
    (
    (
    ))
    (
    (
    ))
    (
    (
    2 2
    1
    j
    i
    i
    v
    r
    c
    v
    r
    c
    v
    c
    +
    +
    m и увеличится на
    )
    1
    )
    (
    )
    (
    (
    2
    -
    +
    i
    j
    v
    r
    v
    r
    c
    . Поскольку
    0
    (.)
    1
    ³
    c
    , стоимость дерева умень- шится, если
    )
    1
    )
    (
    )
    (
    (
    ))
    (
    (
    ))
    (
    (
    2 2
    2
    -
    +
    ³
    +
    j
    i
    j
    i
    v
    r
    v
    r
    c
    v
    r
    c
    v
    r
    c
    ·
    Доказательство леммы 2. Пусть это не так, то есть менеджер
    i
    v подчинен менеджеру
    j
    v и
    )
    (
    )
    (
    j
    i
    v
    r
    v
    r
    >
    . Возьмем любых
    1
    )
    (
    )
    (
    :
    ³
    -
    =
    D
    j
    i
    v
    r
    v
    r
    подчиненных i-го менеджера с суммарной мерой m
    и переподчиним их j-му менеджеру. Стоимость дерева изменится на
    ))].
    (
    (
    ))
    (
    (
    ))
    (
    (
    [
    )]
    )
    (
    (
    )
    )
    (
    (
    )
    )
    (
    (
    [
    2 2
    1 2
    2 1
    j
    i
    i
    j
    i
    i
    v
    r
    c
    v
    r
    c
    v
    c
    v
    r
    c
    v
    r
    c
    v
    c
    +
    +
    -
    D
    +
    +
    D
    -
    +
    - m
    m m
    Но понятно, что
    )
    (
    )
    (
    j
    i
    v
    r
    v
    r
    =
    D
    -
    ,
    D
    +
    =
    )
    (
    )
    (
    j
    i
    v
    r
    v
    r
    , то есть стоимость дерева изменится на
    ))
    (
    (
    )
    )
    (
    (
    1 1
    i
    i
    v
    c
    v
    c
    m m
    m
    -
    -
    , и, в силу монотонности функции (.)
    1
    c
    , уменьшится.
    ·
    Доказательство леммы 4. Пусть в некотором оптимальном дереве, первым (самым нижним) менеджером в самом длинном пути стоит менеджер
    v , управляющий группой g из
    )
    (v
    r
    подчи- ненных.
    Пусть найдутся такие исполнители
    g
    i
    Î
    и
    g
    j
    Ï
    , что
    j
    i
    m m >
    У i-го исполнителя есть
    i
    m начальников, отличных от началь- ников j-го исполнителя. Аналогично, у j-го исполнителя есть
    j
    m начальников, отличных от начальников i-го исполнителя. Так как исполнитель i находится в начале самого длинного пути, понятно, что
    j
    i
    m
    m
    ³
    Поменяем этих исполнителей местами. Тогда у
    i
    m начальни- ков i-го исполнителя меры контролируемых ими групп уменьшатся на
    0
    :
    >
    -
    =
    D
    j
    i
    m m
    , а у
    j
    m начальников j-го исполнителя увеличат- ся на
    D
    . Так как
    j
    i
    m
    m
    ³
    , сумма мер групп всех менеджеров от такой перестановки не увеличится. То есть можно считать, что в
    10 начале самого длинного пути стоит группа из исполнителей с минимальными мерами.
    Докажем, что
    )
    (v
    r
    минимально. Пусть это не так. Тогда по лемме 3 найдется менеджер '
    v , непосредственно контролирующий группу '
    g из
    )
    (
    )
    (
    1
    v
    r
    v
    r
    <
    исполнителей. По доказанному выше,
    )
    '
    (
    )
    (
    v
    v
    m m
    £
    . Тогда поменяем эти группы местами. Аналогично вышеописанному доказывается, что стоимость дерева при этом не увеличится.
    ·
    Доказательство теоремы 1. Возьмем дерево Хаффмана H.
    Пусть имеется дерево '
    H строго меньшей стоимости. По лемме 3 в этом дереве, как и в дереве Хаффмана, имеется менеджер v, непо- средственно управляющий
    )
    (
    1
    v
    r
    исполнителями с минимальными мерами. Стоимость этого менеджера одинакова в обоих деревьях.
    Тогда заменим в обоих деревьях этого менеджера и его подчинен- ных одним исполнителем с мерой
    )
    (v
    m
    . При этом стоимость обоих деревьев уменьшится стоимость этого менеджера, то есть, на оди- наковую величину. В получившихся деревьях, аналогично, найдет- ся пара идентичных менеджеров, которых также удалим. Повторя- ем эти шаги, пока в деревьях не останется один, самый верхний менеджер.
    По лемме 2 в корне оптимального дерева находится менеджер с максимальным количеством подчиненных
    )
    (
    q
    v
    r
    . Он же стоит и в корне дерева Хаффмана, то есть стоимость получившихся «сверну- тых» деревьев одинакова. Значит, и стоимость исходных деревьев одинакова.
    ·
    Доказательство теоремы 2. Рассмотрим некоторое оптималь- ное дерево H. Перенумеруем менеджеров этого дерева так, чтобы меры контролируемых ими групп шли по возрастанию. Получили неубывающую последовательность мер
    q
    m
    m ,...,
    1
    . Рассмотрим теперь дерево Хаффмана '
    H . Также перенумеровав его менеджеров по возрастанию мер контролируемых групп, получим неубываю- щую последовательность '
    ,...,
    '
    1
    q
    m
    m
    . Предположим, что дерево

    11
    Хаффмана не оптимально, а значит, последовательности
    q
    m
    m ,...,
    1
    и '
    ,...,
    '
    1
    q
    m
    m
    различаются.
    Рассмотрим разность стоимостей деревьев H и '
    H
    å
    å
    =
    =
    -
    =
    D
    q
    i
    i
    q
    i
    i
    m
    c
    m
    c
    C
    1 1 1 1
    )
    '
    (
    )
    (
    :
    Обозначим
    i
    a
    – наклон некоторой касательной к функции
    (.)
    1
    c
    в точке
    i
    m ,
    q
    i
    1
    =
    . Так как функция
    (.)
    1
    c
    монотонная и вогнутая, последовательность
    i
    a
    ,
    q
    i
    1
    =
    неотрицательная и не возрастает. Кроме того, в силу вогнутости (.)
    1
    c
    верно неравенство
    )
    '
    (
    )
    (
    )
    '
    (
    1 1
    i
    i
    i
    i
    i
    m
    m
    m
    c
    m
    c
    -
    +
    £
    a и, значит,
    å
    =
    -
    ³
    D
    q
    i
    i
    i
    i
    m
    m
    C
    1
    )
    '
    (
    a
    По теореме 1 дерево Хаффмана минимизирует сумму мер групп, то есть
    å
    å
    =
    =
    ³
    q
    i
    i
    q
    i
    i
    m
    m
    1 1
    ' .
    Кроме того, как отмечено выше, дерево Хаффмана минимизи- рует лексикографически вектор мер групп, то есть если j – мини- мальный номер менеджера, для которого '
    j
    j
    m
    m
    ¹
    , то '
    j
    j
    m
    m
    >
    Отметим, что
    q
    j
    <
    , так как для любой пары деревьев
    å
    =
    =
    =
    n
    i
    i
    q
    q
    m
    m
    1
    '
    m
    Таким образом, получили оценку
    å
    -
    =
    -
    ³
    D
    1
    )
    '
    (
    q
    j
    i
    i
    i
    i
    m
    m
    C
    a
    Если
    1
    -
    =
    q
    j
    , то, очевидно,
    0
    >
    D
    C
    . Пусть теперь
    1
    -
    <
    q
    j
    Зафиксируем
    j
    m и найдем минимум выражения
    å
    -
    =
    -
    1
    )
    '
    (
    q
    j
    i
    i
    i
    i
    m
    m
    a по всем
    i
    m ,
    1
    ,...,
    1
    -
    +
    =
    q
    j
    i
    при условиях, что
    å
    å
    -
    =
    -
    =
    ³
    1 1
    '
    q
    j
    i
    i
    q
    j
    i
    i
    m
    m
    ,
    '
    j
    j
    m
    m
    >
    и
    1
    -
    ³
    i
    i
    m
    m
    при всех
    1
    ,...,
    1
    -
    +
    =
    q
    j
    i
    Так как
    i
    a не возрастает, минимум достигается при
    j
    i
    m
    m
    =
    для всех
    2
    ,...,
    1
    -
    +
    =
    q
    j
    i
    ,
    å
    -
    =
    -
    -
    -
    +
    =
    2 1
    1
    )
    '
    (
    '
    q
    j
    i
    j
    i
    q
    q
    m
    m
    m
    m
    и равен
    å
    å
    -
    =
    -
    -
    =
    -
    +
    -
    2 1
    2
    )
    '
    (
    )
    '
    (
    q
    j
    i
    j
    i
    q
    q
    j
    i
    i
    j
    i
    m
    m
    m
    m
    a a
    Так как '
    j
    j
    m
    m
    >
    и
    i
    a не возрастает с ростом индекса i, этот минимум не превышает
    0
    )
    '
    '
    (
    (
    2 1
    º
    -
    +
    -
    å
    -
    =
    -
    q
    j
    i
    j
    i
    i
    j
    q
    m
    m
    m
    m
    a
    12
    Следовательно,
    0
    ³
    D
    C
    , и стоимость оптимального дерева H не меньше стоимости дерева Хаффмана '
    H , то есть дерево Хафф- мана оптимально.
    ·
    Доказательство леммы 4. Пусть лемма неверна и найдутся заместитель менеджера v и заместитель менеджера '
    v с мерами
    1
    m и
    2
    m соответственно, что
    1 2
    m
    m
    >
    ,
    '
    1 2
    m
    m
    m
    m
    <
    -
    +
    . Тогда поме- няем этих заместителей местами. Стоимость менеджеров
    v и '
    v изменилась на
    )
    '
    (
    )
    (
    ))
    (
    '
    (
    ))
    (
    (
    1 1
    1 2
    1 1
    2 1
    m
    c
    m
    c
    m
    m
    m
    c
    m
    m
    m
    c
    -
    -
    -
    -
    +
    -
    +
    , стоимость остальных менеджеров осталась прежней. Если '
    1 2
    m
    m
    m
    m
    <
    -
    +
    , то
    )
    (
    '
    1 2
    m
    m
    m
    m
    -
    -
    <
    , и (в силу строгой выпукло- сти функции
    (.)
    2
    c
    ) выполнено неравенство
    )
    '
    (
    )
    (
    ))
    (
    '
    (
    ))
    (
    (
    1 1
    1 2
    1 1
    2 1
    m
    c
    m
    c
    m
    m
    m
    c
    m
    m
    m
    c
    +
    <
    -
    -
    +
    -
    +
    , то есть стои- мость дерева строго уменьшилась, что невозможно.
    ·
    Литература
    1.
    Мишин С.П. Оптимальные иерархии управления в экономиче-
    ских системах. М.: ПМСОФТ, 2004.
    2.
    Huffman D. A method for the construction of minimum redundancy
    codes. Proc. of the IRE 40, 1952, pp. 1098-1101.
    написать администратору сайта