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

Я слежу за учебником на Youtube индийского парня о венгерской проблеме. Я складываю в точке, где он решает, какие строки и столбцы будут выбраны для следующего шага. В его примере нет проблемы, с которой я сталкиваюсь. Вот таблица моего примера:

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 = выбран
  • ? = что я должен делать
Источник

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

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

Мы не можем ничего выбрать с самого начала, поэтому мы произвольно выбираем первый 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 для назначения. Возможно, что на данный момент нет решения, и поэтому нам нужно перейти к алгоритму венгрии до этапа рисования линий.

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

Мое решение проблемных произвольных назначений, это больше произвольных назначений. Четвёртая строка является единственной на данный момент без назначения, поэтому мы начнем там и назначим ей первые 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 задания, так что это наше решение.

Источник
Другие вопросы по тегам