Изменения
→Введение
=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <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> — количество ребер в графе. Время работы эволюционных алгоритмов измеряется в количестве вычислений функции приспособленности, а время оптимального алгоритма — в элементарных операциях.
После обзора предыдущих методов опишем представление графа, затем то, как устроена функция приспособленности и операция мутации, а потом адаптируем RLS и (1+1) EA стратегии для нашего случая.
Эйлерову циклу, проходящему по ребрам (2, 6, 7, 4, 3, 8, 5, 1) будет соответстовать множество <tex>M</tex> такого вида:
<tex>M_a = {(b,ec); (ce,d)}</tex>
<tex>M_b = {(a,f)}</tex>
}}
Для случая, когда <tex>M</tex> — разбиение графа на несколько циклов, время работы алгоритма для стратегии, ориентированной на ребра будет <tex>O(m \cdot log \, m )</tex>. Получить такое разбриение можно разбив вершины во всех списках смежности на пары случайным образом.
=== Литература ===
<references/>
