Венгерский алгоритм тупик

Question

Я следую руководству по Youtube of the Indian guy about the Hungarian problem. Я складываю в том месте, где он решает, какие строки и столбцы будут выбраны для следующего шага. Его пример не имеет проблемы, с которой я столкнулся. Вот таблица моего примера:

2 1 0 0 0 3 
2 0 4 5 2 7 
0 7 0 0 0 5 
3 2 3 1 2 0 
0 0 6 3 3 5 
3 4 5 2 0 3 

Итак, давайте начнем шаг строк и столбцов выбор за шагом:

1. первая строка содержит> 1 нули => перейти к следующей строке
2. выберите (2,1) равна нулю и добавьте (5,1) для подвесных нулей
3. третья строка содержит> 1 нули => перейти к следующей строке
4. выберите (4,6) равна нулю
5. выберите (5,1) г эро и добавить (3,1) к взвешенным нулям
6. выберите (6,5) нулевые и добавляют (3,5), (1,5) для подвесных нулей

Теперь, нули, которые остались (1,3), (1,4), (3,3), (3,4)

Я не могу найти способ справиться с ними, ни с помощью столбца, ни мудрости, ни ряда. Что мне делать с ними?

Вот таблица, в конце концов:

2  1  0? 0? 0(su) 3 
3  0(se) 4  5  2  7 
0(su) 7  0? 0? 0(su) 5 
3  2  3  1  2  0(se) 
0(se) 0(su) 6  3  3  5 
3  4  5  2  0(se) 3 

где

• су = подвешенный
• SE = выбран
• ? = То, что я предполагаю сделать

Answer 1

В этом конкретном примере, мы можем просто произвольно выбрать 0. Выбор левый верхний один дает нам

2  1  0(se) 0(su) 0(su) 3 
3  0(se) 4  5  2  7 
0(su) 7  0(su) 0? 0(su) 5 
3  2  3  1  2  0(se) 
0(se) 0(su) 6  3  3  5 
3  4  5  2  0(se) 3 

Затем мы можем выбрать конечный свободный 0 и быть сделанный.

Это не всегда работает. Рассмотрим

0 0 0 0 
0 0 0 0 
0 0 1 2 
0 0 3 4 

(Если вы предпочитаете видео, я использую ту же проблему, как here, хотя я на самом деле решить эту проблему.)

Мы ничего не можем выбрать с самого начала, поэтому мы произвольно выбираем первый 0.

0(se) 0(su) 0(su) 0(su) 
0(su) 0  0  0 
0(su) 0  1  2 
0(su) 0  3  4 

Теперь мы можем выбрать (1,3), потому что это единственный свободный 0 в своей строке.

0(se) 0(su) 0(su) 0(su) 
0(su) 0(su) 0  0 
0(su) 0(se) 1  2 
0(su) 0(su) 3  4 

, а затем (3,1), потому что это единственный свободный 0 в своей колонке.

0(se) 0(su) 0(su) 0(su) 
0(su) 0(su) 0(se) 0(su) 
0(su) 0(se) 1  2 
0(su) 0(su) 3  4 

Это дает нам 3 полных заданий, но нам нужно 4 для решения, и не более доступны 0, чтобы назначить. Вполне возможно, что на данный момент решения нет, поэтому нам нужно продолжить в венгерском алгоритме на шаг рисования линии.

Профессор Г. Шринивасан просматривает это в видео, которое я связал, поэтому я перейду к результату. Если количество строк, нарисованных больше, чем количество назначений, которые мы ищем, мы продолжим работу с остальной частью Венгерского алгоритма; если он меньше, что-то пошло не так на предыдущем шаге, и вы должны вернуться и проверить свою работу; но если он равен (как в этом примере), то мы знаем, что здесь есть оптимальное решение, которого мы не нашли.

Мое решение проблемных произвольных присвоений - более произвольные назначения. 4-я строка является единственной в этой точке без назначения, поэтому мы начнем с нее и назначим ее первый 0 (приостановленные 0 не имеют значения сейчас, поэтому я не отметил их).

0(se) 0  0  0 
0  0  0(se) 0 
0  0(se) 1  2 
0(se) 0  3  4 

Это, очевидно, проблематично, поскольку мы уже выполнили задание в первом столбце. Чтобы исправить это, нам нужно переместить один из них в другое место. К счастью, у 4-й строки все еще нет заданий, а (1,4) равно нулю, поэтому мы можем переместить назначение в (1,1) - (1,4).

0  0  0  0(se) 
0  0  0(se) 0 
0  0(se) 1  2 
0(se) 0  3  4 

В настоящее время конфликтов нет, и у нас есть 4 задания, поэтому это наше решение.