MATLAB Answers

regarding munkres function (Hungarian algorithm)

5 views (last 30 days)
Abbi Hashem
Abbi Hashem on 14 Mar 2020
Answered: Elad Kivelevitch on 8 Sep 2020
Now I know how to use the munkres function. But i want it to choose a certain way when there are many possible optimal solutions.
Example:
Initial_Matrix=
[4 3 4 5
4 3 4 5
6 1 2 3
2 9 8 1]
Now there are 2 possible solutions :
1- (1,1) (2,2)(3,3)(4,4) with a total cost of 10
2- (2,1),(1,2)(3,3)(4,4) also total cost of 10
my 2 questions are:
Q1: I want the munkres function to favor the first solution ( that is, I want the lower row cell value to be assigned to a lower column cell value), in case there were multiple optimal solutions like the above. Is there a way to do that?
Q2: on what basis does the munkres function choose in case there were multiple optimal solutions just like the above ?

  0 Comments

Sign in to comment.

Answers (1)

Elad Kivelevitch
Elad Kivelevitch on 8 Sep 2020
Abbi,
You have a couple of options:
If you know for sure that a certain solution should be favored, you can deduct the cost of one of those elements by an eps. The total cost will be 10-eps and that would cause Munkres to choose that one.
c1 = % your matrix
c1(1) = c1(1)-1e-15;
assignmunkres(c1,10)
ans =
4×2 uint32 matrix
1 1
3 2
2 3
4 4
The Munkres algorithm is described by the paper that Munkres wrote, please see the help/doc page.
You can use the other assignment functions we provide: matchpairs, assignjv, assignauction. These may return a different result when the cost is exactly the same. For example:
c1 = % your matrix
assignjv(c1,10)
ans =
4×2 uint32 matrix
1 1
2 3
3 2
4 4
However, the most robust is to simply look at more than optimal solution. You can use assignkbest. This algorithm uses Murti's algorithm to return the top k optimal solutions. For example:
[assignments, ~, ~, cost] = assignkbest(c, 10, 5)
Returns the following result:
assignments =
5×1 cell array
{4×2 uint32}
{4×2 uint32}
{4×2 uint32}
{4×2 uint32}
{4×2 uint32}
cost =
10
10
10
10
12
This indicates that there are 4 solutions with the exact same cost (10).

  0 Comments

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!