wybranie najkorzystniejszego zestawu par z 2 zestawów danych

0

Witam. Jestem beznadziejny z algorytmiki, a niestety tutaj jest mi potrzebne mozliwie szybkie rozwiązanie.

Mam 2 zestawy danych na wejsciu:

n m

[1] [1]
[2] [2]
[3] [3]
[4] [4]
[5]

muszę teraz je połączyć w pary (jeden zostanie bez pary) tak aby uzyskać jak największą sumę podobieństwa - dla każdej komórki mam dostęp do informacji o podobienstwiez kazdą z drugiego zestawu. Czy ktoś ma jakiś pomysł lepszy niz sprawdzanie wszystkich kombinacji?

0

Utwórz pełny graf dwudzielny i znajdź w nim minimalne drzewo rozpinające. Dodaj najpierw tyle wierzchołków, aby liczność zbiorów była równa - dodatkowe wierzchołki miałyby np nieskończone niepodobieństwo do każdego innego wierzchołka.

Edit:
Szukaj "maximum weighted bipartite matching" na http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs .

1 użytkowników online, w tym zalogowanych: 0, gości: 1