Статья: Градиентный алгоритм для систем независимости с отрицательными весами

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

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) - это множество элементов, каждый из которых может быть курсовые - 700 р.


Назад