Maksymalne ważone dopasowanie dwuczęściowe, ograniczenie: porządek każdego wykresu jest zachowywany

Question

Załóżmy, że mam dwa zestawy: (n_1, n_2, ...) i (m_1, m_2, ...) oraz pasujące dopasowanie funkcji (n, m), która zwraca wartość z 0 na 1. Chcę znaleźć odwzorowanie między dwoma zestawami takie, że następujące ograniczenia są spełnione:

• Każdy element musi mieć co najwyżej 1 dopasowany element w przeciwnym zestawie.
• niedopasowane elementy zostaną połączone z manekina elementu na koszt 1
• Suma funkcją match gdy zastosowany do wszystkich elementów jest maksymalna
• Mam problemy Wyrażając to formalnie, ale jeśli w kolejce każdy zestaw równoległe do siebie nawzajem z oryginalnym porządkiem i narysowali linię pomiędzy dopasowanymi elementami, żadna z linii nie przechodziła. Dawny. [n_1 < -> m_2, n_2 < -> m_3] jest prawidłowym mapowaniem, ale [n_1 < -> m_2, n_2 < -> m_1] nie jest.

(wierzę, że trzy pierwsze są standardowe ważone ograniczenia pasujące Dwuczęściowe, ale podano je w przypadku źle zrozumiałem ważonej dopasowanie dwustronnego)

Jest to stosunkowo proste do zrobienia z wyczerpujących poszukiwań w wykładniczym czasie (w odniesieniu do wielkości zestawów), ale mam nadzieję, że istnieje wielomianowy czas (najlepiej rozwiązanie O ((| | | | | m |)^3) lub lepsze).

Szukałem sporej ilości w "problemie przypisania"/"ważonym dopasowaniu dwustronnym" i widziałem zmiany z różnymi ograniczeniami, ale nie znalazłem takiego, które pasowało lub które udało mi się zredukować do jednego z tym dodanym porządkowanie ograniczeń. Czy masz jakieś pomysły na rozwiązanie tego problemu? A może jakiś dowód na to, że nie da się go rozwiązać w czasie wielomianowym (dla moich celów również działałaby redukcja do NP-complete)?

Answer 1

Ten problem został przebadany pod nazwą "dopasowanie maksymalne bez pasowania". Jest prosty program dynamiczny w systemie kwadratowym. Niech M (a, b) ma wartość optymalnego dopasowania na n 1, ..., n a m , ..., m _b. Mamy nawrotowi

M (0, b) = -b
M (a, 0) = -a
M (a, b) = max {f (a - 1 b - 1) + mecz (a, b), M (a - 1, b) - 1, M (a, b - 1) - 1}.

Odszukując argmaxes, można odzyskać optymalne rozwiązanie z jego wartości.

Jeśli wartość dopasowania jest mniejsza niż liczba kwadratowa większa niż -1, istnieje algorytm, który działa w czasie liniowo w liczbie użytecznych wpisów (Khoo and Cong, A Fast Multilayer General Area Router for MCM Designs).