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

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

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.

Рекомендуем скачать другие рефераты по теме: банки рефератов, где диплом.





1  2  3  4 | Следующая страница реферата