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

Наконец, необходимо рассмотреть качество локальных оптимумов при таком определении соседских отношений. Вспомните, что в двух предыдущих попытках определения соседского окружения выяснилось, что в обоих случаях мы приходим к плохим локальным оптимумам.
Теперь мы покажем, что любой локальный опти- мум с новым соседским отношением является 2-аппроксимацией минимального возможного штрафа.

Начнем с рассмотрения оптимальной разметки f *; пусть для метки а L Va = = {i:f *(i) = а} обозначает множество узлов с меткой a в f '. Рассмотрим локально оп- тимальную разметку f Чтобы получить соседаf разметкиf, мы заменим метки всех узлов в Vа на а. Разметкаf является локально оптимальной, а следовательно, этот сосед f имеет не меньший штраф: Ф(f) > Ф(f). Рассмотрим разность Ф(fa) - Ф(f), которая, как мы знаем, не отрицательна. Какие величины вносят свой вклад в эту разность? Единственное возможное изменение в штрафах за назначение может происходить от узлов в Fj для каждого i V изменение равно c(f *(i)) - c(f(i)). Штрафы за разделение между двумя разметками различаются только в ребрах (i, j), по крайней мере один конец которых находится в V\ Следующее неравенство учитывает эти различия.

(12.10) Для разметки f и ее соседа f

Ч>Ю - Ф00 < ∑⅜ (/' (f))-⅞ (/W)] + Σ P9- Е Р:~r

i⅛I:, \t.j ⅛мпкf ,

/|jК⅛1

Доказательство. Изменение в штрафах за назначение равно Е, ,;cД/*(О).

Штраф за разделение для ребра (i, j) может различаться между двумя разметками только в том случае, если по крайней мере один конец ребра (i, j) принадлежит V\ Общий штраф за разделение в разметке f для таких ребер равен в точности

E ./V

⅜й./|⅛ w ⅛ir?⅜l',

т*su.i

тогда как в разметке fa штраф за разделение не превышает

∑ ⅞

|#./!⅛⅝iпgFj

для этих ребер. (Обратите внимание: последнее выражение всего лишь определяет верхнюю границу, так как ребро (i, j), выходящее из V*a другой конец которого на- ходится в а, не участвует в штрафе за разделениеf.) ■

Теперь можно переходить к доказательству основного утверждения.

(12.11) Для любой локально оптимальной разметки f и любой другой размет- ки f * - Ф(f) > 2Ф(f*).

Доказательство. Пусть fa — сосед f определенный ранее переназначением меток узлов на а. Разметка f является локально оптимальной, поэтому имеем Ф(f) - Ф(f) > 0 для всех а l.

Используем (12.10) для ограничения Ф(f) - Ф(f),

а затем просуммируем полученные неравенства для всех меток с получением сле- дующего результата:


Сгруппируем положительные слагаемые в левой части, а отрицательные — в правой. В левой части получаем c(f *(i)) для всех узлов i, что в точности равно штрафу за назначениеf *. Кроме того, слагаемоеРj учитывается дважды для каждого из ребер, разделенныхf* (по одному разу для каждой из двух метокf*(i) иf*(j)).

В правой части получаем c( f (i)) для всех узлов i, что в точности равно штрафу за назначение f Кроме того, учитываются слагаемые Рj для ребер, разделенныхf Каждый такой штраф за разделение учитывается хотя бы один раз, а возможно и дважды, если разделение также встречается в f *.

В итоге получаем следующее.


Граница в утверждении доказана. ■

Мы доказали, что все локальные оптимумы являются хорошими аппрокси- мациями для разметок с минимальным штрафом. Осталось разобраться еще с одним вопросом: насколько быстро алгоритм находит локальный оптимум? Вспомните, что в случае задачи о максимальном разрезе нам пришлось прибегнуть

к разновидности алгоритма, которая принимала только большие улучшения, так как повторные локальные улучшения могли не обеспечить полиномиальное время выполнения. То же самое происходит и здесь: пусть е > 0 — константа. Для задан- ной разметки f мы будем считать соседнюю разметку f ' значительным улучшением, если Ф( f') < (1 - е/3k) Ф( f). Чтобы алгоритм выполнялся за полиномиальное время, следует принимать только значительные улучшения и завершать его вы- полнение, когда они невозможны. После максимум е-1k значительных улучшений штраф уменьшается с постоянным множителем; следовательно, алгоритм завер- шится за полиномиальное время. Доказательство (12.11) нетрудно адаптировать для того, чтобы доказать следующее.

(12.12) Для любого фиксированного е > 0 версия алгоритма локального поиска, принимающая только значительные улучшения, завершается за полиномиальное время и приводит к такой разметкеf что Ф(f) < (2 + е) Ф(f *) для любой другой разметки f*.

12.7.

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