Hungarian algorithm on jit.matrix
Hi,
I want to use the Hungarian algorithm (https://en.wikipedia.org/wiki/Hungarian_algorithm) in jitter. Basically, a NxN matrix as input would return a size N vector with the colums indices for each row that minimize the cost (as expressed in the input matrix).
The steps to the algorithm are described here, but the iteration process makes it inconvenient with usual objects. However, I don't really like the idea of externals, and would prefer a vanilla Max solution.
What do you think would be the best way to implement that?
jit.gen ? javascript ? node.script ? else ?
Thanks for any advice!
Interesting question.
That would be the start with standard objects:
And a quick shot at finding the columns with two zeros:
Hi Jean-François,
I got roughly to the same point with dimop and stumbled on the
Draw lines through the row and columns that have the 0 entries such that the fewest possible lines are drawn.
... for which I got to this hint:
That's when I started considering jit.gen (or anything to get through) !
Thanks for your patch though: I learnt about the handy "-1" step in jit.dimop (how handy, compared to using jit.matrixinfo to get the dim!) and you reminded me about the equally handy @in2_name. :)
Still stucked on the next steps...
I ended up using javascript and it was pretty much straight forward using a ready-made library like this one : https://github.com/addaleax/munkres-js
It is a bit CPU-greedy and I'll need to see if this can be optimized somehow, but it does the job for now!