Изменения
→(1+1)-ES для MST
На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>.
В качестве оценочной функции возьмем <tex>w(T) + c_C_{penalty} (|T| - n + 1) + {C_{penalty}}^2 ({\#comp} - 1) </tex>, где <tex>\#comp</tex> {{---}} число компонент связности в текущем <tex> T </tex>, а <tex> C_{penalty} > m w_{max}</tex>, где <tex>w_{max}</tex> {{---}} максимальный вес ребра.
{{Теорема
|proof=
Разобьем доказательство теоремы на три этапа: получение связного подграфа, получение остовного дерева и получение минимального остовного дерева. 1) Пусть Покажем, что после <tex>O(m \log m)</tex> итераций <tex>T</tex> связно:.Пусть <tex>X_t = {\#comp} - 1</tex> после итерации <tex>t</tex>.
Если <tex>X_{t - 1} = k</tex>, то существует как минимум <tex>k</tex> ребер, которые не входят в <tex>T</tex> и добавление которых уменьшает <tex>X_t</tex>. По аналогии с решением задачи OneMax получаем:
<tex>E(X_t| X_{t-1} = k) \leq (1 - \frac{1}{e m})k</tex>. Применяя [[#theorem1|теорему о дрифте]], получаем требуемый результат. 2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях, так как <tex>C_{penalty}</tex> достаточно велико. Покажем, что после <tex>O(m \log m)</tex> итераций <tex>T</tex> является деревом, то есть <tex>|T| = n - 1</tex>, где <tex>n = |V|</tex>.Пусть <tex>X_t = |T| - (n - 1)</tex> после итерации <tex>t</tex> (количество "лишних" ребер в <tex>T</tex>). Если <tex>X_{t - 1} = k</tex>, то существует как минимум <tex>k</tex> ребер, удаление которых из <tex>T</tex> уменьшает <tex>X_t</tex>. По аналогии с решением задачи OneMax получаем: <tex>E(X_t | X_{t-1} = k) \leq (1 - \frac{1}{e m})k</tex>.
Применяя [[#theorem1|теорему о дрифте]], получаем требуемый результат.
Пусть <tex> X_t </tex> для <tex>T</tex>{{---}} это разница между весом текущего дерева и оптимального: <tex> X_t = w(T) - w_{opt} </tex> после итерации <tex>t</tex>.
С верояностью <tex>\geq 1/e m^2</tex>, одна итерация обменяет в точности ребра <tex>e_i</tex> и <tex>e'_i</tex>. Тогда:
<tex>E(X_t| X_{t-1} = D) \leq D - \sum_{i} (1/e m^2) (w(e_i) - w(e'_i))= (1 - 1/e m^2) D </tex>
Используем [[#theorem1|теорему о дрифте]], учитывая, что
