Дасгупты, Пападимитриу, Вазирани «Алгоритмы»

9.3. Эвристики локального поиска

281

(2-change neighborhood) пути s множество всех путей, которые могут быть получены из s заменой двух рёбер на другие два ребра. Вот пример такой замены:

DRAFTТем самым определяется алгоритм локального поиска для задачи коммивояжёра, и вопрос теперь в том, каково его время работы и всегда ли он находит оптимальное решение.

К сожалению, ни на один из этих вопросов мы не можем убедительно ответить. Каждая отдельная итерация выполняется быстро, поскольку окрестность любого пути содержит O(n2) элементов. Непонятно, однако, сколько всего понадобится итераций, чтобы дойти до минимума. Более того, даже когда мы до него и дойдём, мы сможем утверждать лишь, что найденный путь локально оптимален, то есть он не хуже всех путей из его окрестности. В то же время могут быть более выгодные пути, находящиеся вдали от текущего. На рисунке ниже показан пример такого рода: изображённый путь не является оптимальным, хотя и является оптимальным в своей 2-окрестности, и 2-изменениями его не улучшить.

Можно попробовать увеличить окрестности, разрешив заменять три ребра. В нашем примере этого хватит: в 3-окрестности сразу найдётся оптимальный путь.

Зато теперь на каждой итерации нам нужно будет перебирать O(n3) соседей, да и проблемы это полностью не решит: для такого поиска в 3-окрестно- сти тоже бывают локальные минимумы, не являющиеся глобальными. Можно было бы перейти, скажем, к 4-окрестностям, но тогда каждая итерация станет ещё медленнее. Как видно, за более высокое качество ответа нам приходится платить быстродействием. Чтобы алгоритм работал быстро, нужно, чтобы окружения не были слишком большими –– но чем они меньше, тем вероятнее застрять в локальном минимуме, далёком от оптимума. Компромиссный вариант приходится подбирать экспериментально.

282 Глава 9. Решение NP-полных задач

Рис. 9.7. (a) Девять городов США. (b) Поиск в 3-окрестности для задачи коммивояжёра (начатый с наугад взятого цикла). Оптимальный цикл находится за три шага.

(a)

Wichita
Albuquerque	Tulsa
Amarillo	Little Rock
DRAFT
Dallas
El Paso	Houston
San Antonio
(b)
(i)	(ii)
(iii)	(iv)

На рисунке 9.7 показан локальный поиск для задачи коммивояжёра на ранее рассмотренном нами графе, а рисунок 9.8 изображает работу подобных алгоритмов символически. Незакрашенная область –– это пространство решений, и их стоимость убывает сверху вниз. Алгоритм двигается вниз от начального решения, пока не дойдёт до локального минимума.

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

9.3. Эвристики локального поиска

283

Рис. 9.8. Локальный поиск.

стоимость

DRAFTлокальные оптимумы

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

9.3.2. Разбиение графа

Задача разбиения графа возникает во многих приложениях –– от проектирования микросхем до анализа программ и сегментации изображений. Её частным случаем является задача о сбалансированном разрезе (глава 8).

Разбиение графа

Вход: неориентированный граф G = (V, E) с неотрицательными весами на рёбрах и вещественное число 2 (0, 1=2].

Выход: разбиение вершин на две части A и B, размер каждой из которых не меньше jV j.

Цель: минимизировать размер разреза (A, B).

На рисунке 9.9 показан пример графа с 16 вершинами, все рёбра которого имеют вес 1. Стоимость оптимального решения для данного графа равна 0.

Если убрать ограничение на размер частей разбиения, то получится уже знакомая нам задача о минимальном разрезе, которая эффективно решается с помощью задачи о потоке. Однако задача о разбиении графа NP-трудна. Строя алгоритм локального поиска для этой задачи, удобно предполагать,

