The Munkres Assignment Algorithm (Hungarian Algorithm)

the monk res assignment algorithm also known as the Hungarian algorithm let's start with the problem imagine you own an Internet service provider and as part of your package offer free installations for your latest Wi-Fi hub in one area there are three installation jobs pending additionally you have three workers in the area for completing the jobs each work has a cost associated with traveling to each of the three jobs for example for local one it costs 40 pounds to travel its job 160 pounds to travel to job 2 and 15 pounds of drivers job 3 here are the travel cost for all the workers since you are covering the costs of the installation you want to sign the workers to each job in a way that minimizes the overall travel costs it is easier to solve this problem by representing it as an n by n matrix where in this case N equals 3 here the rows represent workers and the columns represent the jobs the problem constitutes that no two workers be assigned the same job and no two jobs be assigned to the same workers this is a correct assignment here we can add all the cost to produce the overall travel cost so for this assignment it is 95 pounds there's another assignment this assignment is 115 pounds we calculate the cost of all six iterations we can find the assignment which produces the minimal overall cost the optimal solution we can see for that this problem it is 70 pounds giving us an assignment of what one's job three worker toots job on and worker three to job T great we have solved our problem however this is a problem for where N equals three for small n this method may suffice but the larger n say a hundred it does not in general for an M by n matrix we have n assignments to choose from in the first column then n minus one in the second column since we cannot choose the same assignment chosen in the first column then n minus two in the third column and so on and so forth until we breach 1 this is n factorial giving us a time complexity of Big O of n factorial this is not good so problems with larger and more efficiently we need the moon Cora's assignment algorithm let's use the monkeys algorithm to solve the problem step one row reduction we're first going to find the minimum of each row we're then going to subtract each rows minimum from every value in that row this means that each row now contains at least one zero for now I'm going to repeat step one but on the columns rather than the rows first find the minimum of each column then subtract each columns minimum from every value in that column this means that each column now contains at least one zero step three test for an optimal assignment to do this we draw the minimum number of straight lines on the matrix to cover all the zeros if the number of lines is equal to the number of rows and columns an optimal assignment can be made and we can skip to step 5 in our example we have covered the zeros using three lines this is equal to the number of rows and columns so we can skip to step five later on we go through an example where step four will be required step 5 making the final assignment we choose n zeros where n is the number of rows and columns whilst ensuring that each row and column of the matrix only contains one chosen zero in our example the chosen zeros have starred these chosen zeros represent our final assignments of workers to jobs to obtain the total minimum cost we sum the values of the original matrix that are in the same positions as our chosen zeros what happens if during step three the number of lines is less than n let's find out using a new example step one row reduction subtract the row minimums from each rows values step two column reduction subtract the column minimums from each columns values step three test for an optimal assignment cover the zeros with straight lines in this case the number of lines is less than n so we go to step four Step four shift zeros we need to shift at least one zero to an uncovered position in order to increase the minimum number of lines required to cover all of the zeros to do this we first find the smallest uncovered value in this case five this value is then subtracted from all the uncovered values and added to each value situated at the intersection of two lines the lines are then removed and we jump back to step three step three test for an optimal assignment step three covers the zeros with three lines so we jump to Step five step 5 making the final assignment during step five you may find more than one way of choosing n zeros as is the case with this example this is OK as all the choices will have the same total cost problem what happens if you have more workers than jobs or jobs than workers simply add extra rows or columns fill the zeros and discard any assignments of these in the final solution step one and two involves scanning and adjusting each value of the matrix as there are n squared values time complexity is Big O of N squared step three covers the zeros with lines it can do this by visiting each 0 of which there at most N squared and covering it if not already covered step 4 scans and adjust at most Big O of M squared values thus both step 3 and 4 a Big O of N squared steps 3 & 4 also iterates while the number of lines is less than n each iteration causes the number of lines to increase by at least one therefore there are at most Big O of n iterations each of which is Big O of N squared meaning Big O of n cubed in total step 5 sums n values of the original matrix thus is Big O of n the overall complexity is therefore Big O of n cubed so there we have it we've shown how to use the Monk Reza Simon algorithm and that it is an efficient method to solve the assignment problem thank you for watching you

Channel: CompSci

Views: 64,963

Keywords: Computer Science, Algorithms, Programming, Time Complexity, Munkres, Munkres Assignment, Hungarian Algorithm, Algorithm, funny cat videos, Hungarian, Assignment, Data Structures, DSA, Computer, hungarian, algorithm, hungarian algorithm, munkres, assignment, munkres assignment, video, tutorial, lesson, teach, time, time complexity, big oh

Id: cQ5MsiGaDY8

Length: 7min 50sec (470 seconds)

Published: Tue Jan 12 2016