Обновление цен узлов
Рис. 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 вычислений кратчайшего пути с неотрицательной длиной ребер.
Еще по теме Обновление цен узлов:
- Обновление
- Обновление
- Глава 7 Чудо духовного обновления
- Решение двойных узлов
- Решение двойных узлов
- Еще раз об аспектах Лунных узлов
- Роль Лунных узлов в астрологии
- 3. Узловые соглашения между транспортными организациями
- Решение двойных узлов.
- Приложение к § 23 О ценности имуществ. – Понятие о цене. – Мерило ценности. – Категория цен. – Способы оценки. – Таксы на разные предметы и таксы вознаграждения за труд. – Меры и весы.
- Цензура и журналистика при «обновленном строе»
- ГЛАВА ПЯТАЯ Пришествие - обновление 2004
- Статья 290. Уничтожение, подделка или замена номеров узлов и агрегатов транспортного средства
- 1. Чудо обновления семьи свершится, когда истинная свобода приобщит взрослых и детей к матери-природе, к великим тайнам народной культуры, сбереженной в укромных и неприметных далях нашего отечества
- § 25 Прекращение обязательств посредством нового договора. – Обновление договора. – Признаки оного и последствия. – Прекращение договора по условию. – Мировая сделка. – Компромисс. – Русский закон мирового соглашения.
- ПАХ (БОЛЬ)
- Уран и Лунные узлы.