Hungarian algorithm: Difference between revisions

Revision as of 07:19, 4 June 2024

Revision as of 11:30, 18 July 2024

Line 8:

=== Example ===

In this simple example, there are three workers: Alice, Bob and DoraCarol. One of them has to clean the bathroom, another sweep the floors and the third washes the windows, but they each demand different pay for the various tasks. The problem is to find the lowest-cost way to assign the jobs. The problem can be represented in a [[Matrix (mathematics)|matrix]] of the costs of the workers doing the jobs. For example:

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

! {{diagonal split header|Worker    |Task}}

Line 25:

| '''$3'''

|-

! DoraCarol

| $9

| '''$4'''

Line 31:

|}

The Hungarian method, when applied to the above table, would give the minimum cost: this is $15, achieved by having Alice clean the bathroom, DoraCarol sweep the floors, and Bob wash the windows. This can be confirmed using brute force:

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

! {{diagonal split header|Sweep|Clean}}

! Alice

! Bob

! DoraCarol

|-

! Alice

Line 48:

| $18

|-

! DoraCarol

| '''$15'''

| $16

Line 222:

* First + second + third jobs (15):

* clean bathroom: Alice -> 8

* sweep floors: DoraCarol -> 4

* wash windows: Bob -> 3

*/