wybranie najkorzystniejszego zestawu par z 2 zestawów danych

Odpowiedz Nowy wątek
2012-08-22 17:20
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?

Pozostało 580 znaków

2012-08-22 17:32
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/[...]matchings_in_bipartite_graphs .


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 3x, ostatnio: Wibowit, 2012-08-22 17:38

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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