Анализ алгоритма

Начнем с рассмотрения множества проектов A, удовлетворяющего ограничениям очередности. Пусть A' = A U {5} и B' = (P - A) U {t}; рассмотрим разрез 5-t (A', B'). Если множество A удовлетворяет ограничениям очередности, то ни одно ребро (i, j) ^ E не пересекает этот разрез (рис.
7.20). Пропускная способность разреза выражается следующим образом:

(7.56) Пропускная способность разреза (A', B'), определяемая для множества проектов A с учетом ограничений очередности, равна


Доказательство. Ребра G' можно разделить на три категории: соответствующие множеству ребер E графа G, выходящие из источника 5 и входящие в сток t. Так как A удовлетворяет ограничениям очередности, ребра Eне пересекают разрез (A', B'), а следовательно, не влияют на его пропускную способность. Ребра, входящие в сток t, вносят в пропускную способность разреза вклад

Рис. 7.20. Потоковый граф, используемый для решения задачи выбора проектов. Справа изображен возможный разрез с минимальной пропускной способностью



Вклад ребер, выходящих из источника s, равен

По определению С последнюю величину можно переписать в виде С-Т.,_ 1ιϊ1(ι.(,Рн ∙ Пропускная способность разреза (А\ В') равна сумме этих двух


слагаемых, то есть

как и утверждалось в постановке задачи.

Вспомните, что пропускная способность ребер G превышает

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

(7.57) Если (А\ В') — разрез с пропускной способностью, не превышающей С, то множество А = A' — |⅛J удовлетворяет ограничениям очередности.


Теперь мы можем доказать главную цель всего построения — что минималь- ный разрез в G' определяет оптимальное множество проектов. Объединяя эти два утверждения, мы видим, что разрезы (A', B'), пропускная способность которых не превышает C, однозначно соответствуют действительным множествам проектов A = A'- {s}. Пропускная способность такого разреза (A', B') составляет

Величина пропускной способности C является константой, не зависящей от разреза (A', B'), поэтому разрез с минимальной пропускной способностью соот- ветствует множествам проектов A с максимальной выгодой profit. Следовательно, нам удалось доказать следующее утверждение.

(7.58) Если (A', B') представляет собой минимальный разрез в G', то множество A = A' - {s} является оптимальным решением задачи выбора проектов.

7.12.

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

Еще по теме Анализ алгоритма:

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