Эволюционные алгоритмы поиска эйлерова цикла в графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Предыдущие результаты)
(Jump-оператор)
Строка 8: Строка 8:
 
Пусть для графа <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-оператор====
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-оператор работает следующим образом. Для набора ребер <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>. Работает за <tex>{O(1)}</tex>
 +
 
 
====Улучшенный jump-оператор====
 
====Улучшенный jump-оператор====
  

Версия 19:57, 17 июня 2012

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

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


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

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

Пусть для графа [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](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(1)}[/math]

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

Алгоритм

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

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

Операция мутации

Выбор вершин для мутации