Изменения
→Оценка для RMHC
Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Royal Road функции <tex> R</tex>, с <tex>N</tex> блоками и <tex>K</tex> схемами.
Обозначим время нахождения первого блока за <tex>E(K, 1)</tex>, <tex>O(E(K, 1) \approx ) = 2^K </tex>
Время нахождения второго блока <tex>E(K, 2)=E(K, 1) + E(K, 1)[KN/(KN-K)]</tex>
<tex>E(K, N)=E(K, 1)+E(K, 1)\frac{N}{N-1}+...+E(K, 1)\frac{N}{N-(N-1)}=E(K, 1)N[1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{N}]</tex>
<tex>E(K, N) = E(K, 1) N (\log N + \gamma)</tex>, где <tex>\gamma</tex> — [http://ru.wikipedia.org/wiki/Постоянная_Эйлера_—_Маскерони постоянная Эйлера]
Таким образом, можно получить оценку:
<tex>E(K, N) \approx = O(2^K N (\log N + \gamma)</tex>, где <tex>\gamma</tex> — [http://ru.wikipedia.org/wiki/Постоянная_Эйлера_—_Маскерони постоянная Эйлера]
=== IGA (Idealized Genetic Algorithm) ===
