47
правок
Изменения
→Время работы алгоритма
==== Время работы алгоритма ====
{{Лемма
|statement=
Пусть <tex>M</tex> соответствует <tex>x</tex> путей. Тогда функция приспособленности <tex>f</tex> будет <tex>f = k \le m - |M - x| + x = 2x</tex>, откуда <tex>x \ge k/2</tex>
}}
{{Теорема
|statement=
Ожидаемое время работы эволюционного алгоритма поиска эйлерова цикла в графе по RLS будет:
<tex>O(\sum_{k=1}^{m} \frac{1} {k Delta(G) \cdot q} = \frac{1} {q} \sum_{k=1} ^{m} \frac{1} {k} = O(\frac{1} {q}cdot log \, m)</tex>для стратегии, ориентированной на ребра;
|proof=Пусть <tex>O(M</tex> соответствует <tex>x</tex> путей. Тогда функция приспособленности <tex>f</tex> будет <tex>f = k \frac{le m - |M - x| + x = 2x</tex>, откуда <tex>x \Deltage k/2</tex>}}Предположим, что значение функции приспособленности в данный момент <tex>k</tex>. Тогда путей не менее <tex>k/2</tex>. Если путь является циклом, то в нем есть хотя бы одна вершина, соединяющая данный путь с каким-то другим, то есть найдется пара <tex>(Gu, w)^2} {d</tex>, к которой можно применить мутацию и уменьшить количество путей. Если путь не является циклом, то так же найдется пара, при применении к которой мутации либо уменьшится количество путей, либо путь замкнется в цикл. Количество мутаций, которые уменьшают функцию приспособленности <tex>\Omega(Gk)} </tex>. Как следствие, вероятность выбрать подходящую пару <tex>\Omega(q \cdot m k)</tex>, где <tex>q</tex> — вероятность выбрать подходящую пару. Поэтому ожидаемое время достижения улучшения будет <tex>O(\frac{1} {k \cdot log \, mq})</tex> для стратегии, ориентированной на вершины;. Изначально значение функции приспособленности не более <tex>2m</tex>. Суммируя по всем <tex>k</tex> без учета констант получаем:
<tex>O(\Delta(G) sum_{k=1}^{m} \frac{1} {k \cdot q} = \frac{1} {q} \sum_{k=1} ^{m } \frac{1} {k} = O(\cdot frac{1} {q}log \, m )</tex> для стратегии, ориентированной на ребра;
Подствляя вместо <tex>O(\delta d(G) \cdot m \cdot log \, m )q</tex> различные <tex>p</tex> для стратегии, ориентированной на пары.разных стратегий выбора пар вершин получаем требуемые оценки времени работы алгоритма:
=== Литература ===
<references/>
