Взвешенное двудольное соответствие

Question

Я знаю, что существует много подобных тем. Но большинство из них оставили мне некоторые сомнения в моем случае. Я хочу найти идеальное совпадение (или как можно ближе к совершенству, если нет идеального совпадения), а затем из всех тех совпадений, в которых вы можете сопоставить k из n вершин (где k максимально возможно), Я хочу выбрать максимально возможный общий вес. Так просто поставить то, что я хочу сказать следующее: приоритет

1. Матча, как много вершин в качестве возможных
2. Потому что (не взвешенное) максимальное соответствие в большинстве случаев однозначно, я хочу выбрать тот, который имеет самое большой сумма весов на ребрах. Если их несколько с одинаковым весом, не имеет значения, что будет выбрано.

Я слышал о алгоритме Форда-Фулкерсона. Это работает так, как я описываю это, или мне нужен другой алгоритм?

Answer 1

Если вы реализуете это самостоятельно, вы, вероятно, захотите использовать Hungarian algorithm. Быстрые алгоритмы существуют, но их не так просто понять или реализовать.

Ford-Fulkerson - алгоритм максимального потока; вы можете легко использовать его для решения невзвешенного соответствия. Включение его в алгоритм взвешенного matcing требует дополнительного трюка; с этим трюком вы завершаете венгерский алгоритм.

Вы также можете использовать алгоритм с минимальным издержками для взвешивания двухстороннего соответствия, но он может работать не так хорошо. Существует также сетевой симплекс-метод, но он, по-видимому, в основном имеет исторический интерес.