База курсовых работ, рефератов, научных работ! Otryvnoy.ru Рефераты, курсовые, дипломные работы

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

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

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

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

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) содержит по крайней мере один элемент с отрицательным весом.

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

Доказательство. Пусть  Градиентный алгоритм для систем независимости с отрицательными весами. Присвоим элементам множества F0 вес |E|, элементам Fr(F0) вес -1, а остальным элементам вес 0. Тогда SA и S0 будут содержать элементы с отрицательным весом и, следовательно,  Градиентный алгоритм для систем независимости с отрицательными весамии  Градиентный алгоритм для систем независимости с отрицательными весами(всего отрицательных весов  Градиентный алгоритм для систем независимости с отрицательными весами).

Если число "отрицательных" элементов меньше  Градиентный алгоритм для систем независимости с отрицательными весами, то SA и S0 не могут содержать элементов с отрицательным весом (для SA это очевидно. Если же S0 содержит "отрицательные", то рассмотрим подмножество его "неотрицательных" элементов C. В силу определения  Градиентный алгоритм для систем независимости с отрицательными весамимы можем добавлять к C "неотрицательные" элементы, пока не получим базу, вес которой строго больше веса S0). Следовательно,  Градиентный алгоритм для систем независимости с отрицательными весамии  Градиентный алгоритм для систем независимости с отрицательными весами.

Замечание. Отрицательность здесь не играет принципиальной роли. Основной ее смысл в том, что выделяется класс "отрицательных" элементов, вес каждого из которых меньше веса любого "неотрицательного". К примеру, теорему 4 можно интерпретировать так: S0 и SA не содержат ни одного из  Градиентный алгоритм для систем независимости с отрицательными весаминаименьших по весу элементов.

3. Оценки погрешности  градиентного алгоритма

Лемма 2. Пусть  Градиентный алгоритм для систем независимости с отрицательными весами- произвольная система независимости,  Градиентный алгоритм для систем независимости с отрицательными весами- весовая функция, допускающая отрицательные веса. Если при этом веса всех элементов SA неотрицательны, то справедлива оценка (2).

Доказательство. Рассмотрим новую задачу, в которой все отрицательные веса исходной задачи сделаем нулевыми, оставив тот же порядок элементов (для новой задачи используются обозначения c', S'A, S'0). Тогда S'A=SA, c'(S'A)=c(SA) и  Градиентный алгоритм для систем независимости с отрицательными весами. А поскольку в новой задаче все веса неотрицательны, то теорема 1 справедлива и

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

Из теоремы 4 и леммы 2 непосредственно следует

Теорема 5. Пусть дана система независимости  Градиентный алгоритм для систем независимости с отрицательными весамии весовая функция  Градиентный алгоритм для систем независимости с отрицательными весами, количество отрицательных значений которой меньше, чем  Градиентный алгоритм для систем независимости с отрицательными весами. Тогда

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

Теперь рассмотрим ситуацию, когда нет ограничения на число элементов отрицательного веса.

Хорошо известна теорема Радо-Эдмондса, которая утверждает, что если система независимости является матроидом, то для произвольной неотрицательной весовой функции градиентный алгоритм всегда находит точное решение задачи (1). Нетрудно показать, что этот результат остается верным и для случая, когда допускаются отрицательные веса.

Однако из следующей теоремы вытекает, что если система независимости отлична от матроида, то в общем случае невозможно получить оценку погрешности градиентного алгоритма.

Теорема 6. Если система независимости  Градиентный алгоритм для систем независимости с отрицательными весамиотлична от матроида, то для произвольных  Градиентный алгоритм для систем независимости с отрицательными весамисуществует такая весовая функция  Градиентный алгоритм для систем независимости с отрицательными весами, что  Градиентный алгоритм для систем независимости с отрицательными весамии  Градиентный алгоритм для систем независимости с отрицательными весами. Причем, если  Градиентный алгоритм для систем независимости с отрицательными весами, то существует  Градиентный алгоритм для систем независимости с отрицательными весамис этим же свойством.

Доказательство. Так как  Градиентный алгоритм для систем независимости с отрицательными весамиотлична от матроида, то по лемме 1  Градиентный алгоритм для систем независимости с отрицательными весами, |B|=lr(E), и  Градиентный алгоритм для систем независимости с отрицательными весами. Рассмотрим два случая:

1)  Градиентный алгоритм для систем независимости с отрицательными весами. Среди всех баз, которые являются подмножествами  Градиентный алгоритм для систем независимости с отрицательными весамивыберем максимальную по мощности базу C. Присвоим всем элементам  Градиентный алгоритм для систем независимости с отрицательными весамивес, условно говоря,  Градиентный алгоритм для систем независимости с отрицательными весами, элементам  Градиентный алгоритм для систем независимости с отрицательными весамивес  Градиентный алгоритм для систем независимости с отрицательными весами, а элементу u вес  Градиентный алгоритм для систем независимости с отрицательными весами. Если S0 содержит u, то  Градиентный алгоритм для систем независимости с отрицательными весами, иначе, очевидно,  Градиентный алгоритм для систем независимости с отрицательными весами. А т.к.  Градиентный алгоритм для систем независимости с отрицательными весами, то нетрудно понять, что  Градиентный алгоритм для систем независимости с отрицательными весами.

2)  Градиентный алгоритм для систем независимости с отрицательными весами. Среди всех баз, которые являются подмножествами  Градиентный алгоритм для систем независимости с отрицательными весами, выберем базу C, для которой  Градиентный алгоритм для систем независимости с отрицательными весамиминимальна. Пусть v произвольный элемент  Градиентный алгоритм для систем независимости с отрицательными весами. Присвоим элементам  Градиентный алгоритм для систем независимости с отрицательными весамивес  Градиентный алгоритм для систем независимости с отрицательными весами, элементу u вес  Градиентный алгоритм для систем независимости с отрицательными весами, элементу v вес  Градиентный алгоритм для систем независимости с отрицательными весами, а всем остальным элементам вес 0 (в этом случае  Градиентный алгоритм для систем независимости с отрицательными весами). Т.к.  Градиентный алгоритм для систем независимости с отрицательными весамиминимальна, то любая база, веса отличного от  Градиентный алгоритм для систем независимости с отрицательными весамии не содержащая u, содержит v, поэтому  Градиентный алгоритм для систем независимости с отрицательными весами.

В обоих случаях можно так упорядочить элементы равного веса, что SA=A и  Градиентный алгоритм для систем независимости с отрицательными весами.

Замечание. Задачу максимизации с весами  Градиентный алгоритм для систем независимости с отрицательными весамиможно интерпретировать как задачу минимизации с весами  Градиентный алгоритм для систем независимости с отрицательными весами(весовой функцией c'(e)=-c(e)). Теорема 6 показывает, что для любой системы независимости, отличной от матроида, и задачи минимизации на ней (все веса неотрицательные) в принципе не может существовать гарантированной оценки погрешности градиентного алгоритма.

Список литературы

Hausmann D., Korte B. Lower bounds on the worst-case complexity of some oracle algorithms // Discrete Math. 1978. V.24. N 3. P.261-276.

Korte B. Approximative algorithms for discrete optimization problems // Annals of Discrete Math. Amsterdam: North-Holland. 1979. V.4. P.85-120.

Для подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/




Наш опрос
Как Вы оцениваете работу нашего сайта?
Отлично
Не помог
Реклама
 
Мнение авторов может не совпадать с мнением редакции сайта
Перепечатка материалов без ссылки на наш сайт запрещена