Венгерский алгоритм
Задача о назначениях
Имеется
m заданий и столько же исполнителей. Каждый исполнитель способен выполнить каждое задание, но за каждое задание он возьмет с Вас определенную сумму денег. Вы торопитесь, поэтому хотите назначить каждому исполнителю по задаче (разные исполнители получают разные задачи), и заставить их всех работать одновременно. Ваша задача - сделать это так, чтобы минимизировать затраты.
Более формально это можно описать так: задана квадратная действительная матрица размера
m на
m. Набор элементов матрицы назовем
независимым, если никакие два элемента не находятся в одной и той же строке или в одном и том же столбце.
Максимальным независимым набором элементов назовем независимый набор, состоящий из наибольшего возможного числа элементов (в нашем случае
m).
Весом набора элементов назовем сумму значений этих элементов. Тогда задача о назначениях состоит в нахождении максимального независимого набора элементов с наименьшим весом.
Наконец иногда бывает полезно думать об этой задаче как о задаче на двудольном графе. Рассмотрим двудольный граф
Kmm, в котором обе доли содержат по
m вершин и между вершинами проведены все
m^2 допустимых ребер. Пусть также каждому ребру поставлен в соответствие некоторый вес (произвольное действительное число). Задача состоит в отыскании полного паросочетания наименьшего веса в этом графе.
Связь между формулировками на языке матриц и на языке графов вполне очевидна. Вершинам из первой доли графа соответствуют строки матрицы, вершинам из второй доли - столбцы. Ребрам графа соответствуют элементы матрицы, паросочетаниям - независимые наборы элементов, наконец наибольшим (в нашем случае полным) паросочетаниям отвечают максимальные независимые наборы элементов.
Двойственная задача
Двойственная задача формулируется следующим образом. Задана квадратная матрица
w размера
m на
m. Требуется найти такие числа
u[1],
u[2], ...,
u[m] и
v[1],
v[2], ...,
v[m], чтобы выполнялись следующие неравенства:
w[i][j] >=
u[i] + v[j]
и при этом чтобы сумма
s = u[1] + u[2] + ... + u[m] + v[1] + v[2] + ... + v[m] была максимальна.
Связь между прямой и двойственной задачами прояснится в ходе изложения алгоритма. Однако уже сейчас можно сделать вполне очевидное замечание: пусть в матрице
w имеется какой-то максимальный независимый набор элементов веса
z, а числа
u[i], v[i] удовлетворяют требуемому неравенству. Тогда их сумма
s не превосходит
z. Для доказательства этого факта рассмотрим произвольный элемент из максимального набора:
w[i][j] в позиции
(i, j). Для него, как и для всякого другого элемента, выполнено неравенство
w[i][j] >=
u[i] + v[j]
Складывая эти неравенства для всех элементов набора, как раз и получим, что
z >=
s. Из этого утверждения следует, что минимально возможное значение
z (то есть решение прямой задачи) не меньше максимально возможного значения
s (решения двойственной задачи). Как выяснится далее, на самом деле эти решения совпадают.
Идея алгоритма
Начиная с этого момента будем предполагать, что значения всех элементов матрицы
w[i][j] неотрицательны. Задача легко сводится к этому случаю, если ко всем элементам матрицы прибавить достаточно большое положительное число. Для матрицы
w с неотрицательными элементами справедливо следующее очевидное утверждение:
Искомый минимальный вес
z независимого набора равен нулю тогда и только тогда, когда в матрице существует полный независимый набор, состоящий из нулевых элементов.
Идея алгоритма состоит в том, чтобы при помощи некоторых операций модифицировать матрицу
w так. чтобы в ней появился такой независимый набор из нулей. При этом операции, производимые над матрицей, будут сводить задачу к эквивалентной, то есть модификации матрицы будут сохранять свойство минимальности веса для каждого полного независимого набора. Эти операции состоят в следующем:
- Модификация строки. Операция состоит в добавлении заданного числа
a ко всем элементам одной строки матрицы w.
- Модификация столбца (аналогично).
Пусть, к примеру, мы производим первую операцию. Какой бы полный независимый набор элементов матрицы
w мы ни взяли, ровно один элемент этого набора стоит в изменяемой строке, поэтому вес набора увеличится ровно на
a. Поскольку веса всех полных независимых наборов увеличатся на одно и то же число, то наборы минимального веса и только они станут наборами минимального веса в модифицированной матрице. Те же рассуждения применимы и ко второй операции.
Остается только показать, каким образом при помощи операций 1 и 2 можно произвольную матрицу привести к нужному виду (когда существует полный независимый набор из нулевых элементов).
Заметим, что на практике при выполнении операций 1 и 2 совсем не обязательно на самом деле модифицировать элементы матрицы
w. Разумнее завести два массива
u[i] и
v[i], изначально заполненные нулями, и в качестве модифицированной матрицы рассматривать матрицу
w'[i][j] = w[i][j] - u[i] - v[j] . Тогда операциям 1 и 2 соответствует вычитание числа
a из одного из элементов
u[i] или
v[i]. Кроме того, мы будем следить за тем, чтобы в модифицированной матрице (т.е.
w') все элементы оставались неотрицательны. Таким образом, массивы
u[i] и
v[i] будут удовлетворять неравенствам из условия двойственной задачи.
На первом этапе работы алгоритма мы просто вычтем из каждой строки значение минимального элемента этой строки. Затем проделаем то же самое и со столбцами. В результате получим матрицу
w', у которой в каждой строке и каждом столбце имеется хотя бы по одному нулевому элементу. Если уже после этого найдется полный независимый набор из нулевых элементов, то решение найдено. В противном случае нужно выполнять последовательные улучшения матрицы.
Улучшение матрицы
w' состоит в следующем. Рассмотрим только те элементы матрицы
w', значения которых равны нулю. Среди этих нулевых элементов можно выделить наибольший независимый набор. Для этого достаточно воспользоваться аналогией с формулировкой задачи при помощи двудольного графа. Нулевым элементам матрицы
w' соответствуют некоторые ребра нашего двудольного графа, и они индуцируют в нем некоторый двудольный подграф. Теперь для нахождения наибольшего независимого набора элементов достаточно в этом индуцированном графе найти
наибольшее паросочетание. Итак, мы нашли этот набор, и он состоит из
k <
m элементов матрицы. Дальше в том же индуцированном графе найдем
минимальное контролирующее множество V. Это множество отвечает некоторому множеству строк матрицы
R и множеству столбцов
C, причем суммарное количество строк в
R и столбцов в
C равно
k. Согласно определению контролирующего множества, все элементы матрицы
w, которые лежат на пересечении строк не из
R и столбцов не из
C, отличны от нуля, и следовательно строго положительны. Пусть
d - значение наименьшего из них. Теперь мы вычтем
d из всех строк
не из
R, и добавим его ко всем столбцам из
C. Заметим, что при этом сумма
s всех элементов массивов
u и
v увеличится на
d*(m-k), то есть строго возрастет.
В случае, если все числа целые, количество допустимых операций улучшения матрицы
w' конечно. Это значит, что после некоторого количества улучшений в матрице
w' найдется полный независимый набор из
m нулевых элементов, что и даст решение задачи. Заметим, однако, что в таком виде время работы алгоритма может зависеть не только от
m, но и от порядка чисел в матрице
w. Кроме того, не видно простого способа хотя бы даже доказать, что в случае нецелых
w[i][j] исполнение алгоритма вообще остановится.
Однако существует реализация Венгерского метода, использующая те же идеи (операции над строками и столбцами, последовательное улучшение матрицы с тем, чтобы в ней появился полный независимый набор нулевых элементов), работающая за время
O(m^3). В этой реализации операции улучшения матрицы более упорядочены. Идея состоит в том, чтобы на
i -том шаге алгоритма решить задачу для первых
i строк матрицы, то есть получить матрицу
w', у которой в перых
i строках содержится независимый набор из
i нулевых элементов, по одному в каждой строке. Тогда после
m шагов мы получим матрицу
w' с полным независимым набором нулевых клеток, что и требуется. Описание этого алгоритма и его реализацию на языке C++ можно найти
здесь.
Связанные темы
Реализации
--
DanielShved - 22 Mar 2008