<<
>>

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

Сначала мы рассмотрим очень простой алгоритм для пропускной способности c = 1, то есть когда пути не должны пересекаться по ребрам. По сути, это жадный алгоритм, не считая того, что он предпочитает короткие пути.
Мы покажем, что этот простой алгоритм является О(Jtit) -аппроксимирующим алгоритмом, где m = |Ё — количество ребер в G. Может показаться, что это довольно большой коэффициент аппрокси- мации; это действительно так, однако есть довольно веская причина, по которой это фактически лучшее, на что можно рассчитывать. Задача о максимальных непересека- ющихся путях не только является МР-полной, но и плохо аппроксимируется: доказано (если только не окажется, что Р = NР), что алгоритм с полиномиальным временем не способен достичь границы апрроксимации, существенно лучшей О( 4яt ) для произ- вольных направленных графов.

После разработки жадного алгоритма будет рассмотрен чуть более сложный алгоритм назначения цены для версии с пропускными способностями. Интересно, что алгоритм назначения цены работает намного эффективнее простого жадного алгоритма, даже если пропускная способность c ненамного выше 1.

Greedy-Disjoint-Paths:

Присвоить I = 0

Пока удается найти новые пути

Пусть Pi - кратчайший путь, не пересекающийся по ребрам с ранее выбранными путями и соединяющий пару (s ,t ), которая еще не была соединена

Добавить i в I и выбрать путь Р для соединения s с t.

Конец Пока

Длинный путь ИЗ Si в t\ заблокирует все остальные пути

V_______________________ J

Рис. 11.9. В этом случае критично, чтобы жадный алгоритм выбора непересекающихся путей отдавал предпочтение коротким путям перед длинными

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. Алгоритм обработки результатов.