Higher order Hungarian algorithm?

Question

Ludovic Tenorio 2024-4-9

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2104976-higher-order-hungarian-algorithm

编辑： Aquatris 2024-4-10

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Aquatris 2024-4-10

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2104976-higher-order-hungarian-algorithm#answer_1439161

编辑：Aquatris 2024-4-10

在 MATLAB Online 中打开

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_1 = 2x4
     4    -8     4     0
     2   -13    11     0
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
% winning_2 = [a b c abs(a+b+c)]
winning_2 = [A(idx2) B(idx2) C(idx2) s(idx2)]
winning_2 = 6x4
     4    -8     4     0
     5    -8     4     1
     5   -13     7     1
     2    -8     7     1
     5     3    -9     1
     2   -13    11     0
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>