<<
>>

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

В ходе анализа мы сосредоточимся на простейшем случае, в котором одно ребро может использоваться не более чем двумя путями, то есть c = 2. Будет показано, что в этом случае значение β = да1/3 обеспечивает лучший результат аппроксимации для алгоритма.
В отличие от случая с непересекающимися путями (при c = 1) не- известно, будут ли границы аппроксимации, полученные здесь для c > 1, близки к лучшим возможным для алгоритмов с полиномиальным временем вообще (при условии, что P ф NP).

Анализ случая без пересечения базировался на возможности различать «корот- кие» и «длинные» пути. Для случая c = 2 путь P., выбранный алгоритмом, будет считаться коротким, если его длина менее β2. Пусть Is — множество коротких путей, выбранных алгоритмом.

Затем мы хотим сравнить количество выбранных и максимально возможных путей. Пусть I * — оптимальное решение, а P* — множество путей, использованных в решении. Как и прежде, ключевая идея анализа — рассмотрение ребер, блокирую- щих выбор путей в I *.

Длинные пути могут заблокировать многие другие пути, по- этому пока мы сосредоточимся на коротких путях в I. Однако пытаясь действовать по той же схеме, что и в непересекающемся случае, мы немедленно сталкиваемся с трудностями. В том случае длина пути в I * определялась количеством содержа- щихся в нем ребер, а на этот раз длины изменяются в ходе выполнения алгоритма, и теперь неясно, как определить длину пути в I* в целях анализа. Другими словами, когда измерять эту длину в контексте проводимого анализа? (В начале выполне- ния? В конце?)

Как выясняется, критическим моментом алгоритма для проводимого анализа является первая точка, в которой не остается ни одного короткого пути для выбо- ра. Пусть Т — функция длины для текущей точки в выполнении алгоритма; мы

используем I для измерения длины путей в Г.

Длина пути Р, ^ , будет обо-

значаться ∕ (Р). Путь Р*. в оптимальном решении Г будет считаться коротким, если

т Ю < β2, и длинным в противном случае. Пусть f обозначает множество корот- ких путей в I*. Прежде всего нужно показать, что не существует коротких путей, соединяющих пары, которые не были соединены аппроксимирующим алгоритмом.

(11.17) Возьмем пару «источник-сток» i ^ Г, не соединенную аппроксимиру- ющим алгоритмом; то есть i ФI. Для нее выполняется ∕ (Р *) > β2.

Доказательство. Пока выбираются короткие пути, нам не придется специаль- но следить за тем, чтобы каждое ребро использовалось не более чем в c = 2 путям; любое ребро e, рассматриваемое для включения в третий путь, уже имеет длину ie = β2, а следовательно, является длинным.

Рассмотрим состояние алгоритма при длине ∕ . Как следует из предыдущего абзаца, можно считать, что алгоритм отработал до этой точки, не беспокоясь об ограничении с; он просто выбирал короткий путь тогда, когда мог его найти. Так как точки sf t из P* не соединяются жадным алгоритмом и так как при достижении

функцией длины I коротких путей не остается, из этого следует, что путь Р* имеет длину по крайней мере β2 согласно ∕ . ■

При анализе случая без пересечений тот факт, что количество ребер не превы- шает т, использовался для ограничения количества длинных путей. На этот раз в качестве величины, потребляемой путями, будет использоваться длина I вместо количества ребер. Следовательно, для дальнейших рассуждений нам понадобится граница общей длины в графе ∙ Сумма длин по всем ребрам / начинается

с m (длина 1 для каждого ребра). Добавление короткого пути в решение Is может увеличить длину не более чем на β3, так как длина выбранного пути не превышает β2, а длины ребер увеличиваются с множителем β вдоль пути. Это дает нам полез- ное сравнение между количеством выбранных коротких путей и общей длиной.

(11.18) Множество ∕ коротких путей, выбранных аппроксимирующим алго- ритмом, и длины ∕ находятся в отношении УУ/e < β3 \ls\ + т .

Итак, граница аппроксимации для этого алгоритма доказана. Оказывается, даже при простом увеличении количества путей, разрешенных для каждого ребра, с 1 до 2 гарантия аппроксимации уменьшается на значительную величину, которая, по сути, встраивает изменение в экспоненту: с O(m1/2) до O(m1/3).

(11.19) Алгоритм Greedy-Paths-with-Capacity c β = m1/3 является (4m1/3 + 1)-ап- проксимирующим алгоритмом в случае пропускной способности c = 2.

Доказательство. Начнем с ограничения \l*~l[ Согласно (11.17), имеем I (Р*) > β2 для всех i ^ I* - I. Суммируя по всем путям в I* - I, получаем

∑⅞∙)>i>∙i/∙-4

jіГ-і

С другой стороны, каждое ребро в решении I * используется не более чем двумя путями, поэтому

Объединяя эти границы с (11.18), получаем

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. АНАЛИЗ КОРОТКИЙ
  15. КОНТЕНТ - АНАЛИЗ
  16. Анализ документов
  17. МЕТОД АНАЛИЗА ЖИЗНИ
  18. АНАЛИЗ ДИСПЕРСИОННЫЙ