Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Градиентный алгоритм для систем независимости с отрицательными весами
Раздел: Рефераты по математике
Тип: статья Добавлен 18:35:07 24 марта 2007 Похожие работы
Просмотров: 39 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:57:11 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:54:45 24 ноября 2015

Работы, похожие на Статья: Градиентный алгоритм для систем независимости с отрицательными весами

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151202)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru