Добавление стоимостей в задачу паросочетаний - Нахождение потока в сети

Вернемся к первой задаче, упомянутой в этой главе, — двудольным паросочетаниям. Идеальные паросочетания в двудольном графе предоставили механизм моделирования парных отношений между разными объектами — заданий с машинами, например. Но во многих ситуациях в одном множестве объектов существует много возможных идеальных паросочетаний, и нам хотелось бы как-то выразить идею о том, что некоторые идеальные паросочетания могут быть “лучше” других.

Задача

Естественная формулировка задачи такого рода заключается во введении стоимостей. Например, выполнение некоторого задания на некоторой машине может требовать определенных затрат, или же нам хотелось бы связать задания с машинами так, чтобы свести к минимуму общую стоимость. Или представьте себе n пожарных машин, которые необходимо отправить в n разных домов; каждый дом находится на заданном расстоянии от пожарной части, и распределение должно минимизировать среднее расстояние перемещения каждой машины до точки назначения. Короче, алгоритм для поиска идеального паросочетания с минимальной общей стоимостью был бы чрезвычайно полезен.

Формально мы рассматриваем двудольный граф G = (V, E), множество узлов которого, как обычно, разбито на подмножества V = X U Y так, что один конец каждого ребра e ∈ E принадлежит X, а другой конец принадлежит Y. Кроме того, с каждым ребром e связана неотрицательная стоимость c_e. Для паросочетания M стоимостью паросочетания называется общая стоимость всех ребер, входящих в M, то есть Задача нахождения идеального паросочетания с минимальной стоимостью предполагает, что │X| = |Y| = n, и целью является поиск идеального паросочетания с минимальной стоимостью.

Разработка и анализ алгоритма

В этом разделе описан эффективный алгоритм для решения этой задачи, основанный на идее увеличивающих путей, но адаптированный с учетом стоимостей. Таким образом, алгоритм итеративно строит паросочетания с использованием i ребер, для каждого значения i от 1 до n. Мы покажем, что при завершении алгоритма с паросочетанием размера п получается идеальное паросочетание с минимальной стоимостью. Высокоуровневая структура алгоритма проста: если имеется паросочетание с минимальной стоимостью с размером i, то мы ищем увеличивающий путь для получения паросочетания с размером i+1; и вместо любого увеличивающего пути (достаточного при отсутствии ребер) используется увеличивающий путь с минимальной стоимостью, чтобы самое большое паросочетание тоже имело минимальную стоимость.

Вспомните процедуру построения остаточного графа, использовавшегося для поиска увеличивающих путей. Имеется паросочетание M; в граф добавляются два новых узла s и t. Мы добавляем ребра (s, х) для всех непарных узлов х ∈ X и ребра (у, t) для всех непарных узлов у ∈ Y. Ребро e = (х, y) ∈ E ориентировано от х к у, если e не входит в паросочетание M, и от у к х, если e ∈ M. Этот остаточный граф будет обозначаться G_M. Обратите внимание: все ребра, проходящие из Y в X, входят в паросочетание M, тогда как ребра, проходящие из X в Y, в него не входят. Любой направленный путь s-t P в графе G_M соответствует паросочетанию, размер которого на 1 больше, чем у M, полученному заменой ребер из P — то есть ребра P, проходящие из X в Y, добавляются в M, а все ребра в P, проходящие из Y в X, удаляются из M. Как и прежде, путь P в G_M будет называться увеличивающим путем; соответственно паросочетание M увеличивается с использованием пути P.

Полученное паросочетание должно иметь как можно меньшую стоимость. Для этого мы будем искать увеличивающий путь, стоимость которого мала относительно следующих естественных стоимостей: ребра, выходящие из s и входящие в t, имеют стоимость 0; ребро, ориентированное от X к Y, имеет стоимость с_е (так как включение этого ребра в путь означает добавление ребра в M); и ребро e, ориентированное от Y к X, имеет стоимость -c_e (так как включение этого ребра в путь означает удаление ребра из M). Стоимость пути P в G_M будет обозначаться cost(P). Следующее утверждение кратко резюмирует суть построения.

