Изменения
fix
== Постановка задачи однокритериальной оптимизации==
<tex>S</tex> {{- --}} пространство решений (дискретно),
<tex>f : S \rightarrow \mathbb{R}</tex> {{- --}} оценочная функция.
Задача: найти <tex>s \in S : f(s) \rightarrow max </tex>. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.
x <tex>\leftarrow</tex> random
while(true)
x' <tex>\leftarrow</tex> neiborneighbour(x)
f(x') <tex>\geq</tex> f(x) <tex> \Rightarrow </tex> x = x'
Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:
<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>.
Отсюда по [[#theorem1|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.
=== (1+1)-ES для MST ===
==Источники==
