Форд-Беллман и random shuffle

Revision ru1, by Burunduk1, 2018-04-08 20:54:39

Предыстория

Жил был алгоритм Форд-Беллмана. Разные люди его по всякому оптимизировали.
Например, популярен «Форд-Белман с очередью», также известный, как SPFA.

Здесь мы рассмотрим менее популярную версию «Форд-Белман с random shuffle».

(1) random_shuffle(edges.begin(), edges.end());
for (int run = 1; run; ) {
	run = 0;
        (2) random_shuffle(edges.begin(), edges.end());
	for (Edge e : edges)
		if (relax(e))
			run = 1;
}

Фазой назовём цикл по всем рёбрам. Обычный Форд-Беллман сделает не более V фаз.

История

Оказывается, в зависимости от того, где написать random_shuffle,
сделать один раз заранее, или делать в начале каждой фазы, многое зависит.

На худшем тесте матожидание числа фаз у одного из новых Форд-Беллманов равно V / 2, у другого V / 1.72.
Как думаете, у кого меньше? Скоро допишу сюда ответ и доказательства.

Tags ford bellman, random, random_shuffle, magic

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru5 Russian Burunduk1 2018-04-10 09:33:24 103
ru4 Russian Burunduk1 2018-04-08 21:27:25 2
ru3 Russian Burunduk1 2018-04-08 21:10:07 397
ru2 Russian Burunduk1 2018-04-08 21:00:14 14
ru1 Russian Burunduk1 2018-04-08 20:54:39 1037 Первая редакция (опубликовано)