Xreferat.com » Рефераты по математике » Градиентный алгоритм для систем независимости с отрицательными весами

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

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

Доказательство. Так как Градиентный алгоритм для систем независимости с отрицательными весамиотлична от матроида, то по лемме 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.

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: