Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 49
Текст из файла (страница 49)
Н. А. Мангег. Вег1!п: Зрып8егдуег1а8, 1979. П Взвеыенное паросочетанне «л Введение Значительно более сложной представляезся задача о паросочетаиии, в которой задан граф 6=()л, Е) и каждому ребру (иь из1ЕЕ сопоставлено число ш„) О, называемое весом ребра Ьь и,]. Предлагается найти паросочетание в 6 с наибольшей возможной суммой весов. Очевидно, что задача о невзвешенном паросочетании, которую мы рассматривали в предыдущей главе (называемая иногда задачей о мощности паросочетания),— это частный случай задачи о взвешенном паросочетании: достаточно положить ш„=) для всех (ио и;)ЕЕ.
Нетрудно видеть, что в формулировке задачи о взвешенном паросочетании можно убрать граф 6, приняв соглашение, что этот граф всегда полный, и полагая веса тех ребер, которых нет в 6, равными нулю. Кроме того, всегда можно считать, что число вершин четно— в противном случае можно добавить новую вершину и положить веса всех ребер, инцидентных эгой вершине, равными нулю. Если рассматривается двудольный случай этой задачи, также можно считать, что граф представляет собой полный двудольный граф с двумя мно.
жествами вершин одинаковой мощности. Отме~им также, что оптимальные решения обязательно будут полными паросочетаниямн (так как шм ) 0), и, следовательно, можно формулировать эти задачи как задачи минимизации, рассматривая стоил~ости со=-%' — инь где Чг больше, чем все иль Всюду в этой главе будет рассмазриваться именно такой вариант задачи. Как и задача о мощности паросочетания, задача о взвешенном паросочетании значигельно проше в двудольном случае. Задача о взвешенном паросочетании в двудольном графе известна еше и как задача о назначениях, поскольку в принципе ее можно применять для вычисления наилучшего назначения работ рабочим в предположении, что известна величина гвы, производимая енм рабочим при выполнении )'-й работы.
Задачу о назначениях можно описать как упрощенную задачу линейного программирования, являющуюся частным случаем задачи Хичкока (см. й 7.4), и поэтому ее можно решать, применяя прямо-двойственный метод, называемый в этом частном случае венгерским метадолс Венгерский метод позволяет решать задачу о взвешенном паросочетании для полного двудольного графа с 27) вершинами за 0(~7(') арифметических операций.
2оей !Д2. Венеерений метод дяя задачи о назначениях 1!ри попьпках применить тот же подход в недвудольном случае оказывается, что задачу о взвешенном паросочетании не удается ~очно сформулировать как задачу линейного программирования. Здесь имеется в виду то, что соответствующая задача линейного программирования имеет базисные допустимые решения, не соответствующие паросочетаниям.
Не удивительно, что эта патология снова связана с наличием цветков. Поэтому мы должны обнаруживать такие цветки и, несмотря на нх наличие, находить увеличивающие пути. Однако в случае взвешенного паросочетания та часть нашей задачи, которая относится к теории графов, проще как теоретиче. ски, так и алгоритмически. Трудная часть состоит в таком усовершенствовании формулировки соответствующей задачи линейного программирования, чтобы она ~очно описывала нашу задачу, что позволит разработать подходящий прямо-двойственный алгоритм. Способ, который при этом используегся, являешься красивым применением теории двойственности.
Алгоритм нахождения взвешенного паросочетания для произвольных графов, который будет построен в 5 11,3, имеет сложность О(!У!е); в задаче 14 будут указаны усовершенствования, необходимые для понижения сложности до 0((У)е). 41.2 Веигерсинй метод дяя задачи о назначениях Г!риведем простую алгебраическую формулировку задачи о взвешенном паросочетании в двудольиом графе. Пусть кц — мно- жесчво переменных для 1=1,..., и и 1=1,..., и, где л — число вершин в множествах У и (з' в полном двудольном графе В=(У, (з', Е).
Здесь кц=! означает, что ребро !по и!) включается в паро- сочетание, в то время как хц= О означает обратное. Для того чтобы эти величины представляли полное паросочетание, необходи- мо выполнение следующих условий: н Х х; = 1, ! = 1, ..., и, / =! П (А) Х хм=1, 1=1, ..., л, е=! х, >О. Наша цель — минимизировать е. цсцхц. Таким образом, мы получили задачу линейного программирования (являющуюся частным случаем задачи Хичкока из гл. 7, в которой т=п и все а и Ь равны 1), которая в некотором смысле описывае~ задачу о назначениях.
К сожалению, невозможно записать с помощью линейных неравенств наше условие о том, что переменные хц должны принимать только значения О и !. Поэтому наша задача линейного программирования в принципе может иметь дробное оптимальное реше- Гм ! К В»оешенног пороеооемоное ние, не соответствующее никакому допустимому паросочетанию. Соответствующий пример приведен на рис. 11.1. К счастью, здесь так же, как в аналогичной ситуации, связанной с задачей о максимальном потоке (см. з 9.8), работает некая таинственная дружественная сила. Хотя такие о, З „, дробные решения, очевидно, существуют, они никогда не являются базисными допустимы- 4 ми решениями рассматриваемой задачи ли- 4 пейного программирования.
Поэтому если мы захотим решать эту задачу линейного 5 программирования, используя симплекс-алгоритм (любой его вариант), то можем быть уверены, что заключительное оптимальное Рис. ! 1.1. решение будет не дробным, т. е. будет соответствовать реальному паросочетанию. В гл. 13 будет разработана теория вполне унимодулярноети, которая позволит полностью понять это явление. Здесь же мы приведем конструктивное доказательство того, что всегда существует оптимальное решение задачи (А), соответствующее ореальному» полному паросочетанию. Наше конструктивное доказательство основано просто на применении прямо-двойственного метода к этой задаче линейного программирования путем комбинаториализации ее стоимости, так же как это делалось для более общей задачи Хичкока в гл.
7. Лемма 11.1. Приведенны1» на рис. 7.9 алгоритм АЛЬФАБЕТА в применении к задаче гп!и ~~~!у, е,,х, ори ограничениях (А) диет оптимальное решение задачи о назначениях. Доказательсгпво. Очевидно, алгоритм порождает оптимальное решение рассматриваемой задачи линейного программирования, Оспается установить, что все хм в полученном оптимальном решении целочисленны, т. е. имеют значения О или 1. Это, однако,следует из того факта, чзо оптимальное решение, отыскиваемое алгоритмом АЛЪФАБЕТА, является решением некоторой задачи о максимальном потоке с целочисленными (на самом деле О или 1) прону. скпыми способностями (вспомните рис. 7.8). Несколько модифицируем алгоритм АЛЬФАБЕТА для того, чащобы применить его к задаче о назначениях.
В результате он примет вид алгоритма поиска паросочетания, напоминающего алгоритм, разработанный в предыдущей главе. Кроме того, булез существенно понижена его асимптотическая сложность. Напомним, что этот алгоритм решает постоянно изменяющуюся ограниченную прямую (ОП) задачу, которая в нашем случае является задачей о максимальном потоке. При этом легко понять, что ОП оказывается задачей о невзвешенном паросочетании в двудольном графе, состоя1цем из допустимых на данном этапе ребер (т. е. тех ребер, для которых 1Д2. Венгерский метод дяя задачи о назначениях 257 сы — — аг+Рт длЯ двойственных пеРеменных а! и Р~, .вспомните 25.1), которую мы решим, применяя алгоритм, представленный на рис. 10.3.
Во время поиска увеличивающего пути мы можем столкнуться с отсутствием прорыва — это будет означать, что невозможно произвести увеличение в имеющемся множестве допустимых ребер. В этом случае изменим двойственные переменные и, и !)т так, чтобы появились новые допустимые ребра, и возобновим поиск увеличивающего пути. После нахождения увеличивающего пути используем его для увеличения паросочетания и начинаем все сначала.
Назовем вычисления между двумя последовательными увеличениями этапом. Тогда этап состоит из поиска увеличивающего пути в двудольном графе, составленном из допустимых ребер, чередующегося с модификациями двойственных переменных, изменяющими множество допустимых ребер (на рис. 11.2 это соответствует вызовам процедуры МОДИФИЦИРОВАТЬ), Для модификации двойственных переменных необходимо вычислить (вспомните равенства (7.13)) ! О, = 2 ш!и (сы — а; — р,), и где минимум берется по всем помеченным вершинам в,91 и непомеченным вершинам итсУ (имеется в виду полный двудольный граф с вершинами [г= (оь..., ои) и У= (и,,..., и„)). Вычисление заново этой величины каждый раз, когда модифицируются двойственные переменные, путем сравнения и' кандидатов могло бы быть очень дорогим.
Мы разрешим эту проблему ну~ем хранения и пересчета ') двух массивов невязка[и!! и сосед[и!! для 1=1,..., и, где невязка [и,! — это минимум (см — а,— ([т) по всем помеченным вершинам о, и сосед[и,! — выделенная помеченная вершина еь на которой достигается невязка[и,!. Таким образом, невязка[ау[=-0 означает, что [сосед!и
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
