Цены и узлы

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

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

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

к паросочетанию M, если:

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

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

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

Чем полезна такая система цен? На интуитивном уровне совместимые цены предполагают, что паросочетание имеет малую стоимость: по парным ребрам пре- мия равна стоимости а на всех остальных ребрах премия не превышает стоимость.

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

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

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

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

В нашем случае наличие цен позволяет вычислять кратчайшие пути для неот- рицательных сокращенных стоимостей cpe, получая эквивалентный ответ. Предпо- ложим, мы используем алгоритм Дейкстры для нахождения минимальной стои- мости dpM(v) направленного пути от 5 к каждому узлу v JU Y в соответствии со стоимостями c pe. С заданными минимальными стоимостями dp,M(y) для непарного узла у Y (несокращенная) стоимость пути от 5 к t через у составляет dм(y) + p(у), а минимальная стоимость находится за дополнительное время O(n). Подводя итог, приходим к следующему факту.

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Цены и узлы:

  1. ПРИМЕРНЫЕ ЦЕНЫ НА НЕКОТОРЫЕ ТОВАРЫ И УСЛУГИ В США, ОТ…(и, как правило, выше)
  2. Статья 710. Возмещение разницы в цене в случае замены товара, уменьшения цены и возвращение товара ненадлежащего качества
  3. Дуальные пары и двойные узлы
  4. Дуальные пары и двойные узлы
  5. Двойные узлы.
  6. ЛИМФАТИЧЕСКИЕ УЗЛЫ (ОПУХАНИЕ)
  7. Двойные узлы
  8. Двойные узлы
  9. Лунные узлы, или путеводитель по жизни
  10. Лунные узлы и Арабские части (точки)
  11. Глава 4 ЛУННЫЕ УЗЛЫ
  12. Солнце и Лунные узлы.
  13. Меркурий и Лунные узлы.
  14. Венера и Лунные узлы.
  15. Марс и Лунные узлы.