Градиентный алгоритм для систем независимости с отрицательными весами (стр. 1 из 2)

И.В. Оффенбах, Омский государственный университет, кафедра прикладной и вычислительной математики

1. Основные понятия

Пусть E - конечное множество,

- непустое семейство его подмножеств. Семейство называется системой независимости, если

Множества семейства

называются независимыми множествами, а подмножества E, не вошедшие в семейство , - зависимыми. Базой множества называется любое максимальное по включению независимое подмножество F. Базы множества E называются базами системы независимости. Множество всех баз будем обозначать . Введем обозначения:

Числа lr(F), ur(F) называются соответственно нижним и верхним рангом множества F. Величина

называется кривизной системы независимости

(минимум берется по всем ). Очевидно, что для любой системы независимости .

Рассмотрим задачу максимизации на системе независимости:

где

- семейство баз системы независимости , а - аддитивная весовая функция.

Для решения задачи (1) применим следующий Алгоритм A:

Шаг 0: Упорядочить множество

по невозрастанию весов; ;

Шаг i:

. Если , то ; если i < n, то перейти на шаг i+1, иначе результат SA. Алгоритмы такого типа в англоязычной литературе имеют наименование greedy, что обычно переводится как жадный. Жадный алгоритм является дискретным аналогом градиентного алгоритма, поэтому его называют также градиентным алгоритмом.

Договоримся далее через SA обозначать результат работы алгоритма A на системе независимости

, а через S0 - базу максимального веса

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

В работе [1] (см. также [2]) получена следующая нижняя оценка погрешности градиентного алгоритма решения задачи (1).

Теорема 1 (Корте и Хаусманн). Пусть

- произвольная система независимости. Тогда для любой неотрицательной аддитивной весовой функции задачи максимизации (1) имеет место достижимая оценка

где k - кривизна системы

.

Cистема независимости называется матроидом, если семейство

ее баз обладает следующим свойством:

В дальнейшем нам понадобится следующая

Лемма 1.

Доказательство. При lr(E)=ur(E) лемма, очевидно, следует из определения матроида.

Рассмотрим случай lr(E)<ur(E). Пусть

. Перенумеруем элементы и так, что если среди них есть одинаковые, то они имеют первые m номеров ( ), иначе m=0. Определим где r=ur(E).

Шаг 0: Am=A - база. Шаг i:

. Am+i-1 - база, следовательно, множество независимо и не база. Если - не база, то мы нашли требуемые базы Am+i-1, B и элемент u=am+i. Иначе пусть - база. Переход на шаг i+1.

Учитывая, что A|B| зависимо (т.к. B - база и

), алгоритм завершится не позднее, чем на шаге |B|+1 доказательством леммы.

2. Характеристика

и ее свойства

Фронтом данного независимого множества F назовем

.

Fr(F) - это множество элементов, каждый из которых может быть добавлен к F без нарушения его независимости. Именно из этих элементов градиентный алгоритм выберет на очередном шаге самый "тяжелый" для добавления к F.

Введем новую характеристику системы независимости:

Она характеризует "узкое место" в работе градиентного алгоритма.

Будем называть предбазами максимальные по включению независимые множества, не являющиеся базами. Тогда определение (4) можно записать как

поскольку каждое независимое подмножество, которое не является базой, содержится в некоторой предбазе и

.

Теорема 2. 1) Для систем независимости

, базы которых представляют собой все r-элементные подмножества (r-однородные матроиды),

где n=|E|, r=ur(E).

2) Для систем независимости, отличных от r-однородных матроидов,

Доказательство. 1) Очевидно, т.к. |Fr(F)|=n-|F|=n+1-ur(E) для любой предбазы F.

2) Если

матроид (не r-однородный), то . Пусть F - база A. Т.к. |F|<|A|, то F не является базой матроида и .

Если

не матроид, то по лемме 1 . Заметим, что .

Замечание. На различных системах независимости

может принимать значения от 1 до n=|E| включительно, причем только в случае 1-однородного матроида.

Теорема 3 (оценка кривизны). Для любой системы независимости, отличной от 1-однородного матроида, имеет место оценка

Доказательство. Если система независимости

представляет собой r-однороный матроид, , то k=1 и оценка (6) верна. Иначе , следовательно, и т.к. и ( ), то

Пусть дана система независимости

, через (через ) обозначим такое минимальное число, что существует весовая функция , ровно ( ) значений которой отрицательны, и SA (S0) содержит по крайней мере один элемент с отрицательным весом.