Изменения

Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <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 computationPages , 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), pages 245–250(2007). IEEE, 2007.</ref>. При этом оптимальный (не эволюционный) алгоритм работает за <tex>O(m)</tex>. Здесь и далее <tex>m</tex> — количество ребер в графе.