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