Алгоритм Эдмондса

Алгоритм Эдмондса

Цель алгоритма Эдмондса — найти идеальное паросочетание (максимальной мощности) в задаче о назначениях.

Проблема сцепления заключается в следующем:

Построить график двудольный (элементы слева соединены дугами только с элементами справа, элементы справа не имеют исходящей связи) такой, что элементы слева — это машины, а элементы справа — задачи, подлежащие выполнению . Луки имеют мощность 1 и стоимость согласно таблице назначения. Если поток проходит через ребро (i,j), это означает, что машина i выполняет задачу j.
Чтобы завершить двудольный граф, чтобы сделать его потоковой задачей, каждый левый элемент связан как конечная вершина с фиктивным источником. Каждый линейный элемент привязан как исходная вершина к фиктивной скважине. Все эти дуги имеют пропускную способность 1 и стоимость 0. Для решения задачи о назначениях применим алгоритм из максимальный расход с минимальными затратами на построенный двудольный граф.
Алгоритм задачи о назначении идеальной связи Эдмонда
Делиться
ru_RURU
%d такие блоггеры, как: