Алгоритм розв’язування задачі про призначення Угорським методом

Якщо після першого етапу виділено менше ніж n нулів, виконується другий етап, який являє собою ітераційну процедуру збільшення кількості виділення нулів. Для поданої приведеної матриці збільшити кількість виділених нулів можна за рахунох вибору іншої сукупності виділених нулів. У основі методу пошуку такої сукупності покладено ідею побудови почергових ланцюжків, яку можна пояснити на прикладі. Припустимо у вихідній приведеній матриці виділено перший нуль таким чином

Збільшення кількості виділених нулів

0^* 0

0 1

Тоді неможливо додати до виділеного нуля жоден нуль. В той же час, якщо врахувати, що у першому рядку є ще один нуль-претендет на виділення, і у першому стовпчику також є такий нуль, то можна побудувати почерговий ланцюжок “від невиділеного нуля за стовпчиком до виділеного, і далі від виділеного нуля за рядком до невиділеного”. Будемо надалі позначати невиділені нулі-претенденти як 0^’.

0^* 0^’

0^’ 1

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

0 0^*

0^* 1

Зрозуміло, що кількість нулів у почерговому ланцюжку може бути і більшою. Головне, щоб ланцюжок починався і закінчувався нулем із штрихом.

У тому разі, коли у приведеній матриці не існує жодного почергового ланцюжка, а кількість виділених нулів менше n, переходять до еквівалентної матриці з більшою кількістю нулів-претендентів. При цьому так перетворюється матриця, щоб виділені нулі зберігли своє значення.

Перед описом алгоритму наведемо декілька означень. Будемо використовувати термін зайнятий для деяких стовпців, що містять 0^*. Інші стовпці будемо вважати вільними. Рядки, що містять 0^’, будемо завжди вважати зайнятими, а рядки, що не містять 0^’, - вільними. Елемент, не маючий ніяких позначень і розташований на перетинанні вільного рядка та вільного стовпця, будемо називати вільним.

1. Починаючи з першого рядка, послідовно у кожному рядку (якщо це можливо) виділити один нуль (0^*), що не стоїть у стовпчику з вже виділеним нулем. Помітити усі стовпці з 0^* як зайняті.

2. Якщо кількість 0^* дорівнює n, кінець алгоритму.

3. Якщо матриця не містить вільних нулів, перейти до кроку 7.

4. Проглядаючи послідовно рядки зліва направо, вибрати перший вільний нуль, помітити його як 0^’ і помітити рядок з цим нулем як зайнятий. Якщо у рядку з цим нулем міститься 0^*, зняти мітку зайнятості зі стовпця, утримуючого поданий 0^*, і перейти до кроку 3.

5. Починаючи з останнього отриманого 0^’, побудувати почерговий ланцюжок з нулів: від цього 0^’ за стовпцем до 0^*, від нього за рядком до 0^’, і так далі, доки це можливо. Ланцюжок завжди закінчується деяким 0^’.

6. У побудованому ланцюжку зняти зірочки у нулів і потім штрихи у нулів замінити на зірочки. Зняти усі мітки, крім зірочок; усі стовпці з 0^* помітити як зайняті, і перейти до кроку 2.

7. Відняти мінімальний вільний елемент від усіх незайнятих рядків і потім додати його до усіх зайнятих стовпців. Перейти до кроку 4.

Дата добавления: 2014-01-13