В алгоритмі Хопкрофта-Карпа максимальнодвостороннє співставлення, чому ми завжди шукаємо найкоротший шлях, що збільшується в першому пошуку? Це тому, що широта першого пошуку завжди знаходить найкоротший шлях? Я просто заплутався, чому важливо, щоб шлях до збільшення був найкоротшим.
Відповіді:
2 для відповіді № 1Знайти лише один шлях до збільшення - це вже аТета (| E |) -час роботи. Ідея, що стоїть перед Хопкрофтом-Карпом (більшість алгоритмів збільшеного контуру, насправді, якщо хтось косить трохи), - це зробити більше з кожною ітерацією Theta (| E |).
Чому найкоротші шляхи збільшення? H – K шукає декілька шляхів нарощування одночасно, які повинні бути роз'єднані вершиною, щоб бути корисними одночасно. Вершина непересічність створює проблему упаковки, до якої жадібним рішенням є спочатку "найгустіші" (найкраще співвідношення співвідношення значення та простір), тобто найкоротші шляхи збільшення. На практиці жадібні алгоритми часто добре працюють (див., Наприклад, аналізи кришки заданих чи H – K на випадкових графах).
Справжня відповідь, однак, полягає в тому, що H – K є доказовимкраще, ніж Тета (| E | | V |). Формальний аналіз H – K використовує довжину найкоротшого шляху розширення для вимірювання прогресу алгоритму, і, використовуючи максимальний набір цих шляхів, H – K збільшує цю величину. Коли найкоротші шляхи нарощування досягають довжини √ | V |, їх неможливо спакувати більше √ | V | з них (вершина неперервна), тому алгоритм повинен мати не більше √ | V | ребер і загальну кількість ітерації O (√ | V |), для часу (O | | E | √ | V |) - кроку.