2015-05-30
1967
Метод был предложен венгерским математиком Эгервари. Прежде чем перейти к рассмотрению венгерского метода, условимся элементы матрицы, образующие некоторое множество, называть независимыми, если никакие два элемента этого множества не лежат на одной и той же линии (строке, столбце). Так, например, элементы вида ajj (j=1,N) независимы. Задача фактически сводится к определению N независимых элементов матрицы {aij} так, чтобы сумма этих элементов была максимальной. В процессе решения задачи приходится выделять отдельные линии матрицы (строки или столбцы). Выделенные линии отмечаются знаком +. Элементы, находящиеся в выделенных строках или столбцах, называются выделенными, а остальные - невыделенными. Алгоритм состоит из подготовительного этапа и ряда последовательно выполняемых итераций.
Подготовительный этап. При решении задач на максимум в каждом столбце матрицы выбирается максимальный элемент, из которого вычитаются все элементы этого столбца. Затем в каждой строке матрицы выбирается минимальный элемент, который вычитается из всех элементов этой строки. В результате этого в каждой строке и каждом столбце матрицы будет не менее одного нуля. В первом столбце матрицы выбирается произвольный нуль и отмечается звездочкой (*). Затем рассматриваются нули второго столбца, и если среди них есть такие, которые находятся не в одной строке с нулем первого столбца, и уже отмеченные звездочкой, то один из них отмечается звездочкой. Аналогично рассматриваются нули всех других столбцов. Отмеченные звездочкой нули являются независимыми, так как в каждой строке и каждом столбце может быть не более одного нуля со звездочкой.
Итак, подготовительный этап заканчивается выделением звездочками независимых нулей.
Итерационный процесс. Целью итерации является увеличение числа независимых нулей. Когда число независимых нулей станет равным N, задача решена. Оптимальный выбор определяется местом независимых нулей. Перед началом итерации выделяются знаком + столбцы матрицы, содержащие нули со звездочкой. Итерация включает в себя три этапа, взаимосвязь между которыми представлена на рис. 3.4.
Этап 1. Над найденным невыделенным нулем ставится штрих('), соответствующая строка отмечается справа знаком(+), а знак выделения столбца, содержащего нуль со звездочкой, снимается 
.
Этап 2. Производится построение цепочки элементов. Цепочка начинается от нуля со штрихом и по столбцу проходит к нулю со звездочкой, затем к нулю со штрихом в той же строке и т.д. Начало и конец цепочки - нули со штрихом. После этого звездочки над нулями, входящие в цепочку, зачеркиваются, а над нулямисо штрихом ставятся звездочки. Зачеркиваются также все знаки выделения в матрице (кроме звездочек). На этом заканчивается построение цепочки. Так как концы цепочки - нули со штрихами, то в результате итерации число нулей со звездочкой увеличивается на 1.
Этап 3. Среди элементов, находящихся в невыделенных линиях, выбирается минимальный, который прибавляется к элементам выделенных столбцов и вычитается из элементов не выделенных строк. В результате этих операций появляются невыделенные нули.
Рис. 3.4
