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

Хотя этот жадный метод базируется на вполне естественном принципе, оптималь- ность возвращаемого множества интервалов не столь очевидна. В самом деле, торопиться с вердиктом вообще не стоит: идеи, приведшие к описанным выше неоптимальным версиям жадного алгоритма, также на первый взгляд выглядели перспективно.

Для начала можно сразу утверждать, что интервалы множества A, возвращае- мого алгоритмом, совместимы.

(4.1) Множество A состоит из совместимых заявок.

Нужно продемонстрировать, что это решение оптимально. Итак, пусть О — оп- тимальное множество интервалов. В идеале хотелось бы показать, что A = O, но это уже слишком: оптимальных решений может быть несколько, и в лучшем случае A совпадает с одним из них. Итак, вместо этого мы просто покажем, что A| = |О|, то есть A содержит столько же интервалов, сколько и O, а следовательно, является оптимальным решением.

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

Для упрощения доказательства будут введены дополнительные обозначения. Пусть i1, ..., ik — множество заявок A в порядке их добавления в A. Заметьте, что | A | = k. Аналогичным образом множество заявок О будет обозначаться j1, ..., jm. Мы намерены доказать, что k = m. Допустим, заявки в O также упорядочены слева на- право по соответствующим интервалам, то есть по начальным и конечным точкам. Не забывайте, что заявки в О совместимы, то есть начальные точки следуют в том же порядке, что и конечные.

--------------------------------------------------------------------------------------- ►

Рис. 4.3. Шаг индукции в доказательстве того, что жадный алгоритм идет впереди


Выбор жадного метода происходит от желания освобождать ресурс как можно раньше после удовлетворения первой заявки. В самом деле, жадное правило гаран- тирует, что f (il) 1 r-я принятая заявка в расписании алгоритма завершается не позднее r-й заявки оптимального расписания.

(4.2) Для всех индексов r < k выполняется условие f (ir) 1.

Согласно гипотезе индукции, будем считать, что ут- верждение истинно для r - 1, и попробуем доказать его для r. Как видно из рис. 4.3, индукционная гипотеза позволяет считать, что f (ir1) < f (jr_1). Если r-й интервал алгоритма не завершается раньше, он должен «отставать». Но существует простая причина, по которой это невозможно: вместо того, чтобы выбирать интервал с бо- лее поздним завершением, жадный алгоритм всегда имеет возможность (в худшем случае) выбрать jr и таким образом реализовать шаг индукции.

В формальном представлении этот аргумент выглядит так. Мы знаем (так как O состоит из совместимых интервалов), что f(jr1) < s(jr). Объединяя это с ин- дукционной гипотезой f (ir1) < f (jr-1), получаем f (ir1) < s( jr). Следовательно, интервал jr принадлежит множеству R доступных интервалов на тот момент, когда жадный алгоритм выбирает ir. Жадный алгоритм выбирает доступный интервал с наименьшим конечным временем; так как jr является одним из таких доступных интервалов, имеем f (i ) < f (jr). На этом шаг индукции завершается. ■

Таким образом, мы формализовали смысл, в котором жадный алгоритм «идет впереди» O: для всех r выбираемый r-й интервал завершается по крайней мере не позже r-го интервала в O. А сейчас мы увидим, почему из этого следует оптималь- ность множества A жадного алгоритма.

(4.3) Жадный алгоритм возвращает оптимальное множество A.

Доказательство. Утверждение будет доказано от обратного. Если множество A не оптимально, то оптимальное множество O должно содержать больше заявок, то есть m > к. Применяя (4.2) для r = к, получаем, что f (ik) < f (jk). Так как m > к, в O должна существовать заявка jk+1. Она начинается после завершения заявки jk, а следовательно, после завершения iк. Получается, что после удаления всех заявок, несовместимых с заявками i1, ..., ik, множество возможных заявок R по-прежнему будет содержать jk+1. Но тогда жадный алгоритм останавливается на заявке ik, а дол- жен останавливаться только на пустом множестве R, — противоречие. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. Принципы анализа происшествия.
  13. АНАЛИЗ
  14. АНАЛИЗ КОРОТКИЙ