Изменения
Нет описания правки
minCut():
answer = INF;
for i = 1..ccount
curCut = getCut();
if curCut < answer
answer = curCut;
return answer;
Так как алгоритм вероятностный и функция <tex>getCut</tex> возвращает вес случайного потока, а не минимального, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию <tex>ccount</tex> раз. Какое конкретное значение <tex>ccount</tex> выбрать будет описано ниже.
Реализация функции <tex>getCut</tex> {{---}} это и есть основа алгоритма. Будем действовать следующим образом: пока вершин больше двух, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа.
getCut():
}}
Таким образом, мы видим, что вероятность получить правильный ответ после единичного запуска функции <tex>getCut</tex> очень мала. Однако, вызвав эту функцию <tex>ccount</tex> раз мы увеличим эту вероятность. Рассчитаем значение <tex>ccount</tex> такое, чтобы вероятность успеха была близка к <tex>1</tex>.
Для этого воспользуемся следующим неравенством:
<tex> e^x \geq 1 + x</tex> для любого вещественного <tex>x</tex>.
Вероятность того, что мы не получим правильный ответ после <tex>ccount</tex> независимых запусков равна
<tex dpi="140">(1-\frac{2}{n^2})^c</tex>.
Пусть <tex>c count = n^2ln2\ln(n)</tex>. Тогда в силу указанного выше неравенства:
<tex dpi="140">(1-\frac{2}{n^2})^c count \leq e^{c count \cdot (-\frac{2}{n^2})} = e^{-2ln2 \ln(n)} = \frac{1}{n^2}</tex>.
То есть, если вызвать функцию <tex>getCut</tex> <tex>n^2\ln(n)</tex> раз, и после каждой итерации запоминать минимум, то вероятность того, что найденный ответ будет неверен <tex> \leq \frac{1}{n^2}</tex>. Даже при небольших значениях <tex>n</tex> алгоритм практически гарантированно выдает правильный ответ.
<tex>T(n) = O(n^2) + T(n/\sqrt{2}) = O(n^2\log(n))</tex>.
Это медленнее, чем оригинальный алгоритм, однако вероятность нахождения разреза минимального веса экспоненциально выше. Достаточно запустить алгоритм <tex>c\log^2(n)</tex>раз, где <tex>c</tex> - некоторая константа. Действительно, рассчитаем вероятность неправильного ответа также, как раньше:
<tex dpi="160">(1-\frac{1}{log(n)})^{c\log^2(n)} \leq e^{c\log^2(n) \cdot -\frac{1}{log(n)}} = \frac{1}{n^c}.</tex>
