Рандомизированный Min-Cut, алгоритм Каргера

Question

Я реализую алгоритм Каргера. Из того, что я понимаю, число ребер между двумя последними узлами не всегда является минимальным срезом. У меня возникли проблемы с пониманием, как мне на самом деле сократить минимальные значения этого алгоритма. Я продолжаю находить много вещей о вероятностях, но все это выглядит для меня бессмысленным...

Из того, что я прочитал, я думаю, что мне нужно запустить алгоритм Каргера несколько раз на графике. Это даст мне высокую вероятность успеха попадания в мин. Я думаю?...

Может кто-нибудь объяснить это более простым способом? Как мне найти количество раз, чтобы запустить этот алгоритм? Правильно ли то, что я сказал выше?

Answer 1

Каждый раз, когда вы запускаете алгоритм Каргера, он дает вам (полу-случайное) сокращение. Вероятность того, что этот разрез является минимальным, составляет P = 1 / (n^2/2 - n/2), что намного лучше, чем просто выбирать разрез совершенно случайно.

Если вы запустите алгоритм один раз, ваша вероятность получить минимальное сокращение составляет P, но ваша вероятность не получить это 1 - P, Если вы запустите алгоритм дважды, то ваши шансы не получить минимальное сокращение (1 - P) * (1 - P), так как вам придется пропустить мин сократить первый раз, а второй раз.

Это немного лучше. Запуск алгоритма дважды дает нам более высокую вероятность нахождения минимального сокращения.

Если мы запустим алгоритм T раз, то вероятность не получить минимальное сокращение составляет (1 - P)^T, что означает, что вероятность получения минимального сокращения составляет 1 - (1 - P)^T,

В этот момент вы спрашиваете себя, насколько сильно вы хотите правильное решение. Составьте некоторую вероятность (1 на 1 000 000?) И решите для T. Вот сколько раз вы должны запустить алгоритм.

Это обычно для установки T = C * (n choose 2) * ln(n), так как это дает вам меньше, чем (1 / n)^C вероятность того, что вы не найдете минимальное сокращение, что является гораздо более простой формулой, особенно если вы установите C 1. У вас меньше шансов получить неправильный срез, чем при случайном выборе одного узла вашего графика. Это очень хорошо, если ваш график большой.

В итоге выберите C исходя из того, насколько необходимо получить правильный ответ. Если вы не знаете, насколько это необходимо, то C = 1 хорошая догадка, и просто запустите свой алгоритм (n choose 2) * ln(n) раз.

(Большая часть этой математики взята со страницы википедии. Вы можете найти более подробную информацию там)