284	Глава 9. Решение NP-полных задач
Рис. 9.9. Вход задачи о разбиении графа и оптимальный разрез для = 1=2 (разделяет
белые и серые вершины).
что = 1=2 (ищем разбиение на равные части); это не очень существенно,
потому что общий случай сводится к этому частному.
Алгоритм локального поиска задаётся описанием окрестностей. Рассмот-
рим разрез (A, B) с jAj = jBj. Назовём его соседом (включим в окрестность)
любой разрез, полученный обменом двух вершин между частями, то есть раз-
рез вида (A fag + fbg, B fbg + fag), где a 2 A, b 2 B. На рисунке показан
такой обмен.
Насколько хорош такой алгоритм локального поиска? К сожалению, бы-
вают локальные минимумы, сильно отличающиеся от глобального. Ниже по-
казан пример такого локального минимума стоимости 2.
DRAFT

9.3. Эвристики локального поиска

285

Что тут можно поделать? Даже разрешив менять не по одной, а по две вершины, мы не поможем делу. Вместо этого давайте рассмотрим два других общих рецепта улучшения локального поиска.

9.3.3. Способы усовершенствования локального поиска

Рандомизация и перезапуски

Рандомизацию (случайный выбор) можно использовать и при выборе начальной точки (скажем, взяв случайное разбиение вершин на части), и при DRAFTвыборе очередного улучшения (если есть несколько возможностей).

Благодаря этому появляется ненулевая вероятность попасть в глобальный минимум, даже если локальных минимумов много. Если эта вероятность равна p, то можно запустить алгоритм O(1=p) раз и выбрать наилучший ответ (что с большой вероятностью даст глобальный минимум, см. упражнение 1.34).

На рисунке 9.10 показано пространство поиска в задаче о разбиении графа (для небольшого графа с 8 вершинами). Всего есть C4 = 70 разбиений, но

8

для каждого разбиения есть парное, в котором части переставлены, поэтому на рисунке показаны только 35 разбиений. Для удобства они объединены в семь групп. Есть пять локальных минимумов, из которых только один глобальный. Если начать локальный поиск в случайной точке и на каждом шаге выбирать случайный ход из наиболее выгодных, то вероятность попасть в плохой локальный минимум не более чем в четыре раза превосходит вероятность попасть в хороший. Поэтому будет достаточно небольшого количества перезапусков.

Метод имитации отжига

В примере на рис. 9.10 вероятность попасть в локальный минимум (при одном запуске алгоритма) не так уж мала. Но при увеличении размера задачи она может убывать экспоненциально, поэтому просто перезапустить алгоритм небольшое число раз уже не достаточно.

Вместо этого можно разрешать (иногда) переходить к худшим решениям: теоретически это может помочь выбраться из плохих локальных минимумов. На рис. 9.10 это могло бы помочь выйти из плохого локального минимума и перейти в хороший. Но как выбрать вероятности? Метод имитации отжига (simulated annealing) основан на физической аналогии и вводит неотрицательный параметр T , называемый температурой:

s какое-нибудь начальное решение повторять:

выбрать случайное решение s0 из окружения scost(s0) cost(s)

если < 0: заменить s на s0

иначе:

заменить s на s0 с вероятностью e =T

286	Глава 9. Решение NP-полных задач

Рис. 9.10. Пространство поиска для графа на восьми вершинах. Всего есть 35 вариантов. Они разбиты на семь групп, и для каждой группы показан один из вариантов. Есть пять локальных минимумов.

4 варианта, стоимость 6

DRAFT
8 вариантов, стоимость 4	2 варианта, стоимость 4
8 вариантов, стоимость 3	8 вариантов, стоимость 3
	4 варианта, стоимость 2
	1 вариант, стоимость 0

Упражнения

287

Для нулевого T (считаем, что тогда e =T = 0) последняя строка не выполняется, и этот алгоритм превращается в рассмотренный ранее. А для больших T этот алгоритм иногда будет делать ходы в сторону ухудшения. И какое же T нам выбрать?

Хитрость тут в следующем: мы начинаем с большого значения температуры T , а потом постепенно уменьшаем её до нуля. Сначала локальный поиск будет почти что случайным блужданием, но постепенно всё больше и больше станет предпочитать ходы в сторону меньшей стоимости и лишь изредка будет делать ходы в другую сторону. В некоторой момент процесс сойдётся к DRAFTлокальному минимуму, и его можно будет остановить. Пример такого рода движения изображён на рис. 9.11.

