<<
>>

Работоспособное соседское окружение при локальном поиске

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

Рассмотрим разметку f В процессе локального шага нашего нового алгоритма должно происходить следующее: мы выбираем одну метку а L и ограничиваем рассмотрение узлами, не имеющими метки a в разметке f За один локальный шаг любому подмножеству этих узлов разрешается изменить свои метки на а. Или в более формальном определении, две разметки f и f считаются соседними, если су- ществует метка а L, такое что для всех узлов i Vлибо f'(i) = f (i), либо f'(i) = а.

Обратите внимание на то, что это соседское отношение не является симметрич- ным; другими словами, f не удастся получить обратно из f' за один шаг. Теперь мы покажем, что для любой разметки f любого соседа можно найти за к вычислений минимального разреза, а локальный оптимум этого соседского окружения является

2- аппроксимацией разметки с минимальным штрафом.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Работоспособное соседское окружение при локальном поиске:

  1. Глава семнадцатая. Советы при лечении антидепрессантами В поисках «черной желчи»
  2. РАБОТОСПОСОБНОСТЬ
  3. Работоспособность
  4. 4.3.1. Информационные правоотношения, возникающие при осуществлении поиска, получения и потребления информации, информационных ресурсов, информационных продуктов, информационных услуг
  5. Поиск смысла жизни – это поиск бессмертия!
  6. 5.3. СОЦИАЛЬНОЕ СТРАХОВАНИЕ В СВЯЗИ С ВРЕМЕННОЙ УТРАТОЙ РАБОТОСПОСОБНОСТИ
  7. МОЗГ ГОЛОВНОЙ: ПСИХОФИЗИОЛОГИЯ ПОРАЖЕНИЙ ЛОКАЛЬНЫХ
  8. ЛОКАЛЬНЫЙ
  9. ПСИХОФИЗИОЛОГИЯ ПОРАЖЕНИЙ ЛОКАЛЬНЫХ МОЗГА ГОЛОВНОГО
  10. 5.4. СОЦИАЛЬНОЕ СТРАХОВАНИЕ ОТ НЕСЧАСТНОГО СЛУЧАЯ НА ПРОИЗВОДСТВЕ И ПРОФЕССИОНАЛЬНОГО ЗАБОЛЕВАНИЯ, КОТОРЫЕ ПОВЛЕКЛИ ПОТЕРЮ РАБОТОСПОСОБНОСТИ
  11. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
  12. 4.3. Акти договірного та локального характеру у сфері трудового права