search

hrldcpr / hungarian

Hungarian / Munkres' algorithm for the linear assignment problem, in Python
MIT License
71 stars 22 forks source link

Wrong result for example? #4

Closed sumpfork closed 8 years ago

sumpfork commented 8 years ago

It may be that I'm not understanding how to use this code correctly, but as I'm interpreting the output on the example included with this package it is not optimal. The scipy implementation finds the correct one.

In [1]: import numpy as np

In [2]: import hungarian

In [3]: from scipy.optimize import linear_sum_assignment

In [4]: inf = 1000

In [5]: a = np.array( [[inf,2,11,10,8,7,6,5],
                  [6,inf,1,8,8,4,6,7],
                  [5,12,inf,11,8,12,3,11],
                  [11,9,10,inf,1,9,8,10],
                  [11,11,9,4,inf,2,10,9],
                  [12,8,5,2,11,inf,11,9],
                  [10,11,12,10,9,12,inf,3],
                  [10,10,10,10,6,3,1,inf]] )

In [6]: sorted(zip(*hungarian.lap(a)))
Out[6]: [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (6, 6), (7, 7)]

In [7]: sorted(zip(*linear_sum_assignment(a)))
Out[7]: [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (6, 7), (7, 6)]

In [8]: sum(a[hungarian.lap(a)])
Out[8]: 2013

In [9]: sum(a[linear_sum_assignment(a)])
Out[9]: 17
sumpfork commented 8 years ago

Seems like I'm misunderstanding the output of this algorithm - sum(a[range(8),hungarian.lap(a)[0]]) gives the correct sum.

hrldcpr commented 8 years ago

Ah okay, thanks for looking into it.

Now that scipy has their own hungarian implementation I should probably just deprecate this package in favor of theirs, so thanks for alerting me to that as well.

sumpfork commented 8 years ago

Please do not - the scipy one is incredibly slow on large problems.

This package runs in about 36 minutes on my matrix, I have yet to see the scipy one return after a day or running.

I'm also trying the dlib one now, as it has python bindings through boost-python.

hrldcpr commented 8 years ago

Interesting! Alright I'll keep it alive then, and maybe see if I can speed up scipy's version too…

sumpfork commented 8 years ago

I think scipy adopted https://github.com/ben-eysenbach/munkres which is pure python. I had fixed it up for my own use before I noticed it in scipy, but it was already way too slow.

And for the record, while dlib is slightly faster on than this project on a smaller matrix, it is already 4 minutes slower on my system (11.5 vs 7.5 minutes) on a 10k x 10k matrix.