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

Алгоритм Куна

Дано

• n сотрудников
• n работ Стоимость выполнения j работы i-ым сотрудником: i, j=1,…n

Найти

Распределить работы среди сотрудников так, чтобы суммарная стоимость выполнения работ была минимальной, при этом один работник берется только за одну работу, и наоборот, одна работа назначается только одному работнику. То есть найти назначения

Модель

Представим исходные данные в виде матрицы работ n*n, у которой на пересечении i-ой строки и j-го столбца стоит стоимость выполнения j-ой работы i-ым сотрудником. Будем проводить манипуляции с этой матрицей.

Идея алгоритма

• если из всех элементов некой строки матрицы или столбца матрицы вычесть одно и то же число y, общая стоимость уменьшится на y, а оптимальное решение не изменится;
• если есть решение нулевой стоимости, то оно оптимально. Отсюда следует, что будем модифицировать матрицу работ по определенным правилам, пока не найдется решение нулевой стоимости. Когда назначение найдется, оно совпадет с искомым

Алгоритм

1. Редукция матрицы работ по строкам: для каждой строки матрицы:
   1. находим минимальный элемент в строке
   2. Из каждого элемента строки вычитаем минимальный элемент
2. Если назначение нулевой стоимости нашлось, оно оптимально
3. Редукция матрицы работ по столбцам: для каждой строки матрицы
   1. находим минимальный элемент в столбце
   2. Из каждого элемента столбца вычитаем минимальный элемент
4. Дописать

Алгоритм

1. Редукция матрицы работ по строкам: для каждой строки матрицы:
   1. находим минимальный элемент в столбце
   2. Из каждого элемента столбца вычитаем минимальный элемент