4501
правка
Жадные алгоритмы аппроксимации: различия между версиями
Перейти к навигации
Перейти к поиску
Жадные алгоритмы аппроксимации (посмотреть исходный код)
Версия от 21:38, 23 апреля 2015
, 23 апреля 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
Лемма 1. Функция f: | '''Лемма 1'''. Функция <math>f: 2^X \to R</math> является субмодулярной в том и только том случае, если <math>\Delta_x f(A) \le \Delta_x f(B)</math> для любого <math>x \in X - B \;</math> и <math>A \subseteq B \;</math>. Кроме того, f является монотонно возрастающей в том и только том случае, если <math>\Delta_x f(A) \le \Delta_x f(B)</math> для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>. | ||
''Доказательство''. Если f является субмодулярной, то для <math>x \in X - B \;</math> и <math>A \subseteq B \;</math> имеет место соотношение | |||
<math>f(A \cup \{ x \} )+ f(B) \ge f((A \cup \{ x \} ) \cup B) + f(A \cup \{ x \} ) \cap B) = f(B \cup \{ x \} ) + f(A)</math>, | |||
иначе говоря, | |||
(1) <math>\Delta_x f(A) \ge \Delta_x f(B)</math>. | |||
Напротив, предположим, что свойство (1) выполняется для любого x 2 B и AC B. Пусть C и D – два множества и C n D = fx1,..x k g. Тогда | Напротив, предположим, что свойство (1) выполняется для любого x 2 B и AC B. Пусть C и D – два множества и C n D = fx1,..x k g. Тогда | ||
U | U | ||