Венгерский алгоритм (также алгоритм присваивания Мункреса)

Question

Я недавно наткнулся на этот алгоритм , и мне трудно объяснить его самому себе. Алгоритм решает проблему присваивания в O (n ⁴ ) (и, очевидно, его можно улучшить до O (n ³ )), но я не понимаю, почему .

Интуитивно я вижу, что алгоритм будет стремиться найти хорошие и оптимальные решения, но я не вижу доказательства! Все доказательства, которые я видел до сих пор, содержат обозначения, с которыми я не знаком. Мой вопрос: кто-нибудь может объяснить это строго, но просто?

Я уже понимаю, что проблему можно перенести в матрицу значений, в которой должно быть выбрано ровно одно значение в каждой строке и каждом столбце. Минимально возможное значение (из выбранных элементов) и выбор, который производит, - это то, что вычисляет алгоритм. Очевидно, что выбор также находит минимум.

---

Часть, с которой я борюсь, в плане обозначений, - здесь . Третий абзац в разделе Настройки , который начинается с «Давайте вызовем функцию» ...

Answer 1

На странице Википедии , на которую вы ссылались, есть шаги, как сделать этот алгоритм вручную на матрице. В реализации python также используются матрицы. Иногда единственный способ понять алгоритм - это пройти его вручную или в интерактивной консоли.

Answer 2

Вы можете почитать эту книгу от Jungnickel, которая содержит подробное теоретическое обсуждение венгерского алгоритма, начиная с p 421, но также приводит пример Проработав пример, вы сможете понять, почему алгоритм равен O (n3)).

Answer 3

Потенциальная функция y присваивает число каждой вершине в вашем полном двудольном графе таким образом, чтобы сумма потенциалов любой вершины из S (множество всех людей) и любой вершины из T (множество всех рабочие места) меньше, чем значение ребра, соединяющего эти вершины (так меньше, чем стоимость человека, выполняющего работу). Функция, которая присваивает 0 каждой вершине, является хорошим примером допустимой потенциальной функции.

Значение потенциала у - это сумма потенциалов всех вершин (это определение).

Можно видеть, что стоимость каждого идеального соответствия, по крайней мере, равна стоимости каждого потенциала.

Это довольно очевидно: при идеальном сопоставлении вы должны выбрать n ребер, которые не имеют общих вершин. Стоимость каждого ребра ниже суммы потенциала его вершин (из определения потенциала). Когда вы суммируете затраты всех ребер из вашего соответствия, оно будет выше, чем значение потенциала для графика.

Теперь алгоритм вычисляет потенциал и соответствие, так что их соотношение цена / стоимость одинаково. Поскольку значение потенциала является нижней границей минимальной стоимости задачи, вы получите оптимальное решение.

Это доказывает алгоритм. Теперь вам нужно взглянуть на него и понять, почему и как он находит идеальное соответствие и потенциал с равной стоимостью / стоимостью.

Answer 4

Функция отображает каждую вершину в графе, который представляет собой объединение S и T, которое означает, что означает этот U-образный символ, в систему рациональных чисел, которая представляет собой то, что представляет Q в этом неравенстве для данной пары вершины. Какая часть обозначения там не имеет смысла?

Answer 5

Это говорит о том, что y значений S и T является потенциальным ответом, если y при i и y в j вместе меньше, чем стоимость, рассчитанная для этой позиции на данный момент (поиск наименьшего потенциального ответа), для каждой позиции в S и T .

Это проблема динамического программирования, если я правильно помню. Идеальное совпадение было бы тогда, когда парень, чья самая низкая цена оказалась именно тем, кого он выбрал.