Викиконспекты - Вклад участника [ru]

Коды антигрея

2012-12-19T12:08:35Z

217.66.152.167: /* Псевдокод */

== Определение ==

{{Определение
|definition=
'''Код антигрея (Anti-Gray Code)''' {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.
}}

Здесь должно быть написано о том нафига вообще все это нужно.

== Двоичный код антигрея ==
{{Определение
|definition=
'''Двоичный код антигрея''' {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
}}

Объяснение, почему невозможен код, где соседние отличаются во всех битах.

=== Пример ===

Пример двоичного кода антигрея.

=== Алгоритм генерации ===

Описание алгоритма генерации

=== Псевдокод ===

genBinAntiGray(n)
for i = 1 to 2^(n-1)
v = getMirrorGray(i, n)
print(v)
inverseBits(v)
print(v)

=== Доказательство корректности алгоритма ===

Здесь приведено доказательство корректности алгоритма выше

== Троичный код антигрея ==
{{Определение
|definition=
'''Троичный код антигрея''' {{---}} такое упорядочивание троичных вектором, что соседние отличаются во всех разрядах.
}}

В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.

=== Пример ===

Пример троичного кода антигрея

=== Алгоритм генерации ===

Здесь идет описание алгоритма генерации троичного кода антигрея

=== Псевдокод ===

genTernAntiGray(n)
for v = <000..0> to <022..2>
digitCircleShift(v)
while(v[0] != 0)
print(v)
digitCircleShift(v)

=== Доказательство корректности алгоритма ===

Здесь идет доказательство корректности приведенного выше алгоритма

== См. также ==

*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]

== Источники ==

*[http://en.wikipedia.org/wiki/Talk%3AGray_code#Anti-Gray_Codes.3F Talk:Gray Code - Wikipedia, the free encyclopedia]

Коды антигрея

2012-12-19T12:05:39Z

217.66.152.167: /* Псевдокод */

== Определение ==

{{Определение
|definition=
'''Код антигрея (Anti-Gray Code)''' {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.
}}

Здесь должно быть написано о том нафига вообще все это нужно.

== Двоичный код антигрея ==
{{Определение
|definition=
'''Двоичный код антигрея''' {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
}}

Объяснение, почему невозможен код, где соседние отличаются во всех битах.

=== Пример ===

Пример двоичного кода антигрея.

=== Алгоритм генерации ===

Описание алгоритма генерации

=== Псевдокод ===

genBinAntiGray(n)
for i = 1 to 2^(n-1)
v = getMirrorGray(i, n)
print(v)
inverseBits(v)
print(v)

=== Доказательство корректности алгоритма ===

Здесь приведено доказательство корректности алгоритма выше

== Троичный код антигрея ==
{{Определение
|definition=
'''Троичный код антигрея''' {{---}} такое упорядочивание троичных вектором, что соседние отличаются во всех разрядах.
}}

В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.

=== Пример ===

Пример троичного кода антигрея

=== Алгоритм генерации ===

Здесь идет описание алгоритма генерации троичного кода антигрея

=== Псевдокод ===

genTernAntiGray(n)
doSomething

=== Доказательство корректности алгоритма ===

Здесь идет доказательство корректности приведенного выше алгоритма

== См. также ==

*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]

== Источники ==

*[http://en.wikipedia.org/wiki/Talk%3AGray_code#Anti-Gray_Codes.3F Talk:Gray Code - Wikipedia, the free encyclopedia]

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

2012-06-20T10:39:38Z

217.66.152.167: /* Введение */

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex><ref>Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers. Proceeding GECCO '07 Proceedings of the 9th annual conference on Genetic and evolutionary computation, 1203-1210 (2007)</ref> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot log\,m)</tex>)<ref>B. Doerr, C. Klein, and T. Storch. Faster evolutionary algorithms by superior graph representation. In Proc. of the 2007 IEEE Symposium on Foundations of Computational Intelligence (FOCI), 245–250 (2007).</ref>. При этом оптимальный (не эволюционный) [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%BE%D0%B2%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0 алгоритм] работает за <tex>O(m)</tex>. Здесь и далее <tex>m</tex> — количество ребер в графе.

После обзора предыдущих методов опишем представление графа, затем то, как устроена функция приспособленности и операция мутации, а потом адаптируем RLS и (1+1) EA стратегии для нашего случая.

=== Постановка задачи ===
{{Определение
|definition='''Эйлеров цикл в графе''' — это цикл, проходящий по всем рёбрам графа ровно по одному разу.
}}
Задача — для заданного графа найти такой цикл. Заметим, что это возможно тогда и только тогда, когда граф связный и степень каждой его вершины четна (для неориентированного графа).

=== Обзор методов ===
====Перестановка ребер ====
Пусть для графа <tex>G</tex> задан набор всех его ребер <tex>(e_1, e_2, \dots e_m)</tex>. На каждом шаге два случайно выбранных ребра меняются местами. Функция приспособленности — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное от количества ребер время.
====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>i > 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>. Алгоритм с использованием jump-оператора работает за <tex>O(m^5)</tex>, где <tex>m</tex> — количество ребер в графе.
====Улучшенный jump-оператор====
Лучших результатов можно достичь, если использовать только операции вида <tex>jump(i, 1)</tex>. Тогда время работы алгоритма будет <tex>O(m^3)</tex>.
=== Алгоритм ===
==== Представление графа ====
Пусть <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>, где

<tex>m</tex> — количество ребер в графе;

<tex>|M|</tex> — размер множества <tex>M</tex>;

<tex>k</tex> — количество путей в <tex>M</tex>.

==== Операция мутации ====
Операция мутации вводится для двух вершин <tex>u</tex> и <tex>w</tex> из <tex>L_v</tex>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <tex>u=w</tex>, то ничего не делаем;
* если для <tex>u</tex> и для <tex>w</tex> нет пары, то добавляем к <tex>M_v</tex> пару <tex>(u,w)</tex>;
* если <tex>u</tex> и <tex>w</tex> уже содержатся в <tex>M_v</tex> как пара, то удалим ее;
* если <tex>u</tex> уже добавлена в паре с некоторой вершиной <tex>p</tex>, а <tex>w</tex> не имеет пары, то удалим <tex>(u,p)</tex> из <tex>M_v</tex> и добавим <tex>(u,w)</tex>;
* если <tex>w</tex> уже добавлена в паре с некоторой вершиной <tex>p</tex>, а <tex>u</tex> не имеет пары, то удалим <tex>(w,p)</tex> из <tex>M_v</tex> и добавим <tex>(u,w)</tex>;
* если <tex>u</tex> уже добавлена в паре с некоторой вершиной <tex>p</tex>, а <tex>w</tex> уже добавлена в паре с некоторой <tex>k</tex>, то удалим <tex>(u,p)</tex> и <tex>(w,k)</tex> из <tex>M_v</tex> и добавим <tex>(u,w)</tex> и <tex>(p,k)</tex>;

==== Выбор вершин для мутации ====
Пусть <tex>d(v)</tex> — степень вершины <tex>v</tex> (количество ребер, которые из нее выходят), <tex>d(G)</tex> — средняя степень среди вершин <tex>G</tex>, <tex>\Delta G</tex> — максимальная степень среди вершин <tex>G</tex>, а <tex>\delta d(G) = \frac{1} {2m} \sum_{v \in V}d(v)^2</tex>.
Есть три способа выбрать две вершины для мутации.

'''Ориентированный на вершины'''

Сначала случайно выбираем <tex>v</tex> из <tex>V</tex>. Затем случайно и независимо выбираем <tex>u</tex> и <tex>w</tex> из <tex>L_v</tex>. Вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению:

<tex>p = \frac{1} {d(v)^2n} = \frac{d(G)} {2d(v)^2m} \ge \frac{d(G)} {2 \Delta (G)^2m}</tex>

'''Ориентированный на ребра'''

Выбираем случайно вершину <tex>u</tex> из всех <tex>2m</tex> вершин во всех списках <tex>L</tex>. Пусть она оказалась в <tex>L_v</tex>. Далее случайно выбираем <tex>w</tex> из <tex>L_v</tex>. Вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению:

<tex>p = \frac{1} {2d(v)m} \ge \frac{1} {2 \Delta (G)m}</tex>

'''Ориентированный на пары вершин'''

Выбираем случайно пару <tex>(u,w)</tex> из всех пар для всех <tex>2m</tex> вершин во всех списках в <tex>L</tex>. Пусть обе вершины присутствуют в <tex>L_v</tex>. Тогда вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению:

<tex>p = \frac{1} {2\delta d(G)m} </tex>

Эти три случая эквивалентны в случае разреженного графа (в котором <tex>d(G) = \delta d(G) = \Delta (G)</tex>). В общем случае <tex>d(G) \le \delta d(G) \le \Delta (G)</tex> и лучший результат достигается для способа, который ориентирован на вершины.

==== Стратегии RLS и (1+1) EA ====
Эволюционный алгоритм поиска эйлерова цикла в графе работает следующим образом. Размер популяции возьмем равным одному; представление графа, операция мутации и функция приспособленности будут такими, как описано выше. Начальное заполнение множества <tex>M</tex> можно сделать случаным образом или оставить пустым, на время работы алгоритма это не влияет.

Стратегия Randomized local search будет работать так: на каждом шаге к текущему индивиду (он один, так как в популяции только одна особь) применяется операция мутации. Если полученный индивид лучше текущего, он выбирается для дальнейшей работы, в противном случае ничего не происходит. Алгоритм работает до тех пор, пока функция приспособленности не минимизирована.

Псевдокод:
Initialize(M)
while (f(M) > 1) do
M′:=φ(M)
if f(M′) ≤ f(M)
then M := M′

Стратегия (1+1) evolutionary algorithm в классическом варианте применяет операцию мутации к каждому биту <tex>n</tex>-битной строки с вероятностью <tex> \frac{1} {n}</tex>. В текущем алгоритме применять изменения можно только последовательно, поэтому просто делают операцию мутации несколько раз.

Псевдокод:
Initialize(M)
while (f(M) > 1) do
M′ :=M
for i := 0 to k do //k — некоторое число
M′ := φ(M′)
if f(M′) ≤ f(M)
then M := M′

==== Время работы алгоритма ====
Для RLS и (1+1) EA верны следующие оценки времени работы алгоритма:

<tex>O(\frac{\Delta(G)^2} {d(G)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

<tex>O(\Delta(G) \cdot m \cdot log \, m )</tex> для стратегии, ориентированной на ребра;

<tex>O(\delta d(G) \cdot m \cdot log \, m )</tex> для стратегии, ориентированной на пары.

=== Литература ===
<references/>