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

Перейти к навигации Перейти к поиску

Жадные алгоритмы аппроксимации (посмотреть исходный код)

Версия от 14:41, 1 октября 2023

3664 байта добавлено ,  1 октября 2023
м
нет описания правки
мНет описания правки
 
(не показано 27 промежуточных версий этого же участника)
Строка 34: Строка 34:




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




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




Доказательство. Если f является субмодулярной, то для x 2 X — B и ACJJ имеет место
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция -q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций.
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,
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. Тогда
f(A) </(AU
</(AU {xux2}) < ••• </


Рассмотрим теперь субмодулярность of—q(A). Лемма 2. Если A С B, то Ayq(A) > Ayq(B).
Субмодулярная функция 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>.
 
 
''Доказательство''. Если 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) выполняется для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>. Пусть C и D – два множества и <math>C \setminus D = \{ x_1, ..., x_k \}</math>. Тогда
 
<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 является монотонно возрастающей, то <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. Таким образом, лемма верна.
 


Доказательство. Заметим, что каждый связный компонент графа (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:'''
 
Входные данные – субмодулярная функция f и целевая функция c;
 
<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>


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




Строка 94: Строка 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}),
чтобы выполнялось




Строка 117: Строка 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.
 
 
'''Лемма 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>.


Отказ от субмодулярности – непростой вопрос, уже долгое время остающийся открытым. Однако это возможно благодаря наблюдению Дю и коллег относительно утверждения (2) в [1]: субмодулярность –f применяется для приращения вершины yj, принадлежащей к оптимальному решению C*.
В силу гибкости упорядочения yj можно организовать его таким образом, чтобы контролировать Ayjfid) - Ayjf(d U C*_x). Это позволит успешно справиться с задачей MCDS.




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




Доказательство. Поскольку все 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 является субмодулярной,
Таким образом, <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>.
Таким образом,


где C* = ;. Но, согласно жадному правилу выбора xi + 1, должно иметь место
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,
где <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>.
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>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.


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


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


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


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

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10883...15233

Навигация