15
правок
Изменения
м
→Оценка времени решения MST
<tex> \sum_{k=0}^{n-1} \frac{e n}{n-k} = e n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) </tex>
==Оценка времени решения MSTработы алгоритмов с использованием Drift Analysis==
===Drift theorem===
Тогда <tex>T = \min\{t \in \mathbb{N}_0 | X_t = 0\}</tex> удовлетворяет
<tex>E(T) \leq ( \frac{1/}{\delta)}(\ln(X_0) + 1)</tex>
<tex>\forall c > 0, Pr(T > ( \frac{1/}{\delta)}(\ln(X_0) + c)) \leq e ^ {-c}</tex> ===RMHC для OneMax===Пусть <tex>X_t</tex> --- число нулевых бит после итерации <tex>i</tex>: <tex>X_t = f_{opt} - f(X_t)</tex> Пусть <tex>X_{t-1} = k</tex>. Тогда <tex>E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-1}{n} = k (1 - \frac{1}{n})</tex>, то есть <tex> \delta = \frac{1}{n}</tex>. Отсюда по теореме о дрифте, с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>. ===(1+1)-ES для OneMax===Пусть <tex>X_t</tex> --- число нулевых бит после итерации <tex>i</tex>: <tex>X_t = f_{opt} - f(X_t)</tex> Пусть <tex>X_{t-1} = k</tex>. Тогда вероятность перевернуть один нулевых битов равна <tex>k \frac{1}{n} ( 1 - \frac{1}{n})^{n-1} \geq \frac{k}{e n} </tex>. Отсюда <tex>E(X_t | X_{t-1} = k) \leq (k-1)\frac{k}{e n} + k (1 - \frac{k}{e n}) = k (1 - \frac{1}{e n})</tex>, то есть <tex> \delta = \frac{1}{e n}</tex>. Отсюда по теореме о дрифте, с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.
=== (1+1)-ES для MST ===
Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1</tex>, если <tex>e \in E'</tex>, и <tex>x_e = 0</tex> в обратном случае.
Мутация: независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>.
Фитнес-функция: <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> --- число компонент связности в текущем <tex> T </tex>.
'''Теорема. [Neumann, Wegener (2004)]:''' Ожидаемое время работы (1+1)-EA для задачи MST равно <tex>O(m^2 \log(m w_{max}))</tex>, где <tex>w_{max}</tex> --- максимальный вес ребра.
'''Доказательство. '''
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>:
<tex>E(X_t) \leq (1 - \frac{1}{e m})k</tex>
следовательно <tex>D = \sum_{i} (w(e_i) - w(e'_i))</tex>, и для всех <tex>i</tex>
<tex>T_i = T - e_i + e'_i</tex> --- основное остовное дерево с <tex>w(T_i) < w(T)</tex>.
С верояностью <tex>\geq 1/e m^2</tex>, одна итерация обменяет в точности ребра <tex>e_i</tex> и <tex>e'_i</tex>.
