Алгоритм Каргера: Сила рандомизации в теории графов
Иногда бросить монетку — это лучший способ решить сложную математическую задачу. В информатике существует класс рандомизированных алгоритмов, которые сознательно используют случайные числа в своей логике. Они могут ошибаться, но за счет своей невероятной простоты и скорости позволяют, запустив их тысячу раз, гарантированно получить правильный ответ. Самый красивый пример такого подхода — Алгоритм Каргера для поиска минимального разреза графа.
Минимальный разрез (Min-Cut) — это задача разделения связного неориентированного графа на две непересекающиеся части так, чтобы количество ребер, соединяющих эти две части, было минимально возможным. В реальном мире это отвечает на вопрос: «Какие несколько кабелей нужно перерезать диверсанту, чтобы гарантированно разделить компьютерную сеть компании на два изолированных сегмента?». Классическое детерминированное решение базируется на алгоритме Форда-Фалкерсона и требует многократного поиска путей, что довольно медленно (O(V^3)).
В 1993 году Дэвид Каргер, будучи студентом Стэнфорда, придумал поразительно простой алгоритм, состоящий из одной операции — стягивания ребра (Edge Contraction):
- Выбираем абсолютно случайное ребро в графе.
- Стягиваем его: две вершины, соединенные этим ребром, сливаются в одну новую супервершину.
- Все ребра, которые шли к исходным двум вершинам, теперь идут к новой супервершине (могут образовываться кратные ребра). Петли (ребра, начинающиеся и заканчивающиеся в одной супервершине) просто удаляются.
- Повторяем этот процесс, пока в графе не останутся ровно две супервершины.
- Оставшиеся между ними ребра — это и есть наш вариант разреза!
Кажется, что такой слепой случайный алгоритм обречен на провал. Математический анализ показывает, что вероятность найти настоящий минимальный разрез за один пропуск алгоритма составляет всего около 2 / N^2 (где N — количество вершин). Это очень мало. Однако прелесть метода в том, что он работает невероятно быстро. Если мы повторим этот простенький процесс O(N^2 log N) раз и выберем самый лучший (минимальный) из найденных разрезов, то вероятность нашей ошибки (что мы так и не нашли истинный оптимум) станет меньше, чем вероятность того, что в компьютер ударит метеорит (стремится к нулю).
Позже была разработана оптимизация — алгоритм Каргера-Штейна, который использует частичное стягивание и рекурсивное ветвление, улучшая асимптотическую сложность до квазиквадратичной O(N^2 log^3 N), что сделало рандомизированный подход непревзойденным по скорости в классе задач о разрезах.
