regarding munkres function (Hungarian algorithm)

12 views (last 30 days)
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 ?

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).

Categories

Find more on Systems of Nonlinear Equations in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!