4551
правка
Жадные алгоритмы аппроксимации: различия между версиями
Материал из WEGA
Жадные алгоритмы аппроксимации (посмотреть исходный код)
Версия от 00:38, 24 апреля 2015
, 24 апреля 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 180: | Строка 180: | ||
где <math>n = |V| \;</math>. Заметим, что <math>1 - 1/opt \le e^{-1/opt}</math>. Таким образом, | |||
f(Ci) -2-opt<(n- 2)e~ilopt : Choose i such that f(Ci) > 2 • opt + 2 > f(Ci+1). Then | 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 | opt <{n-2)e-ilopt and | ||
