Алгоритм Karger’ів випадкового мінімального розрізу

Чому це важливо

Ефект розрізу пояснює, як мережі можуть бути вразливими до атак. Мінімальний розмір розрізу показує мінімальну кількість зв’язків, які потрібно зруйнувати або атакувати, щоб розділити комунікаційну мережу, електромережу чи соціальну мережу на від’єднані компоненти. Малий мінімальний розмір розрізу свідчить про вразливість; великий – про стійку структуру. Цей ефект також з’являється як міра стійкості мережі: мінімальний розмір розрізу говорить про найменшу кількість зв’язків, які потрібно зруйнувати або атакувати, щоб розділити комунікаційну мережу, електромережу чи соціальну мережу на від’єднані компоненти. Знайти його ефективно, особливо у великих графах, справді корисно за межами чистої теорії.

Покроковий процес стиснення

Алгоритм Karger'ів працює з багатографіком, тобто повинен допускати паралежні ребра між одними й тими ж вершинами, оскільки стискання природним чином їх створює. Процедура свідомо мінімальна. По-перше, поки залишається більше двох вершин, випадковим чином обирайте одне ребро серед усіх поточних ребер, включаючи будь-які паралельні копії. По-друге, стисніть це ребро: об'єднайте кінцеві вершини в одну нову злиту вершину. Усі ребра, які раніше торкалися однієї з оригінальних кінцевих точок, тепер торкаються новоствореної злитої вершини замість того, щоб бути видаленими. По-третє, видаліть будь-які самоцикли, що виникли, тобто ребра, які тепер з'єднують об'єднану вершину із собою, оскільки самоцикл ніколи не може бути частиною розрізу, який розділяє два залишки супер-вершини. Повторюйте цей цикл «вибирати та стискати», поки не залишиться рівно дві супер-вершини. Усі ребра, які все ще з'єднують ці останні дві супер-вершини, всі з яких походять від паралельних ребер, накопичених у процесі стиснення, утворюють вихідний розріз алгоритму. Зверніть увагу на важливе: випадковий вибір ребра серед поточного множинного набору ребер не той самий, що й випадковий вибір серед початкових пар вершин. Вершини, які поглинули багато стиснень і, відповідно, мають високий ступінь, більш ймовірно будуть обрані наступним ребром, просто тому, що вони сприяють більшій кількості паралельних ребер у басейні. Це зважене за ступенем випадковість не є випадковістю чи недоліком; це саме механізм, який робить аналіз ймовірностей вигідним для збереження малих розрізів, оскільки ребра, що належать малому мінімальному розриву, складають порівняно невелику частку від загальної кількості ребер на кожному етапі, особливо на ранніх стадіях, коли гра все ще велика та добре зв'язана.

Чому один запуск може зазнати невдачі, і чому це рідко трапляється

Уявіть, що справжній глобальний мінімальний розріз графа має рівно k пересічних ребер. Один запуск алгоритму не знаходить цей конкретний розріз лише тоді, коли, в процесі послідовності злиття, одне з цих k спеціальних ребер випадковим чином вибирається та зливається. Злиття ребра мінімального розрізу об'єднує два вершини, які справжній мінімальний розріз призначив для утримання на протилежних сторонах, назавжди знищуючи будь-які шанси на відновлення цього конкретного розрізу пізніше в ході запуску. Отже, вся проблема успіху чи невдачі полягає в тому: яка ймовірність того, що всі кроки злиття уникають усіх k ребер мінімального розрізу? Ключовий структурний факт, який робить аналіз дійсним: якщо глобальний мінімальний розріз має розмір k, то кожна вершина графа повинна мати ступінь принаймні k. Чому? Тому що розріз, який ізолює лише цю одну вершину від усього іншого, сам по собі є дійсним розрізом, і його розмір, а саме ступінь цієї вершини, не може бути меншим за мінімальний розріз, або k не було б справді мінімальним. Оскільки кожна вершина має ступінь принаймні k, граф з n вершинами повинен мати щонайменше nk поділити на 2 ребер загалом, відповідно до принципу рукостискання між ступенем та кількістю ребер. Це означає, що на будь-якому етапі з m решта вершин поточний граф має принаймні mk поділити на 2 ребер, тоді як лише k з них належать до розрізу, який відстежується. Отже, ймовірність випадкового вибору краю потрапити одне з цих k небезпечних ребер не перевищує k поділити на mk поділити на 2, що спрощується до 2 поділити на m. Це межа справедлива на кожному кроці злиття, і множення ймовірностей виживання на всіх етапах від n вершин до 2 дає знаменитий результат, що один запуск має успіх з ймовірністю принаймні 2 поділити на n помножити на n мінус 1, що приблизно дорівнює 2 поділити на n в квадраті.

