<<
>>

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

Понятно, что алгоритм выбирает пути, не пересекающиеся по ребрам. Если пред- положить, что граф G является связным, он должен выбрать хотя бы один путь. Но как количество выбранных путей сравнивается с максимально возможным? Ситуация, в которой могут возникнуть проблемы, изображена на рис.
11.9: один из путей (из s1 в 11) очень длинный, и если выбрать его первым, мы потеряем до Ω(m) других путей.

Теперь покажем, что предпочтительность коротких путей в жадном алгоритме не только избегает проблему, представленную в этом примере, но и ограничивает количество других путей, с которыми может взаимодействовать выбранный путь.

(11.16) Алгоритм Grееdv-Disjоiпt-Раths является (2 Jпt + l)-аппроксимирую- щим алгоритмом для задачи о максимальных непересекающихся путях.

Доказательство. Рассмотрим оптимальное решение: пусть I * — множество пар, для которых в этом оптимальном решении был выбран путь, а P*. для i I* — вы- бранные пути. Обозначим I множество пар, возвращаемых алгоритмом, а P.

для i I — соответствующие пути. Требуется ограничить |I *| в отношении |I |. Ключе- вую роль в этом анализе играет возможность различать короткие и длинные пути, которые рассматриваются по отдельности. Путь будет считаться длинным, если он содержит не менее 4пt ребер; в противном случае путь считается коротким. Пусть I *s обозначает множество индексов в I *, для которого соответствующий путь P’ является коротким, а Is — множество индексов I, для которого соответству- ющий путь Р является коротким.

Граф G содержит т ребер, и каждый длинный путь использует не менее ре- бер, так что в Г может быть не более 4т длинных путей.

Теперь рассмотрим короткие пути в I *. Чтобы множество I * было намного больше I, должно быть большое количество пар, соединенных в I *, но не в I. Рас- смотрим пары, соединенные оптимумом с использованием короткого пути, но не соединенные жадным алгоритмом.

Так как путь P*, соединяющий s. и t . в опти- мальном решении I *, является коротким, жадный алгоритм выбрал бы этот путь, если бы он был доступен, прежде чем выбирать какие-либо длинные пути. Но жад- ный алгоритм не соединил s и t., а следовательно, одно из ребер e на пути P* должно входить в путь P,, выбранный ранее жадным алгоритмом. Мы будем говорить, что ребро e блокирует путь P*.

Длины путей, выбранных жадным алгоритмом, монотонно возрастают, так как у каждой итерации остается меньше вариантов выбора путей. Путь Р. был выбран до рассмотрения P*f а следовательно, он должен быть короче: |Р.| < |Р*J < Jtit. Та- ким образом, путь P, является коротким. Так как пути, используемые оптимумом, не пересекаются по ребрам, каждое ребро в пути P, может блокировать не более одного пути Р*.. Отсюда следует, что каждый короткий путь Р. блокирует не более \ft>i путей в оптимальном решении, и мы получаем границу

JЧI,

Эта граница будет использована для получения границы общего размера опти- мального решения. Для этого множество I * рассматривается как состоящее из трех типов путей в соответствии с предшествующим анализом:

4- длинные пути, которых может быть не более ⅝/fй;

4 пути, также входящие в I;

4 короткие пути, не входящие в /, которые только что были ограничены |/J 4t)i.

Объединяя все сказанное, мы используем тот факт, что |I | > 1 всюду, где может быть соединен по крайней мере один набор терминальных пар, и получаем заяв- ленную границу:

|/|< ⅞+|/|+|/;-/|

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.