В данном алгоритме происходит последовательное преобразование матрицы весов (назначений) для получения приведенной матрицы, в которой в каждом ее столбце и строке есть хотя бы один нуль. Решение будем искать на нулевых элементах (независимых нулях). Еще раз поясним, что нулевые элементы матрицы C называются независимыми нулями, если для любого i, для которого выполняется условие 1<=i<=k, строка и столбец, на пересечении которых расположен элемент xi, не содержит другие нули xj для всех j k
Следующая последовательность шагов описывает алгоритм решения задачи о назначениях венгерским методом:
Шаг 1. Среди элементов каждой строки матрицы весов выбрать минимальный и вычесть его из элементов этой строки.Повторить эту же процедуры для столбцов.Перейти к шагу 2.
Шаг 2.Попытаться сконструировать решение при помощи нулевых элементов. Для этого необходимо осуществить следующие действия: рассмотрим сначала ту строку (или те строки), которая содержит наименьшее число нулей; обведем квадратиком один из нулей этой строки и затем вычеркнем нули, которые находятся в той же строке и в том же столбце, что и обведенный нуль; найдем среди оставшихся строк ту (или те), которая содержит меньше всего нулей, и повторим тот же процесс. Будем так поступать до тех пор, пока станет невозможным обводить квадратиками новые нули. Если нельзя получить решение с независимыми нулями, то перейти к шагу 4, в противном случае останов: решение найдено.Перейти к шагу 3.
а) пометить крестиком (x) все те строки, которые не содержат ни одного обведенного квадратиком нуля;
б) отметить каждый столбец, содержащий перечеркнутый нуль хотя бы в одной из помеченных строк;
в) отметим каждую строку, имеющую обведенный квадратиком нуль хотя бы в одном из помеченных столбцов;
г) будем повторять поочередно действия б) и в) до тех пор, пока не останется строк и столбцов, которые еще можно пометить.
В результате выполнения действий а) - г) будет получено минимальное число строк и столбцов, содержащих все перечеркнутые или обведенные нули таблицы.
Перейти к шагу 4.
Шаг 4.Перечеркнуть каждую непомеченную строку и каждый помеченный столбец, в результате чего получим минимальное число строк и столбцов, содержащих все перечеркнутые или обведенные нули таблицы.
Перейти к шагу 5.
Шаг 5.Рассмотрим часть таблицы, состоящую из неперечеркнутых элементов, и найдем минимальный элемент в ней. Вычесть это число из элементов неперечеркнутых столбцов и прибавить к элементам перечеркнутых строк. Результат данной процедуры записать в матрицу C2 и попробовать найти оптимальное решение на нулевых элементах. Если возможно получить оптимальное решение, то процесс заканчивается, иначе перейти к шагу 3.
Рассмотрим пример решения задачи о назначениях описанным методом с матрицей:
2 5 4 6 7 4
5 8 6 7 8 3
5 4 6 7 8 5
6 7 3 45 6 5
4 6 8 7 6 45
6 5 4 3 4 5
После вычитания минимального элемента из строк получится матрица:
0 3 2 4 5 2
2 5 3 4 5 0
1 0 2 3 4 1
3 4 0 42 3 2
0 2 4 3 2 41
3 2 1 0 1 2
После вычитания минимального элемента из столбцов получится приведенная матрица, которая будет иметь вид:
Расставляем пометки: крестиком пометим строку 5, пометим столбец 1, пометим строку 1. Пометки расставлялись в соответствии с пунктами а), б), в) шага 3.
Непомеченными будут столбцы 2, 3, 4, 5, 6. Зачеркиваем столбец 1. Также зачеркнем все непомеченные строки.
Рассмотрим часть таблицы, состоящую из неперечеркнутых элементов. Минимальный элемент в ней 1. Вычитаем его из всех неперечеркнутых элементов.
После приведения матрица принимает вид:
02 1 3 3 1
2 5 3 4 4 0
1 0 2 3 3 1
3 4 0 42 2 2
0 1 3 2 0 40
3 2 1 0 0 2
Снова обводим квадратиками (выделяем жирным шрифтом) нули. Мы получили 6 независимых нулей. Следовательно, останов. Подсчитываем суммарный вес назначения, суммируя значения из исходной матрицы, стоящие на позициях независимых нулей
Вес равен 2+4+3+3+6+3 = 21.
В паросочетание входят ребра: 1,1; 3,2; 4,3; 6,4; 5,5; 2,6
Таким образом, получен результат (матрица назначений)
k