Эволюционные алгоритмы поиска эйлерова цикла в графе — различия между версиями
(→Предыдущие результаты) |
(→Предыдущие результаты) |
||
Строка 7: | Строка 7: | ||
====Перестановка ребер ==== | ====Перестановка ребер ==== | ||
Пусть для графа <tex>G</tex> задан набор всех его ребер <tex>(e_1, e_2, \dots e_m)</tex>. На каждом шаге два случайно выбранных ребра меняются местами. Фитнес-функция — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное время. | Пусть для графа <tex>G</tex> задан набор всех его ребер <tex>(e_1, e_2, \dots e_m)</tex>. На каждом шаге два случайно выбранных ребра меняются местами. Фитнес-функция — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное время. | ||
+ | ====Jump-оператор==== | ||
+ | Jump-оператор работает следующим образом. Для набора ребер <tex>(e_1, e_2, \dots e_m)</tex> оператор <tex>jump(i,j)</tex> передвигает <tex>i</tex>-й элемент на позицию <tex>j</tex> и циклически сдвигает ребра между позициями <tex>i</tex> и <tex>j</tex> влево. Таким образом набор <tex>(e_1, e_2, \dots e_m)</tex> превратиться в <tex>(e_1, e_2, \dots e_i-1, e_i+1, \dots e_j, e_i, e_j+1, \dots e_m)</tex>. Работает за {O(1)} | ||
+ | ====Улучшенный jump-оператор==== | ||
=== Алгоритм === | === Алгоритм === |
Версия 19:56, 17 июня 2012
Содержание
Постановка задачи
Определение: |
Эйлеров цикл в графе — это путь, проходящий по всем рёбрам графа ровно по одному разу. Задача — для заданного графа найти такой путь. |
Предыдущие результаты
Перестановка ребер
Пусть для графа
задан набор всех его ребер . На каждом шаге два случайно выбранных ребра меняются местами. Фитнес-функция — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное время.Jump-оператор
Jump-оператор работает следующим образом. Для набора ребер
оператор передвигает -й элемент на позицию и циклически сдвигает ребра между позициями и влево. Таким образом набор превратиться в . Работает за {O(1)}