(7.61) Пусть M — паросочетание, а P — путь в G_M от s к t; паросочетание M' получено из M улучшением относительно P. Тогда │M'│ = │M│ + 1, а cost(M') = cost(M) + cost(P).

Приведенное утверждение подсказывает естественный алгоритм для нахождения идеального паросочетания с минимальной стоимостью: нужно проводить итеративный поиск путей с минимальной стоимостью в G_M и использовать пути для улучшения паросочетаний. Но как убедиться в том, что найденное идеальное паросочетание имеет минимальную стоимость? Или того хуже — что этот алгоритм вообще имеет смысл? Нахождение минимальных путей возможно только в том случае, если граф G_M гарантированно не содержит отрицательных циклов.

Анализ отрицательных циклов

В действительности понимание роли отрицательных циклов в G_M играет ключевую роль при анализе алгоритма. Сначала рассмотрим случай, в котором M является идеальным паросочетанием. Обратите внимание: в этом случае узел s не имеет выходящих ребер, а t не имеет входящих ребер в G_M (поскольку паросочетание является идеальным), а следовательно, никакой цикл в G_M не может содержать s или t.

(7.62) Имеется идеальное паросочетание M. Если в G_M существует направленный цикл C с отрицательной стоимостью, то стоимость M не минимальна.

Доказательство. Воспользуемся циклом C для увеличения — подобно тому, как направленные пути использовались для получения паросочетаний с большим размером. Увеличение Mотносительно C подразумевает добавление (и удаление) ребер из C в M. Полученное новое идеальное паросочетание M' имеет стоимость cost(M') = cost(M) + cost(C); однако cost(C) < 0, а следовательно, стоимость M не минимальна. ■

Что еще важнее, обратное утверждение также истинно; таким образом, идеальное паросочетание M имеет минимальную стоимость тогда и только тогда, когда в G_M нет отрицательных циклов.

(7.63) Пусть M — идеальное паросочетание. Если в G_M нет направленных циклов с отрицательной стоимости C, то M является идеальным паросочетанием с минимальной стоимостью.

