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

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

Вспомните процедуру построения остаточного графа, использовавшегося для поиска увеличивающих путей. Имеется паросочетаниеM; в граф добавляются два новых узла 5 и t. Мы добавляем ребра (5, х) для всех непарных узлов х X и ребра (у, t) для всех непарных узлов у Y. Ребро e = (х, у) E ориентировано от х к у,

если e не входит в паросочетание M, и от у к х, если e M. Этот остаточный граф

будет обозначаться GM Обратите внимание: все ребра, проходящие из Y в X, входят в паросочетание M, тогда как ребра, проходящие из X в Y, в него не входят. Любой направленный путь s-t P в графе GM соответствует паросочетанию, размер которого на 1 больше, чем у M, полученному заменой ребер из P — то есть ребра P, проходя- щие из X в Y, добавляются в M, а все ребра в P, проходящие из Y в X, удаляются из M.

Как и прежде, путь P в GM будет называться увеличивающим путем; соответственно паросочетание Mувеличивается с использованием пути P.

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

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

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

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

Еще по теме Разработка и анализ алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  3. § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ
  6. АЛГОРИТМ УДАЧИ
  7. Алгоритм исцеления:
  8. Алгоритм избавления от боли
  9. 2. Специфика и алгоритмы работы с источниками.
  10. Алгоритм обработки результатов.
  11. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  12. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  13. 2.7. Разработка анкеты
  14. Разработка Плана
  15. 6. Разработка перспектив
  16. Разработка и принятие Основного закона
  17. Состояние научной разработки проблемы.
  18. Правило разработки веера версий