Методи Монте-Карло: Торгівля Впевненості за Простоту та Швидкість

Алгоритм Каржера є класичним прикладом алгоритму Монте-Карло, випадкового алгоритму мінімального розрізу, який завжди працює в обмежений час, але гарантовано дає правильну відповідь лише з певною ймовірністю, на відміну від алгоритму Лас-Вегас, який завжди дає правильну відповідь, але має випадковий час виконання. Це фундаментально інший контракт, ніж пропонують детерміновані алгоритми. Детерміновальний алгоритм мінімального розрізу, такий як той, що будується на повторних обчисленнях максимального потоку, завжди даватиме точну правильну відповідь у кожному запуску, без винятків. Алгоритм Каржера не робить подібного обіцянки для окремого запуску; приблизно 2 з n квадратів успішність означає, що на графі з лише кількома десятками вершин окремий запуск насправді ймовірно поверне розріз більший за мінімальний. Те, що робить це прийнятною, навіть привабливою, торгівлею, полягає в тому, що невірні події під час незалежних повторень є самостійними, оскільки кожен запуск перемішує власні випадкові вибори з нуля. Запуск процесу постійного скорочення T незалежно та зберігання найменшого розрізу, знайденого в результаті, спрацює лише якщо кожна з цих T спроб не вдається. Оскільки ймовірність невдачі на одному запуску не більше ніж одна мінус 2 з n квадратів, ймовірність того, що всі T запусків зазнають невдачі одночасно, зменшується приблизно як e піднесено до степеня -2T з n квадратів. Вибір T пропорційно n квадратів помноженому на логарифм n знижує загальну ймовірність невдачі нижче ніж одну з n, або будь-який інший поліноміально малий поріг, тоді як загальна робота залишається поліноміальною щодо n. Це основна угода Монте-Карло: прийняти обмежену, вимірювану ймовірність помилки в обмін на алгоритм, який значно простіший у формулюванні, реалізації та розумінні, ніж його детерміновані відповідники, і майже повністю нейтралізувати цю ймовірність помилок просто повторюючи дешеві незалежні експерименти та зберігаючи найкращий результат.

Час виконання та практичні вдосконалення

Кожна окрема стискання може бути реалізована ефективно за допомогою структури даних «з’єднаний список» (або «розділений набір») для відстеження, які початкові вершини об’єдналися в одну супер-вершину, дозволяючи одному кроку стиснення виконуватися майже за постійний середній час, а повне виконання n мінус 2 стискань завершується приблизно за O(m) часу, де m - кількість ребер, що визначаються вартістю сканування та вибору ребер. Повторення всього процесу n квадратів log n разів для досягнення високої ймовірності правильності потім дає загальний очікуваний час виконання порядку O(n^2 * m * log n), хоча цей поліноміальний підхід теоретично ефективний, він може бути повільним на практиці для великих графів порівняно зі спеціалізованими детермінованими алгоритмами, такими як алгоритм Stoer-Wagner мінімального розрізу, який знаходить точну відповідь детермінованим способом за час O(n * m + n^2 * log n) за допомогою повністю іншої фазової стратегії злиття вершин без жодної випадковості. Це місце, де чудове вдосконалення, розроблене Давидом Каргером разом із Кліффордом Штайн, значно покращує ситуацію. Їхній підхід, який іноді називають алгоритмом рекурсивного стиснення, спостерігає, що ранні стиснення, коли граф великий, є відносно безпечними, оскільки ймовірність виживання 2/m залишається близькою до 1, тоді як пізні стиснення, коли граф зменшується до приблизно n вершин, є ризикованими. Отже, замість стискання до двох вершин одним кроком і перезапуску з нуля, вдосконалений алгоритм стискає до приблизно квадратний корінь із n вершин, потім розгалужується на два незалежні рекурсивні спроби з цього безпечного проміжного стану, приймаючи кращий з двох результатів. Це рекурсивне розгалуження зменшує загальний час виконання до O(n^2 * log n), зберігаючи при цьому гарантію високої ймовірності правильності, що ілюструє, як основна ідея Монте-Карло може бути впорядкована за допомогою більш ефективного розподілу ресурсів після того, як ви точно визначаєте, де зосереджено ризик невдачі.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Karger's Randomized Min-Cut Algorithm і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.