Покрытие нулей минимальными строками по венгерскому методу

Question

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

1. Отметьте все неназначенные строки.
2. Если отмеченная строка имеет нули, отметьте соответствующий столбец.
3. В отмеченном столбце, если есть назначение, отметьте соответствующую строку.
4. Нарисуйте линию над каждой не отмеченной строкой и отмеченным столбцом.
5. Повторите для каждого неназначенного ряда.
6. Затем найдите тэту (которая является наименьшим непокрытым значением)

Проблема в том, что когда я это делаю, у меня все еще есть нули! в результате чего Theta становится равным нулю и идет бесконечный цикл!

Например, если мы возьмем следующую матрицу 25 на 25):

1 5 5 2 3 1 2 3 2 4 5 2 3 1 5 5 2 3 1 5 1 4 3 2 5

5 5 3 2 3 2 5 1 4 3 2 5 3 2 4 5 2 5 2 1 1 4 1 2 5

5 1 4 3 2 5 1 1 4 1 2 5 2 2 3 4 1 4 5 3 2 4 5 2 5

1 1 4 1 2 5 3 2 4 5 2 5 5 5 1 5 1 5 5 2 2 3 4 1 4

3 2 4 5 2 5 2 2 3 4 1 4 5 4 2 1 3 2 5 5 5 1 5 1 5

2 2 3 4 1 4 5 5 1 5 1 5 5 5 2 5 5 1 4 5 4 2 1 3 2

5 5 1 5 1 5 5 5 3 2 3 2 1 5 5 1 5 1 5 5 5 2 5 5 1

5 4 2 1 3 2 5 1 4 3 2 5 5 5 4 2 1 3 2 5 1 4 3 2 5

5 5 2 5 5 1 1 1 4 1 2 5 1 5 5 2 5 5 1 1 1 4 1 2 5

2 4 5 3 4 2 3 2 4 5 2 5 2 2 4 5 3 4 2 3 2 4 5 2 5

2 2 5 5 1 3 2 2 3 4 1 4 2 2 2 5 5 1 3 2 2 3 4 1 4

4 1 5 4 5 3 5 5 1 5 1 5 5 4 1 5 4 5 3 5 5 1 5 1 5

5 1 4 3 2 5 3 2 4 5 2 5 5 5 1 4 3 2 5 3 2 4 5 2 5

1 1 4 1 2 5 2 2 3 4 1 4 1 1 1 4 1 2 5 2 2 3 4 1 4

3 2 4 5 2 5 5 5 1 5 1 5 4 3 2 4 5 2 5 5 5 1 5 1 5

2 2 3 4 1 4 5 4 2 1 3 2 1 2 2 3 4 1 4 5 4 2 1 3 2

5 5 1 5 1 5 5 5 2 5 5 1 2 5 5 1 5 1 5 5 5 2 5 5 1

5 1 4 3 2 5 3 5 1 4 3 2 5 3 5 2 2 3 5 2 2 3 2 5 3

3 4 1 4 1 1 1 1 1 4 1 2 5 5 1 4 3 2 5 1 4 1 2 5 2

1 5 5 2 3 1 5 3 2 4 5 2 5 1 1 4 1 2 5 2 4 5 2 5 5

5 5 3 2 3 2 2 2 2 3 4 1 4 3 2 4 5 2 5 2 3 4 1 4 3

5 1 4 3 2 5 2 5 5 1 5 1 5 2 2 3 4 1 4 5 1 5 1 5 5

1 1 4 1 2 5 2 5 4 2 1 3 2 5 5 1 5 1 5 4 2 1 3 2 1

3 2 4 5 2 5 1 5 5 2 5 5 1 5 4 2 1 3 2 5 2 5 5 1 3

2 2 3 4 1 4 1 2 4 5 3 4 2 5 5 2 5 5 1 4 5 3 4 2 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 4 0 4 0 4 4 4 1 4 4 0 1 4 4 0 4 0 4 4 4 1 4 4 0

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

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

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

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

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

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

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

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

Затем, когда мы сделаем назначение, у нас будет 23 назначения вместо 25, так что мы сделаем упомянутые ранее покрывающие нули на основе описанных выше шагов, я получу следующее:

Жирные клетки - те, которые покрыты согласно вышеупомянутым шагам.

Обратите внимание, что все еще есть нули, вызывающие бесконечный цикл, так как он будет выбран следующим.

Пожалуйста, помогите мне.

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

Answer 1

Вы можете использовать минимальный алгоритм максимального потока для решения проблемы, когда каждый работник может выполнить две задачи.

Во-первых, давайте посмотрим, как решить стандартную задачу назначения, используя минимальный максимальный поток. Создайте двудольный граф, в котором рабочие находятся в одной части, а задачи - в другой. Поместите грань с емкостью 1 и стоимостью cost_ij между работником i и задачей j для всех i, j. Затем добавьте источник S и ребра из источника каждому работнику с емкостью 1 и стоимостью 0. Аналогично, добавьте приемник T и ребра из каждого задания в приемник с той же стоимостью и мощностью. Затем, если вы найдете минимальный максимальный поток от S до T, тогда его значением будет общая стоимость назначения.

Таким образом, если вы разрешаете каждому работнику выбирать две задачи, то ребра от источника к работникам должны иметь емкость 2. Это дополнение к алгоритму решит вашу проблему оптимальным способом, независимо от заданного ограничения на максимальную разницу.

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