Эволюционные алгоритмы поиска эйлерова цикла в графе

Постановка задачи

Определение:

Эйлеров цикл в графе — это путь, проходящий по всем рёбрам графа ровно по одному разу.

Задача — для заданного графа найти такой путь. Заметим, что это возможно тогда и только тогда, когда граф связный и степень каждой его вершины четна.

Предыдущие результаты

Перестановка ребер

Пусть для графа [math]G[/math] задан набор всех его ребер [math](e_1, e_2, \dots e_m)[/math]. На каждом шаге два случайно выбранных ребра меняются местами. Фитнес функция — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное от количества ребер время.

Jump-оператор

Jump-оператор работает следующим образом. Для набора ребер [math](e_1, e_2, \dots e_m)[/math] оператор [math]jump(i,j)[/math] передвигает [math]i[/math]-й элемент на позицию [math]j[/math] и циклически сдвигает ребра между позициями [math]i[/math] и [math]j[/math] влево (если [math]i \gt j[/math] то вправо) . Таким образом набор [math](e_1, e_2, \dots e_m)[/math] превратиться в [math](e_1, e_2, \dots e_{i-1}, e_{i+1}, \dots e_j, e_i, e_{j+1}, \dots e_m)[/math]. Работает за [math]O(m^5)[/math], где [math]m[/math] — количество ребер в графе.

Улучшенный jump-оператор

Лучших результатов можно достичь, если использовать только операции вида [math]jump(i, 1)[/math]. Тогда время работы будет [math]O(m^5)[/math].

Алгоритм

Идея

Основная мысль — изменить структуру хранения графа. Ниже будет показан алгоритм, работающий за [math]O(m*log(m))[/math] (ранее лучшим считался результат [math]O(m^2*log(m))[/math] )

Представление графа

Пусть [math]G[/math] — неориентированный связный граф, [math]V[/math] — множество его вершин, [math]E[/math] — ребер. Будем хранить ребра в виде списков связности. Пусть [math]L_v[/math] — множество вершин, соединенных с [math]v[/math] ребром, [math]L[/math] — множество всех [math]L_v[/math]. Для каждой вершины [math]v[/math] введем также множество [math]M_v[/math], хранящее в себе неупорядоченные пары вершин из [math]L_v[/math]. Обозначим через [math]M[/math] множество всех [math]M_v[/math]. Таким образом если для всех вершин [math]v[/math] вершины из [math]L_v[/math] разбиты на пары в [math]M_v[/math], то с точностью до первого ребра на [math]G[/math] задан порядок обхода: пара [math](u,w)[/math] в [math]L_v[/math] означает, что придя из [math]u[/math] далее нужно идти в [math]w[/math] (или наоборот).

Фитнес функция

Фитнес функция для эволюционные алгоритмы поиска эйлерова цикла в графе выглядит так: [math]f(M) = m - |M| + k[/math], где

 [math]m[/math] — количество ребер в графе;
 [math]|M|[/math] — размер множества [math]M[/math];
 [math]k[/math] — количество путей в [math]M[/math]

Литература

• Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers