Maximum number of matched pairs between two lists

Правка en1, от AhmadYahya, 2019-11-22 23:45:37

Hello,

If I have 2 arrays of frames, namely, A and B. Each element of an array represents a frame.

and a function calc_sim(frame_i, frame_j) that measures the similarity between two frames.

frame_i and frame_j are matched if their similarity is above 50%.

How can one measure the maximum number of matched pairs between the arrays A and B (of course knowing that if an element is already in a pair, it can’t be used again)?

A greedy solution won’t work here because choosing a frame may affect badly other frames, and the only optimal solution I can think of is trying all the possibilities which is O(n!).



Is there a better solution or is it an NP problem?

Thanks in advance.

Теги #help, pair, np-hard

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский AhmadYahya 2019-11-22 23:45:37 755 Initial revision (published)