1 Комбинаторные алгоритмы Локальный поиск

2 Простейшая задача o размещениях Дано: Полный граф G = (F D, E), стоимости вершин f: F Q + и ребер c: E Q + такие, что для любых трех вершин i, j, k F D выполнено c i,k c i,j + c j,k. Найти множество H F и назначение : D H такое, что общая стоимость открытых предприятий и стоимость назначения минимальна.

Как назначать клиентов F – множество предприятий D – множество клиентов Если множество открытых предприятий H задано, то оптимальным будет назначить каждого клиента к ближайшему предприятию. 3

Окрестность N(H) H, H : 1.Открыть новое предприятие H := H {i}, i F \ H, 2.Закрыть одно предприятие H := H \ {i}, i H. 3.Открыть одно новое предприятие и закрыть одно старое предприятие H := H {i}\ {j}, i F \ H, j H. В каждом из трех случаев перераспределить клиентов к ближайшим предприятиям. 4

5 Алгоритм локального поиска Input (G, f: F Q +, c: E Q + ) 1) Выбрать произвольное текущее решение H. 2) While существует решение H N(H) такое, что X H + Y H > X H + Y H do H:=H. Output (H, H )

Идея анализа Алгоритм локального поиска находит локальный оптимум в окрестности N(H). Оценим как сильно произвольный локальный оптимум в окрестности N(H) может отличаться от глобального. 6

7 Оценка на стоимость назначения Лемма 5.1 Рассмотрим произвольный локальный оптимум H и H. Тогда Y H X* + Y* = OPT..

8 Доказательство леммы 5.1(1) Сравним решение H c некоторым оптимальным решением H*. i* H* H. Добавим i* к H и переназначим всех клиентов таких, что *(j) = i* к предприятию i*. Так как H локальный оптимум, то стоимость нового решения должна быть больше чем стоимость решения H, H.

Доказательство леммы 5.1(2) i* H* H. Поскольку в решении H каждый клиент назначен к ближайшему предприятию, то Суммируя по всем предприятиям в оптимальном решении получим 9

10 Переназначение клиента j к предприятию i = γ( *(j)) при закрытии предприятия i. H H* γ i*=φ*(j) j i=φ(j) i=γ(φ*(j))

11 Стоимость переназначения Лемма 5.2 Рассмотрим произвольного клиента j, для которого φ(j) = i, и i i = γ(φ*(j)). Тогда стоимость переназначения клиента j от предприятия i к предприятию i не превышает 2c j,φ*(j).

12 Доказательство леммы 5.2 H H* γ i*=φ*(j) j i=φ(j) i=γ(φ*(j))

13 Оценка на стоимость предприятий Лемма 5.3 Рассмотрим произвольный локальный оптимум H и H. Тогда X H X* + 2Y*..

14 Доказательство леммы 5.3(1) Сравним решение H c некоторым оптимальным решением H*. Предположим, что мы хотим закрыть предприятие i H. Тогда каждый клиент j, обслуживавшийся в i должен быть назначен к другому предприятию в H{i}. Назовем предприятие i безопасным, если для любого предприятия i* H* предприятие γ(i*) ближайшее к i* в H не совпадает с i. Тогда при закрытии предприятия i, каждого его клиента j можно переназначить к предприятию γ(φ*(j)), а стоимость переназначения по лемме 5.2 оценить величиной 2c j,φ*(j).

15 Оценка на стоимость безопасных предприятий Так как H локальный оптимум, то стоимость нового решения при закрытии предприятия должна быть больше чем стоимость решения H, H.

16 Опасные предприятия Пусть i H опасное предприятие. Существует R = {i* H*|γ(i*) = i}, R. Пусть i ближайшее к i в R. Рассмотрим решения в окрестности N(H), возникающие при –добавлении к H предприятия i* R {i} –замене предприятия i на предприятие i.

17 Опасные предприятия i H H* i i = i опасные предприятия Каждое предприятие из H* попадает ровно в одно множество R.

18 Добавление к H предприятия i* R {i} Добавим к H предприятие i* и назначим всех клиентов j таких, что (j) = i и *(j) = i* к предприятию i*. Так как H локальный оптимум, то стоимость нового решения должна быть больше чем стоимость решения H, H.

19 Замена предприятия i на предприятие i. Заменим предприятие i на предприятие i. Переназначим клиентов j таких, что (j) = i и – *(j) R на предприятие γ( *(j)), – *(j) R на предприятие i.

20 Замена i на i. i H H* i R

21 Оценка стоимости замены i на i Заменим предприятие i на предприятие i: f if i. Переназначим клиентов j таких, что (j) = i и – *(j) R на предприятие γ( *(j)): Лемма 5.2 2c j,φ*(j). – *(j) R на предприятие i: =c ji c ji. Суммируя по всем клиентам и учитывая, что стоимость нового решения должна быть больше чем стоимость решения H, H, получим:

22 Оценка на стоимость опасного предприятия

23 Упрощение φ(j)=i & φ*(j)=i: c ji c ji 2c ji = 2c jφ*(j). φ(j)=i & φ*(j) R {i}: c ji + c jφ*(j) 2c ji c ii + c jφ*(j) c ji c iφ*(j) + c jφ*(j) c ji 2c jφ*(j).

24 Доказательство леммы 5.3(2) Безопасное предприятие i: Опасное предприятие i:

Оценка на локальный оптимум Теорема 5.4 Рассмотрим произвольный локальный оптимум H и H. Тогда X H +Y H 3OPT. Доказательство. Y H X* + Y* (Лемма 5.1) X H X* + 2Y* (Лемма 5.3) X H + Y H 2X* + 3Y* 3OPT. 25

Практика Оценить трудоемкость алгоритма локального поиска. Является ли алгоритм локального поиска полиномиальным? Рассмотрим следующий алгоритм. Input (G, f: F Q +, c: E Q + ) 1) Увеличить стоимость каждого предприятия в 2 раза, то есть положить f new := 2f i для всех i F. 2)Решить пример с новыми стоимостями алгоритмом локального спуска. Output (H, H ) Оценить стоимость полученного решения. 26