Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы алгоритмов и структур данныхВ 31-й статье давайте поговорим о BiPArtite Graph Matching и венгерский алгоритм.
В предыдущей статье мы представили интересную задачу стабильного брака, моделирующую сцену брака и любви между мужчиной и женщиной, и изучили алгоритм Гейла-Шепли, который делает сопоставление более устойчивым. Если вы пропустили эту статью, вы можете ознакомиться с конкретным содержанием супружеской стабильности на портале ниже.
Как мы упоминали в конце прошлой статьи, проблема согласования брака, по сути,Двудольное сопоставление графовПроблема. Так что же такое сопоставление двудольных графов? Какой алгоритм следует использовать для решения задачи сопоставления двудольных графов? Начнем с самых основных понятий.
Двудольное сопоставление графов
Понятие двудольного графа очень простое, то есть в неориентированном графе все точки можно разделить надва подмножества. точки в этих двух подмножествахне пересекаться друг с другом, а вершины, связанные со всеми ребрами графа, принадлежат двум разным множествам. Это немного сложно описать словами, но мы можем понять это, взглянув на картинку.
На приведенном выше рисунке очевидно, что три вертикальные точки слева — это один набор, а три вертикальные точки справа — другой набор. Два набора соединены ребром, и наборы не связаны друг с другом.
Сопоставьте максимальное совпадение
В двудольном графе, если мы выберем ребро, оно соединит соответствующие две точки. Это также представляет собойсовпадение, мы оговариваем, что вершина может составлять не более одного совпадения, то есть между всеми совпадениями нет общей точки.
Для двудольного графа количество совпадений может быть разным, и случай с наибольшим числом совпадений называется максимальным совпадением. Если все вершины совпадают, то ситуация называется идеальным совпадением.
Что представить сегодняВенгерский алгоритмЭто алгоритм, используемый для завершения максимального сопоставления бипарттовых графов.
Венгерский алгоритм
Венгрия, которую мы все знаем, — это название страны, связанной с изобретателем алгоритма. Изобретатель венгерского алгоритма Эдмондс предложил венгерский алгоритм в 1965 году. Я не знаю, почему изобретателя алгоритма называют венгерским алгоритмом, и я никогда не видел других алгоритмов, названных в честь страны, потому что венгры предложили слишком мало алгоритмов.
Основной принцип венгерского алгоритма очень прост, т. е.Найти пути увеличения, чтобы добиться максимального совпадения.
Мы используем простой язык, чтобы объяснить смысл алгоритма, а также используем изображение выше в качестве примера. Сначала мы сопоставляем 1 слева с a справа, а 2 слева с b справа.
Таким образом, когда мы хотим сопоставить узел № 3 слева, мы обнаружили проблему, то есть узлы a и b, которые могут соответствовать узлу № 3, уже заняты. Таким образом, узел 3 не может представлять собой совпадение, но мы можем видеть, глядя на график, что если узлы 1 и 2 немного скорректируют ситуацию сопоставления, на самом деле можно переместить узел 3 из позиции.
Как это работает?
Мы проходим через узлы, которым может соответствовать узел № 3, сначала находим узел а и обнаруживаем, что узел а был занят. Итак, мы находим узел, который соответствует узлу a, то есть узлу 1,попробуй найти совпадение снова, переместите позицию для узла 3. Итак, мы рекурсивно размещаем узел 1, переходим к узлу b и обнаруживаем, что узел b также занят. Таким образом, мы также рекурсивно используем узел № 2, который соответствует узлу b, чтобы увидеть, может ли узел № 2 найти новую яму для создания места.
Давайте посмотрим и обнаружим, что узел 2 может быть сопоставлен с узлом c, освобождая место для узла № 1, так что № 1 может освободить место для узла № 3. Таким образом, окончательный результат сопоставления таков:
Синяя линия — это результат до настройки сопоставления, а красная линия — результат после настройки.
По существу, венгерский алгоритм представляет собойНастроить соответствиепроцесс. В виде рекурсивных вызовов попытайтесь скорректировать сопоставление, занявшее конфликтную позицию, и освободить место для узла справа.
Давайте сравним принцип венгерского алгоритма с алгоритмом Гейла-Шепли, нашли ли мы что-нибудь? На самом деле, основные принципы этих двух алгоритмов одинаковы: в алгоритме GS мы сначала инициируем преследование мальчиков и пытаемся сформировать максимально возможное совпадение. Затем одинокие мальчики инициируют признание раунд за раундом, и, если есть лучший матч, предыдущий матч будет отключен. В задаче стабильного брака мы определяем, является ли совпадение хорошим или плохим, а в задаче сопоставления исходного двудольного графа соответствие не является хорошим или плохим. Если мы отбросим вопрос о том, является ли совпадение хорошим или плохим, и будем рассматривать процесс, когда мальчики высокого качества завладевают девушками низших мальчиков, как процесс приспособления к совпадению, то суть этих двух алгоритмов будет почти одинаковой.
Единственное отличие состоит в том, что алгоритм GS выполняет итерации раунд за раундом, пока не будут найдены все узлы. Потому что в задаче сопоставления браков должно быть идеальное решение сопоставления, а в задаче сопоставления двудольных графовИдеальное совпадение не обязательно может существовать. Таким образом, мы не можем сделать это итеративно, но лучше сделать это рекурсивно. Другими словами, венгерский алгоритм изучает общее решение сопоставления двудольных графов, в то время как алгоритм GS является лишь частным случаем алгоритма двудольного графа.
Код
Если усвоить идею венгерского алгоритма, код на самом деле очень простой, то есть простой рекурсивный вызов.
def find_match(x):
for i in range(n):
if graph[x][i] and not tried[i]:
tried[i] = True
if match[i] == -1 or find_match(match[i]):
match[i] = x
return True
return False
for i in range(n):
tried = [0 for _ in range(n)]
find_match(i)
Давайте попробуем снова использовать венгерский алгоритм для решения проблемы стабильности брака, потому что в задаче стабильности брака существует вероятность образования пары между двумя противоположными полами, поэтому нет необходимости судить о ситуации связи. И есть различия в качестве сформированных совпадений, поэтому необходимо снять суждение о том, было ли это опробовано или нет.
girls_matched = [-1 for _ in range(n)]
boys_round = [0 for _ in range(n)]
boys_matched = [-1 for _ in range(n)]
def find_match(x):
for i in range(n):
idx = girls[i].index(x)
mate = girls_matched[i]
mate_id = n+1 if mate == -1 else girls[i].index(mate)
# 如果女孩i没有对象或者是对象比x男生弱
if mate == -1 or (idx < mate_id and find_match(girls_matched[i])):
girls_matched[i] = x
boys_matched[x] = i
return True
return False
for i in range(n):
# 对i男生进行匹配
find_match(i)
Давайте запустим этот код:
Результат, конечно, правильный, но если мы попытаемся продемонстрировать его с помощью алгоритма GSРезультаты двух алгоритмов не совпадают. Почему это? Причина также очень проста, потому что порядок, который выполняют мальчики в алгоритме GS, — это порядок, который им нравится, а венгерский алгоритм — в порядке чисел, поэтому полученные результаты отличаются.
Суммировать
На этом принцип и введение венгерского алгоритма закончены.Для задачи сопоставления двудольных графов у нас есть много алгоритмов для решения, но венгерский алгоритм является одним из самых простых и легких для понимания и реализации. Если мы сравним его с алгоритмом GS, представленным ранее, мы можем найти много общего и связанных частей. Эта статья является лишь кратким введением, и если вы внимательно ее изучите, то найдете много интересных моментов.
Сегодняшняя статья здесь, если вам понравилась эта статья, пожалуйста, приходите на волнукачество три, поддержите меня (Подписывайтесь, делайте репосты, лайкайте).
- END -