Ważone dopasowanie dwudzielne

Question

Jestem świadomy, że istnieje wiele podobnych tematów. Ale większość z nich pozostawiła w moim przypadku wątpliwości. Co chcę zrobić, to znaleźć idealne dopasowanie (lub jak najdoskonalej, jak to tylko możliwe w przypadku, gdy nie ma idealnego dopasowania oczywiście), a następnie ze wszystkich tych dopasowań, w których można dopasować k z n wierzchołków (gdzie k jest najwyższym możliwym), Chcę wybrać najwyższą możliwą całkowitą wagę. Więc po prostu umieścić, co mówię jest następujący priorytet:

1. dopasować tak wiele wierzchołków jako możliwe
2. powodu (nie ważona) maksymalne dopasowanie w większości przypadków jest jednoznaczna, chciałbym wybrać ten, który ma największy suma wag na krawędziach. Jeśli jest ich kilka o tej samej wadze, nie ma znaczenia, który byłby wybrany.

Słyszałem o algorytmie Forda-Fulkersona. Czy działa tak, jak to opisuję, czy potrzebuję innego algorytmu?

Answer 1

Jeśli implementujesz to samodzielnie, prawdopodobnie będziesz chciał użyć Hungarian algorithm. Szybsze algorytmy istnieją, ale nie są tak łatwe do zrozumienia i wdrożenia.

Ford-Fulkerson jest algorytmem maksymalnego przepływu; możesz go łatwo użyć do rozwiązania dopasowania nieważonego. Włączenie go do ważonego algorytmu matowania wymaga dodatkowej sztuczki; z tą sztuczką, skończysz z węgierskim algorytmem.

Można również użyć algorytmu przepływu minimalnego, aby wyważone dopasowanie dwustronne, ale może nie działać równie dobrze. Istnieje również metoda sieciowa simpleks, ale wydaje się, że jest to głównie kwestia historyczna.