Изменения

Перейти к: навигация, поиск

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

Нет изменений в размере, 02:01, 19 июня 2012
Нет описания правки
==== Представление графа ====
Пусть <tex>G</tex> — неориентированный связный граф, <tex>V</tex> — множество его вершин, <tex>E</tex> — ребер; всего вершин <tex>n</tex>, а ребер <tex>m</tex> . Будем хранить ребра в виде списков связностисмежности. Пусть <tex>L_v</tex> — множество вершин, соединенных с <tex>v</tex> ребром, <tex>L</tex> — множество всех <tex>L_v</tex>. Для каждой вершины <tex>v</tex> введем также множество <tex>M_v</tex>, хранящее в себе неупорядоченные пары вершин из <tex>L_v</tex>. Обозначим через <tex>M</tex> множество всех <tex>M_v</tex>. Таким образом если для всех вершин <tex>v</tex> вершины из <tex>L_v</tex> разбиты на пары в <tex>M_v</tex>, то с точностью до первого ребра на <tex>G</tex> задан порядок обхода: пара <tex>(u,w)</tex> в <tex>L_v</tex> означает, что придя из <tex>u</tex> далее нужно идти в <tex>w</tex> (или наоборот).
==== Фитнес функция ====
Фитнес функция для эволюционные алгоритмы поиска эйлерова цикла в графе выглядит так: <tex>f(M) = m - |M| + k</tex>, где
Анонимный участник

Навигация