Hungarian Algorithm - Arbitrary Choices -

i've looked @ several explanations of hungarian algorithm solving assignment problem , vast majority of these cover simplistic cases.

the understandable explanation i've found youtube video.

i can code algorithm i'm concerned 1 special case. if watch video, relevant case explained 31:55 37:42, i’ll explain below.

i should first mention dealing 300 x 300 matrix, visual inspection out of question. additionally, need find all minimum assignments. in other words, if there multiple assignments produce same minimum value, need find them all.

here's particular case i'm concerned about. can see explained in youtube video i’ll go on here. start matrix:

3   1   1   4 4   2   2   5 5   3   4   8 4   2   5   9 

when reduce rows , columns, this:

0   0   0   0 0   0   0   0 0   0   1   2 0   0   3   4 

(let me mention can visually see there 4 solutions matrix , total score 13.)

given above reduced matrix, there no unique zeros in row or column, so, according algorithm described in video, can arbitrarily select 0 element assignment, select (1,1).

i’ll mark assigned 0 asterisk , i’ll put “x” next zeros in rows , columns no longer available consideration. have this:

0*  0x  0x  0x 0x  0   0   0 0x  0   1   2 0x  0   3   4 

next, continue examining rows unique zero. find 1 @ (3,2) mark asterisk , mark unavailable zeros "x":

0*  0x  0x  0x 0x  0x  0   0 0x  0*  1   2  0x  0x  3   4 

next, start looking unique zeros in columns (since rows have been exhausted). find column 3 has unique 0 @ (2,3) mark it:

0*  0x  0x  0x 0x  0x  0*  0x 0x  0*  1   2 0x  0x  3   4 

at point, there no more available zeros , row 4 has been left unassigned. (this particular youtube video uses “ticking procedure”, common technique determining minimum number of lines needed cover zeros. if unfamiliar technique explained starting @ 14:10 through 16:00, although presenter uses different matrix shown here.) “ticking procedure” this:

1. tick rows have no assigned zeros (row 4).
2. for each row ticked, tick columns contain 0 in row.
3. for each column ticked in step 2, tick corresponding rows have assigned zeros.
4. repeat steps 2 , 3 until no more ticking possible.
5. draw lines through ticked columns , un-ticked rows.

at point, ticking procedure generates 4 vertical lines, covering zeros. 4 vertical lines tell zeros in matrix represent 1 or more solutions, yet, see, row 4 unassigned. fact fourth row remains unassigned in spite of 4 vertical lines tells chose wrong zeros assignment!

the video’s presenter indicates problem result of our initial (arbitrary) assignment of element (1,1). presenter says, “there more sophisticated methods available” out of situation not explain these techniques are. alludes existence of “intelligent” ways of selecting zero, rather arbitrary selection used select 0 @ (1,1).

one approach take (i’m not sure it’s best) when faced making arbitrary assignment make assignment row or column fewest number of available arbitrary choices. in example, means make arbitrary assignment either row 3 or 4, there 2 arbitrary choices, rather row 1 or 2 there 4 arbitrary choices. of course, since need correct solutions, have iterate on available arbitrary assignments, whenever arbitrary assignment made. example, if select (3,1) arbitrary assignment, have assign (3,2) later.

my question then, after this, is, when faced choice of arbitrarily selecting 0 assignment, best approach? mention in previous paragraph? how can eliminate dead-end solutions 1 shown? please remember still need enumerate solutions having same minimal score.

once subtraction steps have been performed on rows , columns did, there step in algorithm, requires find minimum number of rows or columns can strike out find no more zeroes in cells left on (see step 3 in wikipedia article). if minimum number of strike-out rows/columns equals n, have arrived @ matrix assignments can made @ positions all represented zeroes.

this case in second matrix.

then there algorithm step once have done subtraction steps possible: if row or column has 1 zero, 0 represents (optimal) assignment.

i think rule can generalised follows:

if i rows (or columns) each have @ i zeroes, i of zeroes represent (optimal) assignments.

that rule obvious (and utterly unhelpful) when i n.

but small i, can helpful, although algorithm find such rows may time consuming. in example problem, find i = 2 rule applies rows 3 , 4. rule implies can bar other assignments in columns contain zeroes. means can write our matrix as:

-   -   0   0 -   -   0   0 0   0   1   2 0   0   3   4 

now rule can applied again rows 1 , 2, each have 2 zeroes.

we see 2 sub-matrixes of zeroes (subject of applied rule):

0   0 0   0 

there 2 ways make assignments:

x   0 0   x 

or:

0   x x   0 

in general, sub-matrix i rows , i columns, there i! solutions if elements zero, fewer of them not.

in concreate example, there 2! solutions bottom-left sub-matrix, , 2! top-right matrix, resulting in 4 possible solutions.

conclusion

although above considerations may sound interesting, don't think algorithm searches such sub-matrixes more performant algorithm picks assignments in ordered fashion, , backtracks finds on wrong track. need solutions, there no sense in starting row. backtracking should make sure algorithm not waste time on choices have no future.