Жадные алгоритмы аппроксимации: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
мНет описания правки
 
(не показаны 34 промежуточные версии этого же участника)
Строка 16: Строка 16:
выбрать вершину x так, чтобы максимизировать <math>f(C) - f(C \cup \{ x \} )</math> и <math>C \leftarrow C \cup \{ x \}</math>; вывести C.
выбрать вершину x так, чтобы максимизировать <math>f(C) - f(C \cup \{ x \} )</math> и <math>C \leftarrow C \cup \{ x \}</math>; вывести C.


Здесь f определяется как f(C) = p(C) + q(C), где p(C) – количество связных компонент подграфа, порожденного C, а q(C) – количество связных компонент подграфа с множеством вершин V и множеством дуг f(u, v) 2 E j и 2 C или v 2 Cg. Функция f обладает важным свойством: C является связным доминирующим множеством в том и только том случае, если f(C) = 2.
Здесь f определяется как f(C) = p(C) + q(C), где p(C) – количество связных компонент подграфа, порожденного C, а q(C) – количество связных компонент подграфа с множеством вершин V и множеством дуг <math>\{ (u, v) \in E | u \in C </math> или <math> v \in C \}</math>. Функция f обладает важным свойством: C является связным доминирующим множеством в том и только том случае, если f(C) = 2.




