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

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

115 байт добавлено , 23 апреля 2015

4551

правка

@@ Строка 129: / Строка 129: @@
 Чтобы убедиться в этом, рассмотрим утверждение более внимательно.
-Пусть C* = {yi,... , уopt}; обозначим C* = {yx,... , у,}. Тогда
-/(C,)-2=/(C,)-/(C,UC*)
+Пусть <math>C^* = \{ y_i, ..., у_opt \} \;</math>; обозначим <math>C^*_j = \{ y_1, ..., y_j \} </math>. Тогда
-opt
-= J2lf(C,UC*_1)-f(ClUC*)]
+<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>
 (2)
 для j = 1; : : : ; opt. Следовательно, необходимо -Ayjf(Ci)=f(Ci)-f(CiU{yj}),
 чтобы выполнялось