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

Question

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

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

Этапы алгоритма можно найти на вики: Hungarian Algorithm

В шаге 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 

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

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

Answer 1

Ваш текущий подход делает не работу.

0 2 0 
3 0 0 
4 0 0 

Ваш метод: «Тогда начните назначать произвольные задачи работнику с наименьшим счетчиком» Все работники имеют тот же счетчик, так что вы выбираете сотрудника 1 и назначить его к задаче 3, вы можете соответствовать только один оставшихся рабочих, в то время как с этой матрицей вы, очевидно, могли бы соответствовать всем трем.

Что нужно: Максимальное двухстороннее соответствие между этими работниками и задачами, где пара подходит, если в соответствующем положении есть 0. Такое совпадение может быть найдено путем ручного перехода через пути увеличения или быстрее с помощью алгоритма Хопкрофта-Карпа.