Рис. 9.11. Метод имитации отжига.

Данный метод называют «имитацией отжига». Как видно из названия, он исходит из аналогии с отжигом в металлургии (нагревание с последующим медленным охлаждением). Сначала, когда вещество почти что жидкое, атомы движутся почти свободно. При понижении температуры они постепенно располагаются всё более и более регулярно и наконец выстраиваются в кристаллическую решётку (близкую к минимуму энергии).

Конечно, имитация отжига требует больше времени, чем простой локальный поиск. Более того, выбор подходящей схемы отжига (annealing schedule), то есть стратегии понижения температуры, является достаточно творческой задачей. Но во многих случаях это существенно улучшает найденные решения и того стоит.

Упражнения

9.1. Допустим, что в алгоритме поиска с возвратом для задачи выполнимости мы всегда выбираем подзадачу (формулу в КНФ), содержащую самый короткий дизъюнкт, и расщепляем её по переменной этого дизъюнкта. Докажите,

288	Глава 9. Решение NP-полных задач

что время работы такого алгоритма на формулах с дизъюнктами длины 2 (задача 2-выполнимости) полиномиально.

9.2. Предложите алгоритм перебора с возвратом для задачи поиска гамильтонова пути из заданной вершины s. Укажите, что будет подзадачами, как выбирается одна из них и как она разбивается на части.

9.3. Примените метод ветвей и границ к задаче о покрытии множествами. Что будет подзадачами, как выбирается одна из них, как она разбивается на части и как вычисляется нижняя оценка?

DRAFTДокажите, что данный алгоритм всегда возвращает минимальное покрывающее дерево. Какое максимальное число итераций ему может для этого понадобиться?

Как вы думаете, насколько ваш алгоритм будет эффективен в типичных

примерах? Почему?

9.4. Дан неориентированный граф G = (V, E), в котором степень каждой вершины не больше d. Как быстро найти в нём независимое множество, размер которого составляет не менее 1=(d + 1) от размера максимального независимого множества?

9.5. Локальный поиск для минимального покрывающего дерева. Рассмотрим множество всех покрывающих деревьев (не обязательно минимальных) для данного неориентированного связного графа G = (V, E) с весами на рёбрах.

Из раздела 5.1 мы знаем, что добавление ребра e к покрывающему дереву T создаёт цикл. Удалив любое другое ребро e0 6= e из этого цикла, получим другое покрывающее дерево T 0. Будем говорить, что деревья T и T 0 получаются друг из друга заменой (e, e0) и считать такие деревья соседними.

(a) Покажите, что любое покрывающее дерево может быть получено из любого другого покрывающего дерева последовательностью замен (перехо-

дом от соседа к соседу). Сколько таких замен может потребоваться?

(b) Пусть T 0 –– минимальное покрывающее дерево, а T –– произвольное. Покажите, что можно найти последовательность замен, переводящую T в T 0, для которой стоимости (cost) деревьев не возрастают: в возникающей после-

довательности

T = T0 ! T1 ! T2 ! ‌ ! Tk = T 0

неравенство cost(Ti ) ¾ cost(Ti+1) выполнено для всех i < k.

(c) Рассмотрим следующий алгоритм локального поиска, который полу-

чает на вход неориентированный граф G.

T какое-нибудь покрывающее дерево графа G

пока есть замена рёбер (e, e0), уменьшающая cost(T ):

T T + e e0

вернуть T

9.6. На вход в задаче о дереве Штейнера (minimum Steiner tree) даётся полный неориентированный граф G = (V, E) с весами duv на рёбрах и множество

Упражнения

289

терминальных вершин (terminal nodes) V 0 V . Найти необходимо дерево минимального веса, содержащее все терминальные вершины V 0. Такое дерево может содержать также и вершины не из V 0.

DRAFTДругими словами, данный алгоритм является 2-приближённым (если распространить определение на вероятностные алгоритмы, взяв среднее). Более того, если длина всех дизъюнктов равна k, то данная оценка улучшается до

