Венгерский алгоритм - назначайте систематически

Question

Я реализую венгерский алгоритм в проекте. Мне удалось заставить его работать до тех пор, пока это не называется шагом 4 в Wikipedia . Мне удается позволить компьютеру создавать достаточно нулей, чтобы минимальное количество покрывающих линий равнялось количеству строк / столбцов, но я застрял, когда дело доходит до назначения правильного агента для правильной работы. Я вижу, как я мог бы назначить себя, но это больше проб и ошибок - то есть я не вижу систематического метода, который, конечно, важен для компьютера, чтобы он работал.

Скажем, у нас есть эта матрица в конце:

   a  b  c  d
0  30 0  0  0
1  0  35 5  0
2  60 5  0  0
3  0  50 35 40

Нули, которые мы должны принять, чтобы каждый агент был назначен на работу, это (a, 3), (b, 0), (c, 2) и (d, 1). Какова система выбора этих? Мой код теперь выбирает (b, 0) в первую очередь, и теперь игнорирует строку 0 и столбец b. Однако затем он выбирает (a, 1), но с этим выбранным значением больше невозможно присвоение для строки 3.

Любые советы приветствуются.

Answer 1

Ну, мне удалось решить это в конце концов.Метод, который я использовал, состоял в том, чтобы проверить, есть ли какие-либо столбцы / строки только с одним нулем.В таком случае этот агент должен использовать это задание, и этот столбец и строка должны игнорироваться в будущем.Затем сделайте это снова, чтобы получить работу для каждого агента.

В моем примере (b, 0) будет первым выбором.После этого у нас есть:

   a  b  c  d
0  x  x  x  x
1  0  x  5  0
2  60 x  0  0
3  0  x  35 40

Снова используя метод, мы можем сделать (a, 3) и т. Д. Я не уверен, было ли доказано, что это всегда правильно, но кажетсяесть.