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

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

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


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

(7.65) Пусть M — паросочетание, p — совместимые цены, а Mf — паросочетание, полученное посредством увеличения по пути минимальной стоимости от s до t.

Тогда p'(v) = dpM(v) + p(v) является совместимым множеством цен для Mf.

Доказательство. Чтобы доказать совместимость, сначала рассмотрим ребро е = (х',у) ^ М. Единственным ребром, входящим в х', будет направленное ребро (у, х% а следовательно, dpM(xf) = dp M (у) - cp , где cpe = p(y) + -p(x'), и мы полу-

чаем искомое уравнение на всех ребрах. Затем рассмотрим ребра (х, у) в Mf - М. Эти ребра расположены по пути минимальной стоимости от s до t, а следовательно, они удовлетворяют условию (у) = dy м(x) + , как и требовалось. Наконец, мы

получаем необходимое неравенство для всех остальных ребер с учетом того факта, что все ребра е = (х,у) ί Мдолжны удовлетворять условию ⅛⅜ОО ⅛ ⅜, it (-*) + гi\ ■

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

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

Инициализировать M пустым множеством

Определить p(x) = 0 для x е X, и p(y) = mine into ycв для у е y Пока M не является идеальным паросочетанием

Найти путь s-t P с минимальной стоимостью в GM, используя (7.64) с ценами p

Провести увеличение по P для получения нового паросочетания M'

Найти множество совместимых цен в отношении M' согласно (7.65)

Конец Пока

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

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

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

Еще по теме Обновление цен узлов:

  1. Обновление
  2. Обновление
  3. Глава 7 Чудо духовного обновления
  4. Решение двойных узлов
  5. Решение двойных узлов
  6. Еще раз об аспектах Лунных узлов
  7. Роль Лунных узлов в астрологии
  8. 3. Узловые соглашения между транспортными организациями
  9. Решение двойных узлов.
  10. Приложение к § 23 О ценности имуществ. – Понятие о цене. – Мерило ценности. – Категория цен. – Способы оценки. – Таксы на разные предметы и таксы вознаграждения за труд. – Меры и весы.
  11. Цензура и журналистика при «обновленном строе»
  12. ГЛАВА ПЯТАЯ Пришествие - обновление 2004
  13. Статья 290. Уничтожение, подделка или замена номеров узлов и агрегатов транспортного средства
  14. 1. Чудо обновления семьи свершится, когда истинная свобода приобщит взрослых и детей к матери-природе, к великим тайнам народной культуры, сбереженной в укромных и неприметных далях нашего отечества
  15. § 25 Прекращение обязательств посредством нового договора. – Обновление договора. – Признаки оного и последствия. – Прекращение договора по условию. – Мировая сделка. – Компромисс. – Русский закон мирового соглашения.
  16. ПАХ (БОЛЬ)
  17. Уран и Лунные узлы.