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

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

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

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

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




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


== Основные результаты ==
== Основные результаты ==
Строка 142: Строка 142:




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




(2)
(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>.




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




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


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


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


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


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


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


'''Лемма 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>.


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


где C* = ;. Но, согласно жадному правилу выбора xi + 1, должно иметь место
f(Ci) -/(Q+1) > f(Ci) -/(C, U yjg)


Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3
''Доказательство''. Поскольку все <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>.
 
 
Более того, поскольку –q является субмодулярной, <math>\Delta_{y_j} q(C_i) - \Delta_{y_j} q(C_i \cup C^*_{j - 1}) \le 0</math>.
 
 
Таким образом, <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>.
 
 
Теперь можно провести корректный анализ жадного алгоритма 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 :
Выберем такое <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>.
Therefore,
 
и-2 opt
 
< opt(2 +ln<5)
Следовательно, <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.
g < 2 ■ opt + i < opt   2 + ln
где S – максимальная степень исходного графа G.


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


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


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


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

правка

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

Навигация