Aand Bare sets of Ndimensional vectors ( N=10), |B|>=|A|( |A|=10^2, |B|=10^5). The similarity method sim (a, b) is a point product (required). The task is as follows: for each vector Ain, Afind the vector Bin B, so that the sum of the similarities of ssall pairs is maximum.
My first attempt was a greedy algorithm:
- find the pair with the highest affinity and remove this pair from A, B
- repeat (1) until A is empty.
But such a greedy algorithm in this case is suboptimal:
a_1 = [1, 0]
a_2 = [. 5, .4]
b_1 = [1, 1]
b_2 = [. 9,0]
sim (a_1, b_1) = 1
sim (a_1, b_2) =. 9
sim (a_2, b_1) =. 9
sim (a_2, b_2) =. 45
[a_1,b_1] [a_2, b_2], ss=1.45, ss=1.8.
?