Венгерский алгоритм: у меня проблемы с назначением как можно большего числа рабочих мест

Я создал реализацию венгерского алгоритма на C ++. Эта реализация работает очень хорошо для много случаев. Однако в некоторых случаях мой алгоритм вообще не работает, потому что я считаю (и это правда), что моя реализация одного шага алгоритма неверна.

Моя реализация принимает в качестве входных данных массив X, выполняет шаги алгоритма и производит окончательное назначение.

Шаги алгоритма можно найти в вики:Венгерский алгоритм

На шаге 3 он имеет следующий массив затрат (работники представлены строками, а задания — столбцами).

а потом говорит

Initially assign as many tasks as possible then do the following

Однако я не понимаю, что правильный реализация этого будет. Как вы можете назначить как можно больше задач? Будет ли выбор случайным? Тогда, если бы выбор был случайным, я мог бы выбрать первого работника, который займет первую работу, второго работника, который займет четвертую работу, и четвертого работника, который возьмет вторую работу. Итак, второй работник не учтен. Однако в википедии авторы выбрали другой подход. Третий работник должен занять первую работу, второй работник должен занять вторую работу, а четвертый работник — вторую. Итак, первый работник не учтен.

Проблема с выполнением таких случайных действий заключается в следующем:

Предположим, что пока мы запускаем алгоритм и выполняем наши арифметические операции на входе, перед тем, как назначить как можно больше задач работникам, у нас будет следующая матрица затрат:

2 2 0 3
6 1 6 0
0 0 6 1
0 3 5 3

Если я выберу случайным образом назначить третье задание первому работнику, четвертое задание второму работнику, а затем первое задание третьему, у меня останется четвертый работник. Но чтобы алгоритм работал правильно, нам нужно назначить as many jobs to workers as possible, Это тот случай, здесь? Нет, потому что если бы вместо того, чтобы назначить первое задание третьему работнику, я назначил первое задание четвертому работнику, я мог бы затем назначить второе задание третьему работнику, и, таким образом, алгоритм не только назначит столько рабочих мест, сколько возможно но он нашел бы оптимальный результат.

Заключение: Выполнение случайных заданий не является хорошим подходом.

Я немного обыскал это и нашел следующую лекцию:

http://www.youtube.com/watch?v=BUGIhEecipE

В этой лекции профессор предлагает другой подход к проблеме назначения как можно большего количества задач.
По его словам, если какая-либо строка или столбец имеет ровно один ноль, мы сделаем присваивание. Таким образом, начиная с первого ряда, вы проверяете, если первый ряд
имеет только один ноль, если это так, сделайте присваивание. В противном случае проигнорируйте этот ряд и перейдите во второй ряд, сделайте то же самое
повторно сканировать таблицу, пока все нули не будут покрыты из-за назначений.

Следуя этому подходу, можно увидеть, что предыдущий случай раскрыт. Что мы делаем, мы назначаем третью работу первому работнику, четвертую работу второму работнику, затем мы видим, что третий работник может занять 2 работы, поэтому мы некоторое время игнорируем его, назначаем первую работу четвертому работник, а затем вернуться, чтобы назначить второе задание третьему работнику.

Моя реализация следует этой логике, однако, опять же, она не решает все случаи.

Давайте возьмем для примера следующий случай:

0 0 0 0
0 0 0 0
0 0 4 9
0 0 2 3

Первый работник может занять 4 работы, второй 4, третий 2 и четвертый 2. Таким образом, моя реализация не выполняет никаких заданий, потому что мне нужен по крайней мере один работник, который может взять только одну работу, чтобы выполнить назначение, а затем продолжить повторно сканируя таблицу.
Так что мне делать в этом случае? Произвольные задания были бы плохим занятием, к сожалению, в этой лекции ничего не предлагается.
Я мог думать только о следующем:

Для каждого работника есть счетчик, значение которого указывает количество задач, которые могут быть ему назначены, так сколько у нас нулей в этом ряду? это значение счетчика.
Затем начните назначать произвольные задачи работнику с наименьшим счетчиком. Так что в этом случае массив счетчиков для каждого работника будет включать следующие значения:

4
4
2
2

Я бы выбрал например третьего работника и произвольно назначил ему первую работу. Новые счетчики будут:

3
3
0
1

Затем я выбрал бы четвертого работника и выполнил бы единственное доступное ему задание (это вторая работа). Новые счетчики будут:

2
2
0
0

Тогда я мог выбрать либо первого работника, либо второго. Я бы сделал произвольное задание для первого работника и дал бы ему третью работу. Счетчики будут

1
0
0
0

Наконец, я бы дал четвертое задание на первую работу.

Итак, финальные задания:

0 0 0 *
0 0 * 0
* 0 4 9
0 * 2 3

Это кажется хорошим подходом, однако я боюсь, что может быть особый случай, когда этот метод не будет работать. Как я могу проверить, будет ли этот подход работать для всех случаев, и если нет, какой подход полностью решит мою проблему?

заранее спасибо

0 2 0
3 0 0
4 0 0