15
правок
Изменения
м
→(1+1)-ES для MST
=== (1+1)-ES для MST ===
Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1</tex>, если ребро <tex>e \in E'</tex>входит в минимальное остовное деревно, и <tex>x_e = 0</tex> в обратном случае.
На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>.
