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

Материал из Викиконспекты
Версия от 19:45, 17 июня 2012; 92.100.5.133 (обсуждение) (Предыдущие результаты)
Перейти к: навигация, поиск

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

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


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

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

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

Алгоритм

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

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

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

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