Higher order Hungarian algorithm?
2 views (last 30 days)
Show older comments
Say I have 3 vectors that may have different lengths. For example:
a=[ 4 5 2];
b=[-8 -13 3];
c=[ 4 7 -9 11];
How do I find the associations (if any) so that the sum of one element from each vector is:
- Minimized.
- Below a certain threshold (let's say 2 in this example).
Note that once an association is made, those values are removed.
So in this case, you would have two "winning" associations:
- a(1) ,b(1) and c(1): abs(4-8+4) = 0
- a(2), b(2), and c(2): abs(5-13+7) = 1
The possible number of "winning" associations can thus range from 0 up to the length of the shortest vector (3 in this example).
I see how this problem is related to the Hungarian algorithm, but with a cost function that is 3D rather than 2D (which can be solved using the 'matchpairs' function). Or is this more of a shortest path problem? Either way, I'm wondering if there an easy way to solve this.
0 Comments
Answers (1)
Aquatris
on 10 Apr 2024
Edited: Aquatris
on 10 Apr 2024
Somthing like this maybe;
a=[ 4 5 2];
b=[-8 -13 3];
c=[ 4 7 -9 11];
thresholdValue = 2;
[A,B,C] = meshgrid(a,b,c);
s = abs(A+B+C); % absolute sum of all combinations of a b c
idx1 = find(s == min(s,[],'all')); % index for minimum absolute sum
idx2 = find(s < thresholdValue); % index for absolute sum less than threshold
% winning_1 = [a b c abs(a+b+c)]
winning_1 = [A(idx1) B(idx1) C(idx1) s(idx1)]
% winning_2 = [a b c abs(a+b+c)]
winning_2 = [A(idx2) B(idx2) C(idx2) s(idx2)]
0 Comments
See Also
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!