Транспортная задача (Венгерский алгоритм)
Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари).
Джеймс Манкрес в 1957 году заметил, что алгоритм является (строго) полиномиальным. С этого времени алгоритм известен также как алгоритм Куна — Манкреса или алгоритм Манкреса решения задачи о назначениях. Временная сложность оригинального алгоритма была O(n4), однако Эдмондс и Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения O (n3). Форд и Фалкерсон распространили метод на общие транспортные задачи. В 2006 году было обнаружено, что Якоби нашёл решение задачи о назначениях в XIX веке и опубликовал его в 1890 году на латыни.
Постановка задачи
Дана неотрицательная матрица размера n×n, где элемент в i-й строке и j-ом столбце соответствует стоимости выполнения j-ого вида работ i-м работником. Нужно найти такое соответствие работ работникам, чтобы расходы на оплату труда были наименьшими. Если цель состоит в нахождении назначения с наибольшей стоимостью, то решение сводится к решению только что сформулированной задачи путём замены каждой стоимости C на разность между максимальной стоимостью и C.
Основные идеи
Алгоритм основан на двух идеях:
- если из всех элементов некоей строки или столбца вычесть одно и то же число y, общая стоимость уменьшится на y, а оптимальное решение не изменится;
- если есть решение нулевой стоимости, оно оптимально.
Алгоритм ищет значения, которые надо вычесть из всех элементов каждой строки и каждого столбца (разные для разных строк и столбцов), такие что все элементы матрицы останутся неотрицательными, но появится нулевое решение.
Подробнее здесь: http://ru.wikipedia.org/wiki/%C2%E5%ED%E3%E5%F0%F1%EA%E8%E9_%E0%EB%E3%EE%F0%E8%F2%EC
Оставить комментарий