4501
правка
Жадные алгоритмы аппроксимации: различия между версиями
Перейти к навигации
Перейти к поиску
Жадные алгоритмы аппроксимации (посмотреть исходный код)
Версия от 22:31, 23 апреля 2015
, 23 апреля 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 85: | Строка 85: | ||
Лемма 2. Если A | '''Лемма 2'''. Если <math>A \subset B \;</math>, то <math>\Delta_y q(A) \ge \Delta_y q(B)</math>. | ||
''Доказательство''. Заметим, что каждый связный компонент графа (v, D(B)) состоит из одного или нескольких связных компонентов графа (v, D(A)), поскольку <math>A \subset B \;</math>. Следовательно, количество связных компонентов (v, D(B)), доминируемых y, не превышает количества связных компонентов (v, D(A)), доминируемых y. Таким образом, лемма верна. | |||
Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3]. | Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3]. | ||
Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации | Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации | ||
min c(A) при условии A | |||
min c(A) | |||
при условии <math>A \in C_f</math>, | |||
где c – неотрицательная целевая функция, определенная на | где c – неотрицательная целевая функция, определенная на <math>2^X \;</math>, и <math>C_f = \{ C | f(C \cup \{ x \} ) - f(C) = 0</math> для всех <math>x \in X \} \;</math>. Существует жадный алгоритм, вычисляющий приближенное решение этой задачи. | ||
'''Жадный алгоритм B''' | |||
входные данные – субмодулярная функция f и целевая функция c; | входные данные – субмодулярная функция f и целевая функция c; | ||
while существует x 2 E, такое, что Axf(A) > 0 | while существует x 2 E, такое, что Axf(A) > 0 | ||