Изменения

Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot \log \, m )</tex><ref>Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers. Proceeding GECCO '07 Proceedings of the 9th annual conference on Genetic and evolutionary computation, 1203-1210 (2007)</ref> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot \log\,m)</tex>)<ref>B. Doerr, C. Klein, and T. Storch. Faster evolutionary algorithms by superior graph representation. In Proc. of the 2007 IEEE Symposium on Foundations of Computational Intelligence (FOCI), 245–250 (2007).</ref>. При этом оптимальный (не эволюционный) [[Алгоритм построения Эйлерова цикла|алгоритм]] работает за <tex>O(m)</tex>. Здесь и далее <tex>m</tex> — количество ребер в графе. Время работы эволюционных алгоритмов измеряется в количестве вычислений функции приспособленности, а время оптимального алгоритма — в элементарных операциях.

<tex>M_a = {(b,ec); (ce,d)}</tex>