1

Тема: Краскал

http://e-maxx.ru/algo/mst_kruskal_with_dsu

if (rand() & 1) swap (a, b);

Этот if не меняет асимптотику. Может лучше его или убрать, или переписать на честные ранги? :-) Или конкретно в случае построения MST это действительно дает оптимайз?

P.S. Если нужен тест для произвольной СНМ-задачи, на котором этот "оптимайз" ничего не дает, могу предоставить.

2

Re: Краскал

Да? Неожиданно:)
Хочешь сказать, рандомом без честных рангов вообще нельзя получить log* ?

3

Re: Краскал

Интересно. А этот тест дает логарифм для произвольного рандсида?

4

Re: Краскал

Здравствуйте, это я натравил Сережу на вашего Краскала )

Насколько я понимаю, в основной статье про СНМ реализация тоже m*log(n), а не заявленная про Аккерманна.
Т.к:
1. В первой реализации, там вместо размеров оцениваются высоты. Может я не прав, но, по-моему, это не дает требуемую оценку.
2. Про вторую (рандомизированную) написал Сережа.

5

Re: Краскал

Да нет, с рангами там как раз все нормально. Оценивать можно и высоты.

6

Re: Краскал

Извиняюсь, я забыл про форум... мне на почту не приходит "у вас новое сообщение" :-(

Тест очень простой: растим цепочку.
1) Если мы всегда делаем  p[a] = b, мы получим высоту N
2) Если мы делаем if (rand() & 1), мы получим высоту N / 2

P.S. Если делать только сжатие путей, асимптотика (аморатизированная) уже O(logN). Поэтому есть распространенное мнение, что rand() & 1 что-то дает. На самом деле, если тест случаен - он и без rand() & 1 случаен. А если тест = цепочка, то быстро работает не потому что rand() & 1, а потому что сжатие путей.

7

Re: Краскал

>> Хочешь сказать, рандомом без честных рангов вообще нельзя получить log* ?
Да!

8

Re: Краскал

ОК, а поделись пожалуйста тестом smile

9

Re: Краскал

Я надеюсь, Сережа не будет против, если я выложу тест, который он мне показал в личке на КФ.

Структура простая: Join(1,2), Join(1,3), Join(1,4), ..., Join(1,N). Предполагается, что Join выглядит следующим образом:

Join(a,b) {
 A = root(a);
 B = root(b);
 if (rand() & 1) p[A] = B; else
 p[b] = A;
}

При такой реализации с вероятностью 1/2 при каждом Join'е у дерева, содержащего вершину 1, высота будет увеличиваться на 1. Ожидаемая высота через N операций будет N/2.