Допустим, что веса рёбер удовлетворяют свойствам метрики (с. 275). Докажите, что тогда следующий простой алгоритм является 2-приближённым: выкинем из графа все нетерминальные вершины и найдём минимальное покрывающее дерево. (Подсказка: вспомните рассмотренный нами приближённый алгоритм для задачи коммивояжёра.)

9.7. Входом задачи о мультиразрезе является неориентированный граф G = = (V, E) и множество терминальных вершин s1, ‌, sk 2 V . Найти требуется минимальное по размеру множество рёбер, после удаления которых никакие две терминальные вершины не будут лежать в одной компоненте связности.

(a) Покажите, что данная задача может быть решена за полиномиальное

время в частном случае, когда k = 2.

(b) Постройте 2-приближённый алгоритм для случая k = 3.

(c) Предложите алгоритм локального поиска для данной задачи.

9.8. В задаче максимальной выполнимости (maximum satisfiability) дано множество дизъюнктов и требуется найти значения переменных, при которых выполнено максимальное число дизъюнктов.

(a) Покажите, что если эту задачу можно решить (точно) за полиномиальное время, то за полиномиальное время можно решить и задачу выполнимо-

сти.

(b) Рассмотрим простой алгоритм, присваивающий каждой переменной равновероятно и независимо значение 0 или 1. Пусть входная формула содержит m дизъюнктов и kj обозначает количество литералов в j-м дизъюнкте. Покажите, что математическое ожидание количества выполненных дизъ-

юнктов равно

	m	•1	1	‹		m
	i=1				¾
			2kj			2 .
	X

1 + 1=(2k 1).

(c) Как переделать данный алгоритм в детерминированный (избавиться от случайных битов), сохранив качество приближения? (Подсказка: вместо того, чтобы выбирать значение каждой следующей переменной случай-

290 Глава 9. Решение NP-полных задач

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

9.9. В задаче о максимальном разрезе (maximum cut) требуется по данному неориентированному графу G = (V, E) с весами w(e) на рёбрах найти такое разбиение его вершин на две части, при котором суммарный вес рёбер, соединяющих эти две части, был бы максимален.

Для подмножества вершин S V определим w(S) как сумму w(e) для всех рёбер e = fu, vg, у которых jS \ fu, vgj = 1. Задача о максимальном разрезе

DRAFT(a) Покажите, что данный алгоритм является 2-приближённым.

состоит в максимизации w(S).

Рассмотрим следующий алгоритм локального поиска, в котором соседи множества получаются изменением (добавлением или удалением) одного

элемента:
S	какое-нибудь множество вершин										S0) = 1 и w(S0) > w(S):
пока есть S0			V такое, что	j	(S0		S)	[	(S
S	S0										j

(b) Является ли данный алгоритм полиномиальным по времени?

9.10. Назовём алгоритм локального поиска точным, если он всегда даёт оптимальное решение. Например, алгоритм для задачи о минимальном покрывающем дереве из упражнение 9.5 является точным. Симплекс-метод, решающий задачу линейного программирования, тоже можно считать точным алгоритмом локального поиска.

(a) Покажите, что алгоритм поиска в 2-окрестности для задачи коммивояжёра не является точным.

(b) Докажите то же самое для dn=2e-окрестности, где n –– количество городов.

(c) Покажите, что алгоритм поиска в (n 1)-окрестности является точным.

(d) Для оптимизационной задачи A назовём A-улучшением следующую задачу поиска: по данному входу x задачи A и данному решению s для входа x найти другое решение для x с лучшей стоимостью (или же сообщить, что s оптимально и поэтому лучшего решения нет). Например, задача улучшения цикла коммивояжёра выглядит так: дана матрица расстояний и гамильтонов цикл, и нужно найти лучший цикл. Оказывается, что эта задача NP-полна, как и задача улучшения покрытия множествами. Как это доказать?

(e) Скажем, что алгоритм локального поиска имеет полиномиальную итерацию, если каждый шаг улучшения в этом алгоритме занимает полиномиальное время. (Например, при естественной реализации алгоритма локального поиска в (n 1)-окрестности для задачи коммивояжёра такого не будет.) Докажите, что если P 6= NP, то для задачи коммивояжёра и задачи о покрытии множествами нет алгоритмов локального поиска с полиномиальной итерацией.