Доказательство. Предположим, утверждение ложно, и существует идеальное паросочетание M' с меньшей стоимостью. Рассмотрим множество ребер, входящих в одно из паросочетаний M и M' (но не в оба сразу). Заметим, что такое множество ребер соответствует множеству направленных циклов в G_M, непересекающихся по узлам. Стоимость множества направленных циклов равна в точности cost(M') - cost(M). Если M' имеет меньшую стоимость, чем M, значит, по крайней мере один из таких циклов имеет отрицательную стоимость. ■

Итак, план заключается в переборе паросочетаний увеличивающегося размера, при котором граф G_M не содержит отрицательных циклов ни на одной итерации. В этом случае вычисление пути с минимальной стоимостью всегда будет однозначно определено; а при завершении с получением идеального паросочетания из (7.63) будет следовать, что паросочетание имеет минимальную стоимость.

Цены и узлы

Будет полезно представить, что с каждым узлом v связана числовая цена p(v). Цены помогут не только лучше понять логику работы алгоритма, но и ускорить его реализацию. В частности, нам нужно следить за тем, чтобы граф G_M не содержат отрицательных циклов ни при какой итерации. Как узнать, что после увеличения в новом остаточном графе по-прежнему нет отрицательных циклов? Оказывается, компактное доказательство этого факта можно получить при помощи цен.

Чтобы понять, как работают цены в данном случае, полезно представить их экономическую интерпретацию. Рассмотрим следующий сценарий: допустим, множество X представляет людей, которые назначаются на работы из множества Y. Для ребра e = (x,y) стоимость c_e представляет затраты на выполнение человеком x работы у. Цену p(x) можно сравнить с премией, которая выплачивается человеку x за участие в этой системе — своего рода “поощрительная премия”. С учетом этого обстоятельства затраты на назначение человека x на работу у возрастают до p(x) + c_e. С другой стороны, цена p(y) для узлов у ∈ Y может рассматриваться как выгода от выполнения работы у (кто бы из работников X ее ни выполнял). В этом случае “чистые затраты” на назначение человека x на работу у принимают вид p(x) + c_e - p(y): стоимость найма работника x с премией p(x), выполнение им работы у с затратами с_e, с получением выгоды p(y). Назовем эту величину сокращенной стоимостью ребра e = (x, у), и обозначим ее c^p_e = p(x) + с_е - p(y). Однако важно помнить, что в описание задачи входят только стоимости c_e; цены (премии и выгоды) всего лишь помогают анализировать решение.

Набор чисел {p(v) : v ∈ V} образует множество совместимых цен по отношению к паросочетанию M, если:

(i) для всех непарных узлов x ∈ X p(x) = 0 (если человеку не предложена работа, то и платить ему не нужно);

(ii) для всех ребер e = (x, у) p(x) + c_e ≥ p(y) (каждое ребро имеет неотрицательную сокращенную стоимость); и

(iii) для всех ребер e = (x, у) ∈ M p(x) + c_e = p(y) (каждое ребро, используемое при назначении, имеет сокращенную стоимость 0).

Чем полезна такая система цен? На интуитивном уровне совместимые цены предполагают, что паросочетание имеет малую стоимость: по парным ребрам премия равна стоимости а на всех остальных ребрах премия не превышает стоимость. Для частичного паросочетания из этого может не следовать, что паросочетание имеет минимальную возможную стоимость для своего размера (в нем могут быть задействованы дорогостоящие работы). Однако мы утверждаем, что если M является произвольным паросочетанием, для которого существует множество совместимых цен, то G_M не содержит отрицательных циклов. Для идеального паросочетания M из этого будет следовать, что M имеет минимальную стоимость согласно (7.63).

Чтобы понять, почему G_M не может содержать отрицательные циклы, мы расширим определение сокращенной стоимости на ребра остаточного графа с использованием того же выражения c^p_e = p(x) + c_e - p(у) для любого ребра e = (v, w). Заметим, что из определения совместимых цен следует, что все ребра в остаточном графе G_M имеют неотрицательные сокращенные стоимости. Далее для любого цикла C

так как все слагаемые в правой части, соответствущие ценам, компенсируются. Известно, что каждое слагаемое в правой части неотрицательно, поэтому очевидно, что значение cost(C) также неотрицательно.

Существует и другая, алгоритмическая причина для назначения цен узлам. Если в графе имеются ребра с отрицательной стоимостью, но нет отрицательных циклов, кратчайшие пути вычисляются по алгоритму Беллмана-Форда за время O(mn). Но если в графе нет ребер с отрицательной стоимостью, вместо него можно воспользоваться алгоритмом Дейкстры со временем только O(m log n) — ускорение почти в n раз.

В нашем случае наличие цен позволяет вычислять кратчайшие пути для неотрицательных сокращенных стоимостей c^p_e, получая эквивалентный ответ. Предположим, мы используем алгоритм Дейкстры для нахождения минимальной стоимости d_p,M(v) направленного пути от s к каждому узлу v ∈ X U Y в соответствии со стоимостями c^p_e. С заданными минимальными стоимостями d_p,_M(y) для непарного узла y ∈ Y (несокращенная) стоимость пути от s к t через у составляет d_p,_M(y) + p(y), а минимальная стоимость находится за дополнительное время O(n). Подводя итог, приходим к следующему факту.

(7.64) Пусть M — паросочетание, а p — совместимые цены. Путь от s к t с минимальной стоимостью может быть найден за один проход алгоритма Дейкстры и дополнительное время O(n).

Обновление цен узлов

Мы воспользовались ценами для улучшения одной итерации алгоритма. Чтобы подготовиться к следующей итерации, необходимо знать не только путь с минимальной стоимостью (для получения следующего паросочетания), но и способ получения совместимых цен в отношении нового паросочетания.

Рис. 7.22. Паросочетание M (темные ребра) и остаточный граф, используемый для увеличения размера паросочетания

Чтобы примерно представить, как это делается, рассмотрим непарный узел х в отношении паросочетания M и ребро e = (x, y), показанное на рис. 7.22. Если новое паросочетание M' включает ребро e (то есть если e входит в увеличивающий путь, используемый для обновления паросочетания), то мы бы хотели, чтобы сокращенная стоимость этого ребра была равна 0. Однако цены p, использованные в паросочетании M, могут привести к сокращенной стоимости c^p_e > 0 — то есть назначение человека х на работу у в нашей экономической интерпретации не окупится. Нулевую сокращенную стоимость можно обеспечить либо повышением цены p(y) (выгодыу) на c^p_e, либо уменьшением цены p(x) на ту же величину. Чтобы цены оставались неотрицательными, мы увеличим p(y). Однако узел y может быть сопоставлен в паросочетании M с другим узлом x' по ребру e' = (x', у), как показано на рис. 7.22. Увеличение выгоды p(y) уменьшает сокращенную стоимость ребра e' до отрицательной, а следовательно, цены перестают быть совместимыми. Чтобы сохранить совместимость, можно увеличить p(x') на ту же величину. Впрочем, такое изменение может создать проблемы с другими ребрами. Можно ли обновить все цены, сохранив совместимость паросочетания и цен по всем ребрам? Оказывается, эта задача легко решается использованием расстояний от s до всех остальных узлов, вычисленных алгоритмом Дейкстры.

