Изменения
Нет описания правки
=== Введение ===
Способ нахождения Эйлерова эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m*log(m))</tex> (до недавнего времени лучшим считался результат <tex>O(m^2*log(m))</tex>). При этом оптимальный (не эволюционный) алгоритм работает за <tex>O(m)</tex>. Здесь и далее <tex>m</tex> — количество ребер в графе.
=== Постановка задачи ===
<tex>p = \frac{1} {2\delta d(G)m} </tex>
==== Стратегии RLS и (1+1) EA ====
Эволюционный алгоритм поиска эйлерова цикла в графе работает следующим образом. Размер популяции возьмем 1; представление графа, операция мутации и фитнес-функция будут такими, как описано выше. Начальное заполнение множества <tex>M</tex> можно сделать случаным образом или оставить пустым, на время работы алгоритма это не влияет.
Стратегия Randomized local search будет работать так: на каждом шаге к текущему индивиду (он один, так как рамер популяции 1) применяется операция мутации. Если полученный индивид лучше текущего, он выбирается для дальнейшей работы, в противном случае ничего не происходит. Алгоритм работает до тех пор, пока фитнес функция не минимизирована.
Псевдокод:
Initialize(M)
while (f(M) > 1) do
M′:=φ(M)
if f(M′) ≤ f(M)
then M := M′
==== Время работы алгоритма ====
