Эволюционные алгоритмы поиска эйлерова цикла в графе — различия между версиями
(→Предыдущие результаты) |
(→Предыдущие результаты) |
||
| Строка 6: | Строка 6: | ||
=== Предыдущие результаты === | === Предыдущие результаты === | ||
====Перестановка ребер ==== | ====Перестановка ребер ==== | ||
| − | Пусть | + | Пусть для графа <tex>G</tex> задан набор всех его ребер <tex>(e_1, e_2, \dots e_m)</tex>. На каждом шаге два случайно выбранных ребра меняются местами. Фитнес-функция — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное время. |
=== Алгоритм === | === Алгоритм === | ||
Версия 19:45, 17 июня 2012
Содержание
Постановка задачи
| Определение: |
| Эйлеров цикл в графе — это путь, проходящий по всем рёбрам графа ровно по одному разу. Задача — для заданного графа найти такой путь. |
Предыдущие результаты
Перестановка ребер
Пусть для графа задан набор всех его ребер . На каждом шаге два случайно выбранных ребра меняются местами. Фитнес-функция — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное время.
