{"id":1319,"date":"2016-02-02T17:26:34","date_gmt":"2016-02-02T16:26:34","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1319"},"modified":"2022-12-03T22:58:51","modified_gmt":"2022-12-03T21:58:51","slug":"algorithme-hongrois","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/planning-problem\/algorithm-hungarian\/","title":{"rendered":"Hungarian algorithm"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1319\" class=\"elementor elementor-1319\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c0343d1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c0343d1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-000d4ba\" data-id=\"000d4ba\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5ff45da elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5ff45da\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\"> Planning problem<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-884f774\" data-id=\"884f774\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-73ada20 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"73ada20\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-b4f726e\" data-id=\"b4f726e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4750b98 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"4750b98\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_hongrois\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-efffc50 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"efffc50\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-72724cc2\" data-id=\"72724cc2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5efa6b99 elementor-widget elementor-widget-text-editor\" data-id=\"5efa6b99\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/algorithm-hungarian\/#Algorithme-hongrois\" >Hungarian algorithm<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/algorithm-hungarian\/#Etape-1-algorithme-hongrois-reduction-du-tableau-initial\" >Step 1 Hungarian algorithm: reduction of the initial table<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/algorithm-hungarian\/#Etape-2-algorithme-hongrois-rechercher-une-solution-realisable\" >Hungarian Algorithm Step 2: Find a Workable Solution<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/algorithm-hungarian\/#Etape-3-algorithme-hongrois-creation-des-pivots\" >Step 3 Hungarian algorithm: creation of the pivots<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/algorithm-hungarian\/#Etape-4-algorithme-hongrois-modification-du-tableau\" >Step 4 Hungarian algorithm: modification of the table<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-hongrois\"><\/span>Hungarian algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Also called <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> of K\u00fchn, the Hungarian algorithm, or Hungarian method solves assignment problems of the cost table type. Consider a number of machines and as many tasks. Each machine performs a task at a certain cost. The objective is to determine the machine on which each task will run, in parallel.<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">This problem being similar to a coupling problem in a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a>, it meets K\u00f6nig&#039;s criterion for nodal coverage of minimum weight. The objective is therefore to find one item per row and column in the table such that the sum of the costs is minimal. If we start from a maximization problem, it will be necessary to reverse the costs in order to fall back on a problem of <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/minimization-dun-afd\/\">minimization<\/a>.<\/div>\n\n<p>Let us take a simple example in order to show the process of the algorithm. Let 5 machines (row) and 5 tasks (column) give the following cost table:<\/p>\n\n<div class=\"standard\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">16<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">16<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">13<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">13<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-1-algorithme-hongrois-reduction-du-tableau-initial\"><\/span>Step 1 Hungarian algorithm: reduction of the initial table<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">We subtract from each line the smallest element of the line. The more we subtract from each column the smaller element of the column.<\/div>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>5<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">13<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>This standardization of machine and task costs makes it possible to have at least one zero per row and per column.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-2-algorithme-hongrois-rechercher-une-solution-realisable\"><\/span>Hungarian Algorithm Step 2: Find a Workable Solution<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>We are looking for the line with the fewest non-crossed zeros. In the event of a tie, we will take the highest line.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>We surround one of the zeros of this line (arbitrarily the one furthest to the left).<\/li>\n<li>All zeros in the same row and column as the one selected are crossed out.<\/li>\n<li>We start again until all the zeros are boxed or crossed out.<\/li>\n<\/ol>\n<\/div>\n\n<p>If we have framed a zero by row and by column, we have an optimal solution. Otherwise we go to step 3.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>5<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">13<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-3-algorithme-hongrois-creation-des-pivots\"><\/span>Step 3 Hungarian algorithm: creation of the pivots<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>The sub-table allows by subtraction to have a configuration making it possible to find an optimal solution. The construction of the pivots is done as follows:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>We mark any line that does not contain any framed zero.<\/li>\n<li>Any column with a crossed out zero is marked on a marked row.<\/li>\n<li>We mark any row having a framed zero in a marked column.<\/li>\n<li>Repeat 2 and 3 until no more changes.<\/li>\n<\/ol>\n<\/div>\n\n<p>A line is then drawn on any unmarked line and on any marked column. In our example, row 1 and 2 are marked, as well as column 4. Double-marked items are marked with a star.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>5<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">-7-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-9-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-9-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">*-6-*<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #000000;\">-0-<\/span><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-3-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-10-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">*-13-*<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-9-<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">-5-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">*-4-*<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-9-<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-4-algorithme-hongrois-modification-du-tableau\"><\/span>Step 4 Hungarian algorithm: modification of the table<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>The cells not crossed by a line constitute a partial table.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>We subtract from all the boxes of this table the smallest element thereof.<\/li>\n<li>This element is added to all the boxes of the table crossed out in both directions (accompanied by a star).<\/li>\n<\/ol>\n<\/div>\n\n<p>Steps 2 to 4 are repeated until an optimal result is obtained. In our example, we get an optimal result after the first iteration.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td>1<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>The minimum allocation is calculated from the initial table: 9 + 5 + 5 + 4 + 9 = 32.<\/p>\n<p>The following figure shows the changes in the bipartite graph with the Hungarian algorithm.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-9818 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/16-Figure7-1.png\" alt=\"Hungarian algorithm K\u00fchn&#039;s algorithm Hungarian method assignment problems K\u00f6nig&#039;s criterion\" width=\"874\" height=\"746\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/16-Figure7-1.png 874w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/16-Figure7-1-300x256.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/16-Figure7-1-768x656.png 768w\" sizes=\"(max-width: 874px) 100vw, 874px\" \/><\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Scheduling problem Home page Wiki Hungarian algorithm Also called K\u00fchn&#039;s algorithm, the Hungarian algorithm, or Hungarian method solves table-like assignment problems \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":868,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1319","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1319","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=1319"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1319\/revisions"}],"predecessor-version":[{"id":17917,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1319\/revisions\/17917"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/868"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=1319"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}