Hungarian algorithm: Difference between revisions

Revision as of 17:21, 7 March 2022

Revision as of 16:55, 3 April 2022

Line 129:

:{|class="wikitable" style="text-align:center"

|-

| 0 ||a2'||a3' 0 ||a4'

|-

|b1'||b2' 0 ||b3'|| 0

|-

|0 0 ||c2'||c3'||c4'

|-

|d1'|| 0 ||d2'||d3'||d4'

|}

In the above case, no assignment can be made. Note that task 1 is done efficiently by both agentagents a and c. Both can't be assigned the same task. Also note that no one does task 3 efficiently.

To overcome this, we repeat the above procedure for all columns (i.e. '''the minimum element in each column is subtracted from all the elements in that column''') and then check if an assignment is possible.

Line 147:

'''All zeros in the matrix must be covered by marking as few rows and/or columns as possible.''' The following procedure is ''one way'' to accomplish this:

*First, assign as many tasks as possible. The assigned tasks are represented by starring a zero.

** We assign the first zero of Row 1. The second zero of Row 1 can't be assigned, because it is on the same line as the first zero.

** We assign the first zero of Row 2. The second zero of Row 2 can't be assigned.

** Zeros on Row 3 and Row 4 can't be assigned, because they are on the same line as the zero assigned on Row 1

We could end with another assignment if we choose another ordering of the rows and columns.

* Row 1 has one zero, so it is assigned. The 0 in row 3 is crossed out because it is in the same column.

* Row 2 has one zero, so it is assigned.

* Row 3's only zero has been crossed out, so nothing is assigned.

* Row 4 has two uncrossed zeros. Either one can be assigned, and then the other zero is crossed out.

Alternatively, the 0 in row 3 may be assigned, causing the 0 in row 1 to be crossed instead.

:{|class="wikitable" style="text-align:center"

|-

| 0'*||a2'||a3' 0 ||a4'

|-

|b1'||b2' 0*||b3'|| 0'

|-

| 0 ||c2'||c3'||c4'

|-

|d1' 0 || 0d2'|| 0 d3'||d4'

|}

* Cover all columns having an assignment (columns 1 and 2).

Now to the drawing part.

* Mark all rows having no assignments (row 3).

* Mark all columns having zeros in newly marked row(s) (column 1).

* Mark all rows having assignments in newly marked columns (row 1).

* Repeat the steps outlined in the previous 2 bullets until there are no new rows or columns being marked.

<!-- this might need to make the borders go away, if the current appearance is thought to be ugly -->

:{|class="wikitable" style="text-align:center"

|- style="background: white"

|&times; ||&times; || || ||

|-

|style="background:lightgrey"| 0*||style="background:lightgrey"|a2'|| 0 ||a4'

| 0'||a2'||a3'||a4'

|style="background: white"|&times;

|-

|style="background:lightgrey"|b1'||style="background:lightgrey"| 0*||b3'|| 0

|b1'||b2'||b3'||0'

|style="background: white"|

|-

|style="background:lightgrey"| 0 ||style="background:lightgrey"|c2'||c3'||c4'

|style="background: white"|&times;

|-

|style="background:lightgrey"| 0 ||style="background:lightgrey"|d2'||d3'||d4'

|d1'||0' ||0||d4'

|style="background: white"|

|}

* Find a non-covered zero and prime it. If the zero is on the same line as a starred zero, cover the corresponding line, and uncover the column of the starred zero.

Now draw lines through all marked columns and '''unmarked''' rows.

**Here, the second zero of Row 1 is uncovered. Because there is another zero starred on Row 1, we cover Row 1 and uncover Column 1.

**Then, the second zero of Row 2 is uncovered. We cover Row 2 and uncover Column 2.

:{|class="wikitable" style="text-align:center"

|- style="background: white"

|&times; | ||&times; || || ||

|- style="background:lightgrey"

| 0*||a2'|| 0'||a4'

|style="background: white"|&times;

|-

|b1'||style="background:lightgrey"| 0'*||a2b3'||a3'||a4' 0

|style="background: white"|

|-

|| 0 ||style="background:lightgrey"|c2'||c3'||c4'

|style="background: white"|

|-

|| 0 ||style="background:lightgrey"|d2'||d3'||d4'

|style="background: white"|

|}

:{|class="wikitable" style="text-align:center"

|- style="background: white"

|| || || || ||

|- style="background:lightgrey"

| 0*||a2'|| 0'||a4'

|style="background: white"|&times;

|- style="background:lightgrey"

|b1'||b2' 0*||b3'|| 0'

|style="background: white"|&times;

|-

|style="background:lightgrey"| 0 ||c2'||c3'||c4'

|style="background: white"|

|-

|| 0 ||d2'||d3'||d4'

|style="background: white"|

|}

* If a non-covered zero has no assigned zero on its row, perform the following steps :

** Step 1: Find a starred zero on the corresponding column. If there is one, go to Step 2, else, stop.

** Step 2: Find a primed zero on the corresponding row (there should always be one). Go to Step 1.

The zero on Row 3 is uncovered. We find on the path the first zero of Row 1, then the second zero of Row 1, then we are done.

:{|class="wikitable" style="text-align:center"

|- style="background: white"

|| || || || ||

|- style="background:lightgrey"

| <span style="color:red">0*</span> ||a2'|| <span style="color:red">0'</span> ||a4'

|style="background: white"|&times;

|- style="background:lightgrey"

|d1b1'||0' 0*||0b3'||d4 0'

|style="background: white"|&times;

|-

|| <span style="color:red">0'</span> ||c2'||c3'||c4'

|style="background: white"|

|-

|| 0 ||d2'||d3'||d4'

|style="background: white"|

|}

* For all zeros encountered during the path, star primed zeros and unstar starred zeros, remove all covered lines and primed zeros.

**As the path begins and ends by a primed zero when swapping starred zeros, we have assigned one more zero.

:{|class="wikitable" style="text-align:center"

|-

| 0 ||a2'|| 0*||a4'

|-

|b1'|| 0*||b3'|| 0

|-

|| 0*||c2'||c3'||c4'

|-

|| 0 ||d2'||d3'||d4'

|}

* Repeat the previous steps

** we cover columns 1, 2 and 3. The second zero on Row 2 is uncovered, so we cover Row 2 and uncover Column 2

:{|class="wikitable" style="text-align:center"

|- style="background: white"

||&times; || ||&times; || ||

|-

|style="background:lightgrey"| 0 ||a2'||style="background:lightgrey"| 0*||a4'

|style="background: white"|

|- style="background:lightgrey"

|b1'|| 0*||b3'|| 0'

|style="background: white"|&times;

|-

|style="background:lightgrey"| 0*||c2'||style="background:lightgrey"|c3'||c4'

|style="background: white"|

|-

|style="background:lightgrey"| 0 ||d2'||style="background:lightgrey"|d3'||d4'

|style="background: white"|

|}

All zeros are now covered with a minimal number of rows and columns.

The aforementioned detailed description is ''just one way'' to draw the minimum number of lines to cover all the 0s. Other methods work as well.