Если C является связным доминирующим множеством, то p(C) = q(C) = 1 и, следовательно, f(C) = 2. Напротив, предположим, что f(C[fxg) = 2. Поскольку p(C) > 1 и q(C) > 1, должно иметь место p(C) = q(C) = 1, из чего следует, что C является связным доминирующим множеством. Функция f обладает еще одним свойством на графе G, имеющем не менее трех вершин: если f(C) > 2, то существует x 2 V, такое, что f(C)-f(CU{x}) > 0. Фактически, для C = ;, поскольку G является связным графом, имеющим не менее трех вершин, должна существовать вершина x со степенью не ниже двух, и для такой вершины x выполняется f(C [ fxg) < f(C). Для C ф ;, рассмотрим связную компоненту подграфа, порожденного C. Обозначим как B его множество вершин, являющееся подмножеством C. Для каждой вершины y, смежной с B, в случае, если y смежна с вершиной, не смежной с B и не принадлежащей к C, то p(C [ fyg) < p(C) и q(C U yg) < q(C); если вершина y смежна с вершиной из множества C — B, то p(C U yg) < p(C) и q(C [ fyg) < q(C).
Если C является связным доминирующим множеством, то p(C) = q(C) = 1 и, следовательно, f(C) = 2. Напротив, предположим, что <math>f(C \cup \{ x \}) = 2</math>. Поскольку <math>p(C) \ge 1 \;</math> и <math>q(C) \ge 1 \;</math>, должно иметь место p(C) = q(C) = 1, из чего следует, что C является связным доминирующим множеством. Функция f обладает еще одним свойством на графе G, имеющем не менее трех вершин: если f(C) > 2, то существует <math>x \in V \;</math>, такое, что <math>f(C) - f(C \cup \{ x \} ) > 0</math>. Фактически, для <math>C \ne \empty \;</math>, поскольку G является связным графом, имеющим не менее трех вершин, должна существовать вершина x со степенью не ниже двух, и для такой вершины x выполняется <math>f(C \cup \{ x \}) < f(C)</math>. Для случая <math>C \ne \empty \;</math> рассмотрим связную компоненту подграфа, порожденного C. Обозначим как B его множество вершин, являющееся подмножеством C. Для каждой вершины y, смежной с B, в случае, если y смежна с вершиной, не смежной с B и не принадлежащей к C, то <math>p(C \cup \{ y \} ) < p(C)</math> и <math>q(C \cup \{ y \} ) \le q(C)</math>; если вершина y смежна с вершиной из множества C — B, то <math>p(C \cup \{ y \} ) \le p(C)</math> и <math>q(C \cup \{ y \} ) < q(C)</math>.




Проведем некоторый анализ вышеприведенного жадного алгоритма: Пусть x 1..: ; Xg – вершины, выбранные жадным алгоритмом в порядке их появления в алгоритме. Введем обозначение C, = {x\,... , x,}. Пусть C* = {y\,... , yopt} – минимальное связное доминирующее множество. Поскольку добавление C* к Ci уменьшит значение гармонической функции с f(Ci) до 2, значение f, уменьшенной на вершину из C*, будет в среднем составлять (f(Ci) 2)/opt. Но, согласно жадному правилу выбора xi + 1, должно иметь место
Проведем некоторый анализ вышеприведенного жадного алгоритма: Пусть <math>x_1, ..., x_g \;</math> – вершины, выбранные жадным алгоритмом в порядке их появления в алгоритме. Введем обозначение <math>C_i = \{ x_1, ... , x_i \} \;</math>. Пусть <math>C^* = \{ y_1, ..., y_{opt} \} \; </math> – минимальное связное доминирующее множество. Поскольку добавление <math>C^* \; </math> к <math>C_i \;</math> уменьшит значение гармонической функции с <math>f(C_i) \;</math> до 2, значение f, уменьшенной на вершину из <math>C^* \;</math>, будет в среднем составлять <math>(f(C_i) - 2)/opt \;</math>. Но, согласно жадному правилу выбора <math>x_i + 1 \;</math>, должно иметь место соотношение <math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt}</math>.
   
   


Следовательно, <math>f(C_{i + 1}) - 2 \le (f(C_i) - 2) (1 - \frac{1}{opt}) \le (f( \empty ) - 2) (1 - \frac{1}{opt})^{i + 1} = (n - 2) (1 - \frac{1}{opt})^{i + 1}</math>,
Следовательно,
 
1
 
opt
где <math>n = |V| \;</math>. Заметим, что <math>1 - 1/ opt \le  e^{- 1/opt} </math>. Следовательно, <math>f(C_i) - 2 \le (n - 2) e^{-i/opt}</math>.
i+1 = {n-2)
 
1) opt
 
— opt
Выберем такое значение i, что <math>f(C_i) \ge opt + 2 > f(C_{i+1})</math>. Тогда <math>opt \le (n - 2) e^{-i/opt}</math> и <math>g - i \le opt \;</math>.
< (f(;) -
где n = |V|. Заметим, что 1 - 1/ opt < е~11оР(. Следовательно, f(Ci)-2<(n-2)e-il°Pt : Выберем такое значение i, что f(Ci) > opt + 2 > f(Ci+1). Тогда opt < (п-2)е-"°Р( и
g - i < opt :




Таким образом,
Таким образом, <math>g \le opt + i \le opt \left ( 1 + ln \frac{n - 2}{opt} \right ) </math>.
n-2"
opt
< opt + i < opt I 1 + ln




Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа алгоритма жадной аппроксимации с несубмодулярной гармонической функцией.
Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа жадного алгоритма аппроксимации с несубмодулярной гармонической функцией.


== Основные результаты ==
== Основные результаты ==


Роль субмодулярности
'''Роль субмодулярности'''
 
 
Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств <math>2^X \;</math>, то есть семействе всех подмножеств X. Функция f называется [[субмодулярная функция|субмодулярной]], если для любых двух подмножеств A и B в <math>2^X \;</math> выполняется неравенство
 
 
<math>f(A) + f(B) \ge f(A \cap B) + f(A \cup B)</math>.
 
 
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция -q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций.
 
 
Субмодулярная функция f называется [[нормализованная функция|нормализованной]], если <math>f( \empty ) = 0</math>. Каждая субмодулярная функция может быть нормализована посредством задания <math>g(A) = f(A) - f( \empty )</math>. Функция f является [[монотонно возрастающая функция|монотонно возрастающей]], если <math>f(A) \le f(B) \;</math> в случае <math>A \subset B \;</math>. Обозначим <math>\Delta_x f(A) = f(A \cup \{ x \} ) - f(A)</math>.
 
 
'''Лемма 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>.




Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств 2X, то есть семействе всех подмножеств X. Функция f называется субмодулярной, если для любых двух подмножеств A и B в 2X выполняется
''Доказательство''. Если f является субмодулярной, то для <math>x \in X - B \;</math> и <math>A \subseteq B \;</math> имеет место соотношение
f(A) + f(B) > f(A \ B) + f(A [ B) :
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция—q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций.


<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>,


Субмодулярная функция f называется нормализованной, если f(;) = 0. Каждая субмодулярная функция может быть нормализована посредством задания g(A) = f(A) — f(;). Функция f является монотонно возрастающей, если f (A) < f(B) для ACB. Обозначим Axf(A) = f(A [ fxg) -f(A).
иначе говоря,
Лемма 1. Функция f:2X!R является субмодулярной в том и только том случае, если Axf(A) < Axf(B) для любого x 2 X - B и A С B. Кроме того, f является монотонно возрастающей в том и только том случае, если Axf(A) < Axf(B) для любого x2B и ACB.


(1) <math>\Delta_x f(A) \ge \Delta_x f(B)</math>.


Доказательство. Если f является субмодулярной, то для x 2 X — B и ACJJ имеет место
f(A[fxg)+ > f((A [ fxg) [ B) + f(A [ fxg) \ B) = f(B[fxg) + f(
это означает, что
Axf(A) > Axf(B) :
(1)
к
к
Напротив, предположим, что свойство (1) выполняется для любого x 2 B и AC B. Пусть C и D – два множества и C n D = fx1,..x k g. Тогда
U
f(C [ D) - f(D) =
х|Ч)


Если функция f является монотонно возрастающей, то для ACB f(A) < f(B). Следовательно, для x 2 B,
Напротив, предположим, что свойство (1) выполняется для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>. Пусть C и D – два множества и <math>C \setminus D = \{ x_1, ..., x_k \}</math>. Тогда
A)xf{A) > 0 = Axf(B) :
 
Напротив, если Axf(A) > Axf(B) для любого x 2 B и А С B, тогда для любых x и A, Axf(A) > Axf(AU{x}) = 0, то есть f(A) < /(A U xg). Пусть B - A = fx 1..: ; xk g. Тогда
<math>f(C \cup D) - f(D) = \sum_{i=1}^k \Delta_{x_i} f(D \cup \{ x_1, ..., x_{i - 1} \} )</math> <math>\le \sum_{i=1}^k \Delta_{x_i} f((C \cap D) \cup \{ x_1, ..., x_{i - 1} \} )</math> <math>= f(C) - f(C \cap D)</math>.
f(A) </(AU
 
</(AU {xux2}) < ••• </
 
Если функция f является монотонно возрастающей, то <math>A \subseteq B \;</math> влечет <math>f(A) \le f(B)</math>. Следовательно, для <math>x \in B \;</math>,
 
 
<math>\Delta_x f(A) \ge 0 = \Delta_x f(B)</math>.
 
 
Напротив, если <math>\Delta_x f(A) \ge \Delta_x f(B)</math> для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>, тогда, для любых x и A, <math>\Delta_x f(A) \ge \Delta_x f(A \cup \{ x \} ) = 0</math>, то есть <math>f(A) \le f(A \cup \{ x \} )</math>. Пусть <math>B - A = \; \{ x_1, ..., x_k \}</math>. Тогда <math>f(A) \le f(A \cup \{ x_1 \} ) \le f(A \cup \{ x_1, x_2 \} ) \le ... \le f(B)</math>.
 
 
Рассмотрим теперь субмодулярность -q(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. Таким образом, лемма верна.


Рассмотрим теперь субмодулярность of—q(A). Лемма 2. Если A С B, то Ayq(A) > Ayq(B).


Доказательство. Заметим, что каждый связный компонент графа (v, D(B)) состоит из одного или нескольких связных компонентов графа (v, D(A)), поскольку A С B. Следовательно, количество связных компонентов (v, D(B)), доминируемых y, не превышает количества связных компонентов (v, D(A)), доминируемых y. Таким образом, лемма верна.
Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3].
Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3].
Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации
Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации
min    c(A) при условии    A 2 Cf :
 
min    c(A)
 
при условии    <math>A \in C_f</math>,
   
   
где c – неотрицательная целевая функция, определенная на 2X, и Cf = fCj f(C [ fxg) - f(C) = 0 для всех x 2 Xg. Существует жадный алгоритм, вычисляющий приближенное решение этой задачи.
где c – неотрицательная целевая функция, определенная на <math>2^X \;</math>, и <math>C_f = \{ C | f(C \cup \{ x \} ) - f(C) = 0</math> для всех <math>x \in X \} \;</math>. Существует жадный алгоритм, вычисляющий приближенное решение этой задачи.




Жадный алгоритм B:
'''Жадный алгоритм B:'''
входные данные – субмодулярная функция f и целевая функция c;
 
while существует x 2 E, такое, что Axf(A) > 0
Входные данные – субмодулярная функция f и целевая функция c;
do выбрать вершину x, максимизирующую Axf(A)/c(x), и задать
 
A^AU {x}\ return A.
<math>A \gets \empty ;</math>
 
'''while''' существует <math>x \in E \;</math>, такое, что <math>\Delta_x f(A) > 0 \;</math>
 
'''do''' выбрать вершину x, максимизирующую <math>\Delta_x f(A)/c(x) \;</math>, и задать <math>A \gets A \cup \{ x \}</math>
 
return A.




Строка 97: Строка 118:




Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации H(y) от оптимального, где у = maxx2E f(fxg).
'''Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации <math>H( \gamma) \;</math> от оптимального, где <math>\gamma = max_{x \in E} f( \{ x \} )</math>.'''
 
 
'''Теорема 2. Пусть f – нормализованная, монотонно возрастающая, субмодулярная функция, а c – неотрицательная целевая функция. Если в процессе выполнения жадного алгоритма B выбираемое значение x всегда удовлетворяет условию <math>\Delta_x f(A_{i - 1})/c(x) \ge 1</math>, тогда он дает приближенное решение с коэффициентом аппроксимации <math>1 + ln(f^* /opt) \; </math> от оптимального для вышеприведенной задачи минимизации, где <math>f^* = f(A^*) \;</math> и <math>opt = c(A^*) \;</math> для оптимального решения <math>A^* \;</math>.'''




Теорема 2. Пусть f – нормализованная, монотонно возрастающая, субмодулярная функция, а c – неотрицательная целевая функция. Если в процессе выполнения жадного алгоритма B выбираемое значение x всегда удовлетворяет условию Axf(Aj-i)/c(x) > 1, тогда он дает приближенное решение с коэффициентом аппроксимации 1 + ln(/* /opt) от оптимального для вышеприведенной задачи минимизации, где f* = f(A*) и opt = c(A*) для оптимального решения A*.
Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении:
Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении:
«Поскольку добавление C* к Ci уменьшит значение гармонической функции с f(Ci) до 2, значение f, уменьшенной на вершину из C*, будет в среднем составлять (f(Ci) 2)/opt. Но, согласно жадному правилу выбора xi + 1, должно иметь место
«Поскольку добавление <math>C^* \; </math> к <math>C_i \;</math> уменьшит значение гармонической функции с <math>f(C_i) \;</math> до 2, значение f, уменьшенной на вершину из <math>C^* \;</math>, будет в среднем составлять <math>(f(C_i) - 2)/opt \;</math>. Согласно жадному правилу выбора <math>x_i + 1 \;</math>, должно иметь место соотношение <math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt}</math>».




Чтобы убедиться в этом, рассмотрим утверждение более внимательно.
Чтобы убедиться в этом, рассмотрим утверждение более внимательно.
Пусть C* = {yi,... , уopt}; обозначим C* = {yx,... , у,}. Тогда
/(C,)-2=/(C,)-/(C,UC*)
opt
= J2lf(C,UC*_1)-f(ClUC*)]


Пусть <math>C^* = \{ y_i, ..., у_opt \} \;</math>; обозначим <math>C^*_j = \{ y_1, ..., y_j \} </math>. Тогда
<math>f(C_i) - 2 = f(C_i) - f(C_i \cup C^*) = \sum_{j=1}^{opt} [f(C_i \cup C^*_{j - 1}) - f(C_i \cup C^*_j) ] </math>,
где <math>C^*_0 = \empty \;</math>. Согласно жадному правилу выбора <math>x_i + 1 \;</math>, должно иметь место соотношение <math>f(C_i) - f(C_{i + 1}) \ge f(C_i) - f(C_i \cup \{ y_i \} )</math> для <math>j = 1, ..., opt \;</math>. Следовательно, для того, чтобы выполнялось
<math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt}</math>,
должно выполняться соотношение
(2) <math> - \Delta_{y_j} f(C_i) = f(C_i) - f(C_i \; \cup \; \{ y_j \} ) \ge f(C_i \; \cup \; C^*_{j - 1}) - f(C_i \; \cup \; C^*_j) = - \Delta_{y_j} f(C_i \; \cup\;  C^*_{j - 1})</math>.


(2)
для j = 1; : : : ; opt. Следовательно, необходимо -Ayjf(Ci)=f(Ci)-f(CiU{yj}),
чтобы выполнялось




Строка 120: Строка 152:




Отказ от субмодулярности
'''Отказ от субмодулярности'''
 
 
Отказ от субмодулярности – непростой вопрос, уже долгое время остающийся открытым. Однако это возможно благодаря наблюдению Дю и коллег относительно утверждения (2) в [1]: субмодулярность –f применяется для приращения вершины <math>y_j \;</math>, принадлежащей к оптимальному решению <math>C^* \;</math>.
 
 
В силу гибкости упорядочения вершин <math>y_j \;</math> можно организовать его таким образом, чтобы контролировать величину <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1} )</math>. Это позволит успешно справиться с задачей MCDS.
 


Отказ от субмодулярности – непростой вопрос, уже долгое время остающийся открытым. Однако это возможно благодаря наблюдению Дю и коллег относительно утверждения (2) в [1]: субмодулярность –f применяется для приращения вершины yj, принадлежащей к оптимальному решению C*.
'''Лемма 3'''. Пусть значения <math>y_j \;</math> упорядочены таким образом, что для любого <math>j = 1, ..., opt \;</math> последовательность <math>\{ y_1, ..., y_j \} \;</math> порождает связный подграф. Тогда <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>.
В силу гибкости упорядочения yj можно организовать его таким образом, чтобы контролировать Ayjfid) - Ayjf(d U C*_x). Это позволит успешно справиться с задачей MCDS.




Лемма 3. Пусть значения yj упорядочены таким образом, что для любого j = 1..: ; opt, fy1..: ; yjg порождает связный подграф. Тогда
{ [ Cj_r) <


''Доказательство''. Поскольку все <math>y_1, ..., y_{j - 1} \;</math> являются связными, <math>y_j \;</math> может доминировать не более одного дополнительного связного компонента в подграфе, порожденном <math>C_{i - 1} \cup C^*_{j - 1} \;</math> , относительно подграфа, порожденного <math>C_{i - 1} \;</math>. Следовательно, <math>\Delta_{y_j} p(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>.


Доказательство. Поскольку все y 1..: ; y^-\ являются связными, yj может доминировать не более одного дополнительного связного компонента в подграфе, порожденном C,_i [ C*_x, относительно подграфа, порожденного c i — 1.


Более того, поскольку –q является субмодулярной, <math>\Delta_{y_j} q(C_i) - \Delta_{y_j} q(C_i \cup C^*_{j - 1}) \le 0</math>.


Более того, поскольку–q является субмодулярной,
Таким образом,


где C* = ;. Но, согласно жадному правилу выбора xi + 1, должно иметь место
Таким образом, <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>.
f(Ci) -/(Q+1) > f(Ci) -/(C, U yjg)


Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3
 
Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3, <math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} - 1</math>.


   
   
Следовательно,
Следовательно, <math>f(C_{i + 1}) - 2 - opt \le (f(C_i) - 2 + opt) \left ( 1 - \frac{1}{opt} \right ) \le (f( \empty ) - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1} = (n - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1}</math>,
f(Ci+1) -2-opt< (f(Ci) - 2 + opt) 1 - 1 <(/(0)-2-o,f)(l--L)H
= (n - 2 - opt) ( 1 - 1 opt
where n = jVj. Note that 1 - 1/opt < е~11оР(. Hence,
f(Ci) -2-opt<(n- 2)e~ilopt : Choose i such that f(Ci) > 2 • opt + 2 > f(Ci+1). Then
opt <{n-2)e-ilopt and
g - i < 2 ■ opt :
Therefore,
и-2 opt
< opt(2 +ln<5)
g < 2 ■ opt + i < opt  2 + ln
где S – максимальная степень исходного графа G.


где <math>n = |V| \;</math>. Заметим, что <math>1 - 1/opt \le e^{-1/opt}</math>. Таким образом, <math>f(C_i) - 2 - opt \le (n - 2) e^{ -i/opt}</math>.
Выберем такое <math>i \;</math>, чтобы выполнялось <math>f(C_i) \ge 2 \cdot opt + 2 > f(C_{i+1})</math>. Тогда <math>opt \le (n - 2) e^{ -i/opt}</math> и <math>g - i \le 2 \cdot opt \;</math>.
Следовательно, <math>g \le 2 \cdot opt + i \le opt \left ( 2 + ln \frac {n - 2} {opt} \right ) \le opt (2 + ln \; \delta)</math>, где <math>\delta \;</math> – максимальная степень исходного графа G.


== Применение ==
== Применение ==
Строка 161: Строка 193:


== Открытые вопросы ==
== Открытые вопросы ==
Можно ли определить коэффициент эффективности 1 + H(S) для жадного алгоритма B в задаче MCDS? Ответ неизвестен. Неизвестно также, как получить четкое обобщение теоремы 1.
Можно ли определить коэффициент эффективности <math>1 + H( \delta) \;</math> для жадного алгоритма B в задаче MCDS? Ответ неизвестен. Неизвестно также, как получить четкое обобщение теоремы 1.
 


== См. также ==
== См. также ==
* ''[[Связное доминирующее множество]]
* ''[[Связное доминирующее множество]]
* ''[[Алгоритмы локального поиска для kSAT]]
* ''[[Алгоритмы локального поиска для k-КНФ]]
* ''[[Деревья Штейнера]]
* ''[[Деревья Штейнера]]


== Литература ==
== Литература ==

Текущая версия от 14:41, 1 октября 2023

Ключевые слова и синонимы

Техника анализа жадной аппроксимации


Постановка задачи

Рассмотрим граф G = (V, E). Множество C множества V называется доминирующим множеством, если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется связным доминирующим множеством. Пусть дан связный граф G; необходимо найти связное доминирующее множество минимальной мощности. Эта задача имеет обозначение MCDS и является NP-полной. Ее оптимальное решение называется минимальным связным доминирующим множеством. Рассмотрим жадную аппроксимацию с гармонической функцией f.


Жадный алгоритм A:

[math]\displaystyle{ C \leftarrow \empty }[/math]

while [math]\displaystyle{ f(C) \gt 2 ;\ }[/math] do

выбрать вершину x так, чтобы максимизировать [math]\displaystyle{ f(C) - f(C \cup \{ x \} ) }[/math] и [math]\displaystyle{ C \leftarrow C \cup \{ x \} }[/math]; вывести C.

Здесь f определяется как f(C) = p(C) + q(C), где p(C) – количество связных компонент подграфа, порожденного C, а q(C) – количество связных компонент подграфа с множеством вершин V и множеством дуг [math]\displaystyle{ \{ (u, v) \in E | u \in C }[/math] или [math]\displaystyle{ v \in C \} }[/math]. Функция f обладает важным свойством: C является связным доминирующим множеством в том и только том случае, если f(C) = 2.


Если C является связным доминирующим множеством, то p(C) = q(C) = 1 и, следовательно, f(C) = 2. Напротив, предположим, что [math]\displaystyle{ f(C \cup \{ x \}) = 2 }[/math]. Поскольку [math]\displaystyle{ p(C) \ge 1 \; }[/math] и [math]\displaystyle{ q(C) \ge 1 \; }[/math], должно иметь место p(C) = q(C) = 1, из чего следует, что C является связным доминирующим множеством. Функция f обладает еще одним свойством на графе G, имеющем не менее трех вершин: если f(C) > 2, то существует [math]\displaystyle{ x \in V \; }[/math], такое, что [math]\displaystyle{ f(C) - f(C \cup \{ x \} ) \gt 0 }[/math]. Фактически, для [math]\displaystyle{ C \ne \empty \; }[/math], поскольку G является связным графом, имеющим не менее трех вершин, должна существовать вершина x со степенью не ниже двух, и для такой вершины x выполняется [math]\displaystyle{ f(C \cup \{ x \}) \lt f(C) }[/math]. Для случая [math]\displaystyle{ C \ne \empty \; }[/math] рассмотрим связную компоненту подграфа, порожденного C. Обозначим как B его множество вершин, являющееся подмножеством C. Для каждой вершины y, смежной с B, в случае, если y смежна с вершиной, не смежной с B и не принадлежащей к C, то [math]\displaystyle{ p(C \cup \{ y \} ) \lt p(C) }[/math] и [math]\displaystyle{ q(C \cup \{ y \} ) \le q(C) }[/math]; если вершина y смежна с вершиной из множества C — B, то [math]\displaystyle{ p(C \cup \{ y \} ) \le p(C) }[/math] и [math]\displaystyle{ q(C \cup \{ y \} ) \lt q(C) }[/math].


Проведем некоторый анализ вышеприведенного жадного алгоритма: Пусть [math]\displaystyle{ x_1, ..., x_g \; }[/math] – вершины, выбранные жадным алгоритмом в порядке их появления в алгоритме. Введем обозначение [math]\displaystyle{ C_i = \{ x_1, ... , x_i \} \; }[/math]. Пусть [math]\displaystyle{ C^* = \{ y_1, ..., y_{opt} \} \; }[/math] – минимальное связное доминирующее множество. Поскольку добавление [math]\displaystyle{ C^* \; }[/math] к [math]\displaystyle{ C_i \; }[/math] уменьшит значение гармонической функции с [math]\displaystyle{ f(C_i) \; }[/math] до 2, значение f, уменьшенной на вершину из [math]\displaystyle{ C^* \; }[/math], будет в среднем составлять [math]\displaystyle{ (f(C_i) - 2)/opt \; }[/math]. Но, согласно жадному правилу выбора [math]\displaystyle{ x_i + 1 \; }[/math], должно иметь место соотношение [math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} }[/math].


Следовательно, [math]\displaystyle{ f(C_{i + 1}) - 2 \le (f(C_i) - 2) (1 - \frac{1}{opt}) \le (f( \empty ) - 2) (1 - \frac{1}{opt})^{i + 1} = (n - 2) (1 - \frac{1}{opt})^{i + 1} }[/math],


где [math]\displaystyle{ n = |V| \; }[/math]. Заметим, что [math]\displaystyle{ 1 - 1/ opt \le e^{- 1/opt} }[/math]. Следовательно, [math]\displaystyle{ f(C_i) - 2 \le (n - 2) e^{-i/opt} }[/math].


Выберем такое значение i, что [math]\displaystyle{ f(C_i) \ge opt + 2 \gt f(C_{i+1}) }[/math]. Тогда [math]\displaystyle{ opt \le (n - 2) e^{-i/opt} }[/math] и [math]\displaystyle{ g - i \le opt \; }[/math].


Таким образом, [math]\displaystyle{ g \le opt + i \le opt \left ( 1 + ln \frac{n - 2}{opt} \right ) }[/math].


Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа жадного алгоритма аппроксимации с несубмодулярной гармонической функцией.

Основные результаты

Роль субмодулярности


Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств [math]\displaystyle{ 2^X \; }[/math], то есть семействе всех подмножеств X. Функция f называется субмодулярной, если для любых двух подмножеств A и B в [math]\displaystyle{ 2^X \; }[/math] выполняется неравенство


[math]\displaystyle{ f(A) + f(B) \ge f(A \cap B) + f(A \cup B) }[/math].


В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция -q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций.


Субмодулярная функция f называется нормализованной, если [math]\displaystyle{ f( \empty ) = 0 }[/math]. Каждая субмодулярная функция может быть нормализована посредством задания [math]\displaystyle{ g(A) = f(A) - f( \empty ) }[/math]. Функция f является монотонно возрастающей, если [math]\displaystyle{ f(A) \le f(B) \; }[/math] в случае [math]\displaystyle{ A \subset B \; }[/math]. Обозначим [math]\displaystyle{ \Delta_x f(A) = f(A \cup \{ x \} ) - f(A) }[/math].


Лемма 1. Функция [math]\displaystyle{ f: 2^X \to R }[/math] является субмодулярной в том и только том случае, если [math]\displaystyle{ \Delta_x f(A) \le \Delta_x f(B) }[/math] для любого [math]\displaystyle{ x \in X - B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math]. Кроме того, f является монотонно возрастающей в том и только том случае, если [math]\displaystyle{ \Delta_x f(A) \le \Delta_x f(B) }[/math] для любого [math]\displaystyle{ x \in B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math].


Доказательство. Если f является субмодулярной, то для [math]\displaystyle{ x \in X - B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math] имеет место соотношение

[math]\displaystyle{ 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]\displaystyle{ \Delta_x f(A) \ge \Delta_x f(B) }[/math].


Напротив, предположим, что свойство (1) выполняется для любого [math]\displaystyle{ x \in B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math]. Пусть C и D – два множества и [math]\displaystyle{ C \setminus D = \{ x_1, ..., x_k \} }[/math]. Тогда

[math]\displaystyle{ f(C \cup D) - f(D) = \sum_{i=1}^k \Delta_{x_i} f(D \cup \{ x_1, ..., x_{i - 1} \} ) }[/math] [math]\displaystyle{ \le \sum_{i=1}^k \Delta_{x_i} f((C \cap D) \cup \{ x_1, ..., x_{i - 1} \} ) }[/math] [math]\displaystyle{ = f(C) - f(C \cap D) }[/math].


Если функция f является монотонно возрастающей, то [math]\displaystyle{ A \subseteq B \; }[/math] влечет [math]\displaystyle{ f(A) \le f(B) }[/math]. Следовательно, для [math]\displaystyle{ x \in B \; }[/math],


[math]\displaystyle{ \Delta_x f(A) \ge 0 = \Delta_x f(B) }[/math].


Напротив, если [math]\displaystyle{ \Delta_x f(A) \ge \Delta_x f(B) }[/math] для любого [math]\displaystyle{ x \in B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math], тогда, для любых x и A, [math]\displaystyle{ \Delta_x f(A) \ge \Delta_x f(A \cup \{ x \} ) = 0 }[/math], то есть [math]\displaystyle{ f(A) \le f(A \cup \{ x \} ) }[/math]. Пусть [math]\displaystyle{ B - A = \; \{ x_1, ..., x_k \} }[/math]. Тогда [math]\displaystyle{ f(A) \le f(A \cup \{ x_1 \} ) \le f(A \cup \{ x_1, x_2 \} ) \le ... \le f(B) }[/math].


Рассмотрим теперь субмодулярность -q(A).


Лемма 2. Если [math]\displaystyle{ A \subset B \; }[/math], то [math]\displaystyle{ \Delta_y q(A) \ge \Delta_y q(B) }[/math].


Доказательство. Заметим, что каждый связный компонент графа (v, D(B)) состоит из одного или нескольких связных компонентов графа (v, D(A)), поскольку [math]\displaystyle{ A \subset B \; }[/math]. Следовательно, количество связных компонентов (v, D(B)), доминируемых y, не превышает количества связных компонентов (v, D(A)), доминируемых y. Таким образом, лемма верна.


Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3].

Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации

min c(A)

при условии [math]\displaystyle{ A \in C_f }[/math],

где c – неотрицательная целевая функция, определенная на [math]\displaystyle{ 2^X \; }[/math], и [math]\displaystyle{ C_f = \{ C | f(C \cup \{ x \} ) - f(C) = 0 }[/math] для всех [math]\displaystyle{ x \in X \} \; }[/math]. Существует жадный алгоритм, вычисляющий приближенное решение этой задачи.


Жадный алгоритм B:

Входные данные – субмодулярная функция f и целевая функция c;

[math]\displaystyle{ A \gets \empty ; }[/math]

while существует [math]\displaystyle{ x \in E \; }[/math], такое, что [math]\displaystyle{ \Delta_x f(A) \gt 0 \; }[/math]

do выбрать вершину x, максимизирующую [math]\displaystyle{ \Delta_x f(A)/c(x) \; }[/math], и задать [math]\displaystyle{ A \gets A \cup \{ x \} }[/math]

return A.


Следующие два результата хорошо известны.


Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации [math]\displaystyle{ H( \gamma) \; }[/math] от оптимального, где [math]\displaystyle{ \gamma = max_{x \in E} f( \{ x \} ) }[/math].


Теорема 2. Пусть f – нормализованная, монотонно возрастающая, субмодулярная функция, а c – неотрицательная целевая функция. Если в процессе выполнения жадного алгоритма B выбираемое значение x всегда удовлетворяет условию [math]\displaystyle{ \Delta_x f(A_{i - 1})/c(x) \ge 1 }[/math], тогда он дает приближенное решение с коэффициентом аппроксимации [math]\displaystyle{ 1 + ln(f^* /opt) \; }[/math] от оптимального для вышеприведенной задачи минимизации, где [math]\displaystyle{ f^* = f(A^*) \; }[/math] и [math]\displaystyle{ opt = c(A^*) \; }[/math] для оптимального решения [math]\displaystyle{ A^* \; }[/math].


Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении: «Поскольку добавление [math]\displaystyle{ C^* \; }[/math] к [math]\displaystyle{ C_i \; }[/math] уменьшит значение гармонической функции с [math]\displaystyle{ f(C_i) \; }[/math] до 2, значение f, уменьшенной на вершину из [math]\displaystyle{ C^* \; }[/math], будет в среднем составлять [math]\displaystyle{ (f(C_i) - 2)/opt \; }[/math]. Согласно жадному правилу выбора [math]\displaystyle{ x_i + 1 \; }[/math], должно иметь место соотношение [math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} }[/math]».


Чтобы убедиться в этом, рассмотрим утверждение более внимательно.

Пусть [math]\displaystyle{ C^* = \{ y_i, ..., у_opt \} \; }[/math]; обозначим [math]\displaystyle{ C^*_j = \{ y_1, ..., y_j \} }[/math]. Тогда


[math]\displaystyle{ f(C_i) - 2 = f(C_i) - f(C_i \cup C^*) = \sum_{j=1}^{opt} [f(C_i \cup C^*_{j - 1}) - f(C_i \cup C^*_j) ] }[/math],


где [math]\displaystyle{ C^*_0 = \empty \; }[/math]. Согласно жадному правилу выбора [math]\displaystyle{ x_i + 1 \; }[/math], должно иметь место соотношение [math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge f(C_i) - f(C_i \cup \{ y_i \} ) }[/math] для [math]\displaystyle{ j = 1, ..., opt \; }[/math]. Следовательно, для того, чтобы выполнялось


[math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} }[/math],


должно выполняться соотношение


(2) [math]\displaystyle{ - \Delta_{y_j} f(C_i) = f(C_i) - f(C_i \; \cup \; \{ y_j \} ) \ge f(C_i \; \cup \; C^*_{j - 1}) - f(C_i \; \cup \; C^*_j) = - \Delta_{y_j} f(C_i \; \cup\; C^*_{j - 1}) }[/math].


Для (2) требуется субмодулярность –f. Однако, к сожалению, –f не является субмодулярной. Контрпример можно найти в работе [3]. Именно поэтому анализ жадного алгоритма A в разделе «Постановка задачи» неверен.


Отказ от субмодулярности


Отказ от субмодулярности – непростой вопрос, уже долгое время остающийся открытым. Однако это возможно благодаря наблюдению Дю и коллег относительно утверждения (2) в [1]: субмодулярность –f применяется для приращения вершины [math]\displaystyle{ y_j \; }[/math], принадлежащей к оптимальному решению [math]\displaystyle{ C^* \; }[/math].


В силу гибкости упорядочения вершин [math]\displaystyle{ y_j \; }[/math] можно организовать его таким образом, чтобы контролировать величину [math]\displaystyle{ \Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1} ) }[/math]. Это позволит успешно справиться с задачей MCDS.


Лемма 3. Пусть значения [math]\displaystyle{ y_j \; }[/math] упорядочены таким образом, что для любого [math]\displaystyle{ j = 1, ..., opt \; }[/math] последовательность [math]\displaystyle{ \{ y_1, ..., y_j \} \; }[/math] порождает связный подграф. Тогда [math]\displaystyle{ \Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1 }[/math].


Доказательство. Поскольку все [math]\displaystyle{ y_1, ..., y_{j - 1} \; }[/math] являются связными, [math]\displaystyle{ y_j \; }[/math] может доминировать не более одного дополнительного связного компонента в подграфе, порожденном [math]\displaystyle{ C_{i - 1} \cup C^*_{j - 1} \; }[/math] , относительно подграфа, порожденного [math]\displaystyle{ C_{i - 1} \; }[/math]. Следовательно, [math]\displaystyle{ \Delta_{y_j} p(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1 }[/math].


Более того, поскольку –q является субмодулярной, [math]\displaystyle{ \Delta_{y_j} q(C_i) - \Delta_{y_j} q(C_i \cup C^*_{j - 1}) \le 0 }[/math].


Таким образом, [math]\displaystyle{ \Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1 }[/math].


Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3, [math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} - 1 }[/math].


Следовательно, [math]\displaystyle{ f(C_{i + 1}) - 2 - opt \le (f(C_i) - 2 + opt) \left ( 1 - \frac{1}{opt} \right ) \le (f( \empty ) - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1} = (n - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1} }[/math],


где [math]\displaystyle{ n = |V| \; }[/math]. Заметим, что [math]\displaystyle{ 1 - 1/opt \le e^{-1/opt} }[/math]. Таким образом, [math]\displaystyle{ f(C_i) - 2 - opt \le (n - 2) e^{ -i/opt} }[/math].


Выберем такое [math]\displaystyle{ i \; }[/math], чтобы выполнялось [math]\displaystyle{ f(C_i) \ge 2 \cdot opt + 2 \gt f(C_{i+1}) }[/math]. Тогда [math]\displaystyle{ opt \le (n - 2) e^{ -i/opt} }[/math] и [math]\displaystyle{ g - i \le 2 \cdot opt \; }[/math].


Следовательно, [math]\displaystyle{ g \le 2 \cdot opt + i \le opt \left ( 2 + ln \frac {n - 2} {opt} \right ) \le opt (2 + ln \; \delta) }[/math], где [math]\displaystyle{ \delta \; }[/math] – максимальная степень исходного графа G.

Применение

У вышеприведенной техники множество приложений, включая анализ итеративных 1-деревьев Штейнера в задаче нахождения минимального дерева Штейнера и анализ жадных аппроксимаций для задач оптимизации в оптических сетях [4] и беспроводных сетях [3].


Открытые вопросы

Можно ли определить коэффициент эффективности [math]\displaystyle{ 1 + H( \delta) \; }[/math] для жадного алгоритма B в задаче MCDS? Ответ неизвестен. Неизвестно также, как получить четкое обобщение теоремы 1.

См. также

Литература

1. Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.-J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008 3. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, Hoboken (1999) 4. Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325-330 (2004) 5. Ruan, L., Wu, W.: Broadcast routing with minimum wavelength conversion in WDM optical networks. J. Comb. Optim. 9 223-235 (2005)