(7.65) Пусть M — паросочетание, p — совместимые цены, а M' — паросочетание, полученное посредством увеличения по пути минимальной стоимости от s до t. Тогда p'(v) = d_p,M(v) + p(v) является совместимым множеством цен для M'.

Доказательство. Чтобы доказать совместимость, сначала рассмотрим ребро е = (х', у) ∈ М. Единственным ребром, входящим в х', будет направленное ребро (у, х'), а следовательно, d_p,M(x') = d_p,M(у) - с^р_e, где с^р_е = р(у) + c_e - р(х'), и мы получаем искомое уравнение на всех ребрах. Затем рассмотрим ребра (х, у) в М' - М. Эти ребра расположены по пути минимальной стоимости от sдо t, а следовательно, они удовлетворяют условию d_p,M(y) = d_p,M(x) + с^р_e, как и требовалось. Наконец, мы получаем необходимое неравенство для всех остальных ребер с учетом того факта, что все ребра е = (х, у) ∉ М должны удовлетворять условию d_p,M(y) ≤ d_p,M(x) + с^р_e. ■

Наконец, необходимо решить, как инициализировать алгоритм, чтобы начать его выполнение. Мы инициализируем M пустым множеством, определяем p(x) = 0 для всех x ∈ X и определяем p(y) для у ∈ Y как минимальную стоимость ребра, входящего в у. Обратите внимание: эти цены совместимы в отношении M = φ.

Ниже приведено краткое описание алгоритма.

Итоговое множество совместимых цен доказывает, что G_M не имеет отрицательных циклов; и с учетом (7.63) из этого следует, что M имеет минимальную стоимость.

(7.66) Идеальное паросочетание минимальной стоимости может быть найдено за время, необходимое для n вычислений кратчайшего пути с неотрицательной длиной ребер.

Расширения: экономическая интерпретация цен

В завершение нашего обсуждения идеального паросочетания минимальной стоимости мы немного разовьем экономическую интерпретацию цен. Рассмотрим следующий сценарий: допустим, X — множество из n людей, каждый из которых желает купить дом, а Y — множество из n домов. Пусть v(x, у) обозначает ценность дома у для покупателя x. Так как каждый покупатель хочет купить один из домов, можно предположить, что лучшим вариантом будет идеальное паросочетание M, максимизирующее Такое идеальное паросочетание может быть найдено применением алгоритма идеального паросочетания минимальной стоимости со стоимостями c_e = -v(x, у), если e = (x, у).

А теперь зададимся следующим вопросом: можно ли убедить этих покупателей купить назначенный ему дом? Сам по себе каждый покупатель x хочет купить дом у, обладающий для него максимальным значением v(x, у). Как убедить его вместо этого купить дом, выделенный нашим паросочетанием M? Мы будем использовать цены для стимуляции покупателей. Допустим, мы назначаем цену Р(у) для каждого дома у — то есть человек, покупающий дом у, должен заплатить Р(у). С учетом этих цен покупатель будет заинтересован в покупке дома с максимальной чистой стоимостью — то есть дом у, максимизирующий v(x, у) - Р(у). Мы говорим, что идеальное паросочетание M и цены на дома Р уравновешены, если для всех ребер (x, у) ∈ M и всех других домов у' выполняется

v(x, у) - Р(у) ≥ v(x, у') - Р(у’).

Но можно ли найти идеальное паросочетание и множество цен, достигающих такого состояния дел, при котором все покупатели остаются довольными? Оказывается, идеальное паросочетание с минимальной стоимостью и связанное с ним множество совместимых цен дает искомое.

(7.67) Пусть M — идеальное паросочетание минимальной стоимости, где c_e = -v(x, у) для каждого ребра e = (x, у), а p — совместимое множество цен. Тогда паросочетание M и множество цен {Р(у) = -р(у) : у ∈ Y} уравновешены.

Доказательство. Рассмотрим ребро e = (x, у) ∈ M; пусть e' = (x,у'). Так как M и р совместимы, имеем p(x) + ce = р(у) и p(x) + ce' ≥ р(у'). Вычитая эти два неравенства для исключения p(x) и подставляя значения р и c, мы получаем нужное неравенство в определении уравновешенности. ■