Hungarian Algorithm Example

Let four teacher (T1, T2, T3, and T4) require through four subject (S1, S2, S3, and S4), one teacher for each subject. The matrix exhibits the actual cost associated with assigning a particular subject to particular teacher. The objective would be to minimize the total cost from the assignment.

We will describe the particular Hungarian algorithm by using this example.

Step1: Subtract row minima

All of us begin with subtracting the row minimum through every row. The smallest element within the very first row is, for instance, 69. Consequently, all of us subtract 69 through every element within the first row. The particular resulting matrix will be:

Step2: Subtract column minima

Similarly, we subtract the column minimal through every column, providing the next matrix:

Step3: Cover all zeros with a minimum number of lines

We will now determine the particular minimum number associated with horizontal or even vertical lines which have to cover all zeros within the matrix. All zeros could be included making use of 3 lines:

Since the number associated with lines required (3) is lower than the size of the matrix (n=4), we continue with Step 4.

Step4: Create additional zeros

Initial, we all realize that the particular smallest uncovered number is 6. We subtract this number from all uncovered elements and also increase that to be able to all elements which can be included twice. This results in the following matrix:

Now we go to the Step3.

Step3: Cover all zeros with a minimum number of lines

Again, we determine the minimum quantity of outlines necessary to include just about all zeros within the matrix. Now there tend to be 4 lines needed:

Simply because the amount of lines required (4) equals the size from the matrix (n=4), an optimal assignment exists among the zeros in the matrix. Consequently, the algorithm stops.

The optimal assignment

The following zeros cover an optimal assignment:

This corresponds to the following optimal assignment within the original cost matrix:

Therefore, S1 must execute T3, S2 T2, S3 T1, as well as S4 must execute T4. The entire cost of this optimal assignment is to {69 + 37 + 11 + 23} = 140.