Упражнения с решениями - Урок 12 - Локальный поиск

Упражнение с решением 1

Задача о выборе центров из главы 11 тоже может послужить примером для изучения эффективности алгоритмов локального поиска.

Ниже приведен простой пример локального поиска для выбора центров (на самом деле это типичная стратегия для разных задач, связанных с размещением). В этой задаче имеется множество мест S = {s₁, s₂, ..., s_n} на плоскости, и мы хотим выбрать множество из k центров C = {с₁, с₂, ..., с_k}, у которых радиус покрытия (наибольшее расстояние, на которое жителям любого из мест приходится перемещаться до ближайшего центра) как можно меньше.

Начнем с произвольного выбора k точек на плоскости в качестве центров c₁, c₂, ..., с_k. Далее поочередно выполняются следующие два шага:

(i) для заданного множества из k центров с₁, с₂, ..., с_k множество S делится на k множеств: для i = 1, 2, ..., k множество S_i определяется как совокупность всех мест, для которых с_i является ближайшим центром;

(ii) для этого разбиения S на k множеств строятся новые центры, как можно более “центральные” относительно них. Для каждого множества S_i находится наименьший круг на плоскости, содержащий все точки S_i, и центр с_i определяется как центр этого круга.

Если шаги (i) и (ii) приводят к строгому уменьшению радиуса покрытия, то выполняется следующая итерация; в противном случае алгоритм останавливается.

Чередование шагов (i) и (ii) основано на естественном взаимодействии между местами и центрами: на шаге (i) производится как можно лучшая разбивка мест для заданных центров, а на шаге (ii) выбирается как можно лучшее расположение центров для заданной разбивки мест. Помимо своей роли как эвристики для размещения, этот тип двухшагового взаимодействия также закладывает основу для алгоритмов локального поиска в статистике, где этот метод (по причинам, в которые мы углубляться не будем) называется методом максимизации ожидания.

(a) Докажите, что алгоритм локального поиска в конечном итоге завершается.

(b) Рассмотрим следующее утверждение.

Существует абсолютная константа b > 1 (не зависящая от конкретного экземпляра ввода), такая, что при завершении алгоритма локального поиска радиус покрытия его решения не более чем в b раз превышает оптимальный радиус покрытия. Решите, истинно или ложно это утверждение, и приведите доказательство или опровержение.

Доказательство. Первая мысль, которая приходит в голову при доказательстве части (а): множество радиусов покрытия убывает при каждой итерации; они не могут упасть ниже оптимальных значений, так что итерации должны завершиться. Но здесь необходима осторожность, потому что мы имеем дело с вещественными числами. А что, если радиусы покрытия уменьшаются при каждой итерации, но на все меньшую и меньшую величину, и алгоритм может выполняться сколь угодно долго при условии, что радиусы покрытия сходятся к некоторой величине?

Впрочем, справиться с этой проблемой не так уж сложно. Заметим, что радиус покрытия в конце шага (ii) каждой итерации полностью определяется текущим разбиением мест на множества S₁, S₂, ..., S_k. Существует конечное число способов разбиения мест на k множеств, и если бы алгоритм локального поиска выполнялся более этого количества итераций, он должен был бы произвести одно разбиение в двух итерациях. Но тогда в обеих итерациях был бы создан одинаковый радиус покрытия, а это противоречит предположению о том, что радиус покрытия строго убывает между итерациями. Это доказывает, что алгоритм всегда завершается. (Обратите внимание: он устанавливает только экспоненциальную границу количества итераций, так как количество разбиений множества мест на k множеств экспоненциально.)

Чтобы опровергнуть утверждение из части (b), будет достаточно найти пример выполнения алгоритма, в котором итерации “застревают” в конфигурации с очень большим радиусом покрытия. Сделать это несложно: для любой константы b > 1 рассмотрим множество S из четырех точек на плоскости, образующих высокий узкий прямоугольник с шириной w и высотой h = 2bw. Например, это могут быть четыре точки (0,0), (0,h), (w,h), (w,0).

Теперь предположим, что k = 2, и начнем с двух центров слева и справа от прямоугольника (допустим, (-1, h/2) и (w + 1, h/2)). Первая итерация проходит следующим образом:

♦ на шаге (i) S делится на две точки S₁ в левой части прямоугольника (с х-координатой 0) и две точки S₂ в правой части прямоугольника (с х-координатой w);

♦ на шаге (ii) центры размещаются в средних точках S₁ и S₂ (то есть (0,h/2) и (w,h/2)).

Можно убедиться в том, что при следующей итерации разбиение S не изменится, а следовательно, местонахождение центров тоже не изменится; здесь алгоритм завершается на локальном минимуме.

Радиус покрытия этого решения равен h/2, тогда как в оптимальном решении центры должны располагаться в средних точках верхней и нижней стороны прямоугольника с радиусом покрытия w/2. Таким образом, в нашем решении радиус покрытия в h/w = 2b > b раз больше оптимума.

Упражнения

1. Рассмотрим задачу нахождения устойчивого состояния в нейронной сети Хопфилда в специальном случае, когда все веса ребер положительны. Это соответствует задаче максимального разреза, которая обсуждалась ранее в этой главе: для каждого ребра e в графе G конечные точки предпочитают находиться в противоположных состояниях.

Теперь предположим, что граф G является связным и двудольным; узлы можно разбить на множества X и Y так, что один конец каждого ребра принадлежит X, а другой Y. Тогда существует естественная “лучшая” конфигурация для сети Хопфилда, в которой все узлы X имеют состояние +1, а все узлы Y имеют состояние -1. В этом случае все ребра являются хорошими, так как их концы находятся в противоположных состояниях.

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

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

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

Итак, рассмотрим следующий алгоритм градиентного подъема для нахождения паросочетания в двудольном графе:

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

(a) Приведите пример двудольного графа G, для которого этот алгоритм градиентного подъема не возвращает максимальное паросочетание.

(b) Имеются M и M' — паросочетания в двудольном графе G. Предположим, что |M'| > 2|M|. Покажите, что существует ребро e' ∈ M', для которого M U {e'} является паросочетанием в G.

(c) Используйте (b) для доказательства того, что любое локально оптимальное паросочетание в двудольном графе G, возвращаемое алгоритмом градиентного подъема, не менее по крайней мере половины максимального паросочетания в G.

3. Крупная биотехническая компания проводит эксперименты на двух дорогих высокопроизводительных машинах — обозначим их M₁ и М₂ (считается, что оборудование машин идентично). Каждый день появляется множество заданий, которые должны быть выполнены, и каждое задание должно быть назначено на одну из двух машин. Вам предложено помочь в составлении алгоритма распределения заданий между машинами, при котором ежедневные нагрузки остаются сбалансированными. Задача формулируется следующим образом: имеются n заданий, на выполнение каждого задания j требуется время t_j. Задания необходимо разбить на две группы A и B; множество A передается на машину M₁, а множество В — на машину M₂. Время, необходимое для обработки всех заданий на двух машинах, равно и Требуется добиться того, чтобы две машины были заняты приблизительно одинаковое время, то есть минимизировать |T₁ - T₂|.

Консультант, ранее участвовавший в работе, показал, что задача является NР-сложной (посредством сведения от задачи о сумме подмножеств). Теперь компания ищет хороший алгоритм локального поиска и предлагает следующий способ: начать с произвольного назначения заданий на две машины (допустим, задания 1, n/2 на машину M₁, остальные на машину M₂). Локальными переходами являются перемещения одного задания с одной машины на другую, причем задания перемещаются только тогда, когда перемещение приводит к абсолютному уменьшению времени обработки. Вам предложено ответить на основные вопросы относительно эффективности этого алгоритма.

(a) Первый вопрос: насколько эффективно такое решение? Предположим, не существует одного задания, доминирующего по затратам времени обработки, то есть для всех заданий j. Докажите, что для каждого локально оптимального решения время работы двух машин приблизительно сбалансировано:

(b) На следующем месте стоит время выполнения алгоритма: как часто задания будут перемещаться туда и обратно между двумя машинами? Вы предлагаете внести в алгоритм небольшое изменение. Если при локальном переходе много разных заданий перемещается с одной машины на другую, то алгоритм всегда должен перемещать задание j с максимальным t_j. Докажите, что в этом варианте каждое задание будет перемещено не более одного раза (а следовательно, локальный поиск завершится не более чем за n переходов).

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

4. Рассмотрим задачу распределения нагрузки из раздела 11.1. Ваши знакомые управляют группой веб-серверов; они разработали для задачи эвристику локального поиска, отличную от алгоритмов, описанных в главе 11.

Напомним, что в формулировке задачи имеются m машин M₁, ..., M_m и каждое задание требуется назначить на машину. Нагрузка i-го задания обозначается t_i. Периодом обработки называется максимальная нагрузка по всем машинам:

Эвристика локального поиска работает следующим образом: алгоритм начинает с произвольного распределения заданий между машинами и пытается многократно применить следующую “перестановку”:

Пусть A(i) и A(j) — задания, назначенные на машины M_i и M_j соответственно. Чтобы выполнить перестановку M_i и M_j, следует выбрать подмножества заданий B(i) ⊆ A(j) и B(j) ⊆ A(j) и “переставить” их между двумя машинами: то есть A(i) заменяется на A(i) U B(j) - B(i), а A(j) заменяется на A(j) U B(i) - B(j). (Разрешается B(i) = A(i), или B(i) может быть пустым множеством; аналогично для B(j).)

Рассмотрим перестановку, примененную к машинам M_i и M_j. Предположим, нагрузки на M_i и M_j перед перестановкой равны T_i и T_j соответственно, а после перестановки — T'_i и T'_j. Перестановка называется улучшающей, если max(T'_i, T'_j) < max(T'_i, T'_j), другими словами, если большая из двух задействованных нагрузок строго уменьшилась. Распределение заданий между машинами называется устойчивым, если не существует улучшающей перестановки, начинающейся с текущего распределения.

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

Пример. Допустим, имеются две машины: в текущем распределении на машину M₁ назначены задания с размерами 1, 3, 5, 8, а на машину М₂ — задания с размерами 2, 4. В этом случае единственная улучшающая перестановка определяет B(1) как множество из одного задания с размером 8, а B(2) — из задания с размером 2. После перестановки этих двух множеств полученное распределение состоит из заданий с размерами 1, 2, 3, 5 на машине M₁ и заданий с размерами 4, 8 на машине M₂. Это распределение является устойчивым (а также имеет оптимальный период обработки 12).

(a) Для этого определения не существует однозначных гарантий того, что эта эвристика локального поиска всегда завершается. А что, если она будет бесконечное перебирать распределения, которые не являются устойчивыми?

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

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

Примечания и дополнительная литература

Киркпатрик, Гелатт и Веччи (Kirkpatrick, Gelatt, Vecchi, 1983) разработали метод имитации отжига на основе алгоритма Метрополиса и др. (Metropolis et al., 1953), предназначенного для моделирования физических систем. При этом они выделили аналогию между энергетическими поверхностями и пространствами решений вычислительных задач.

В сборнике под редакцией Аартса и Ленстры (Aarts, Lenstra, 1997) рассматриваются многочисленные примеры использования методов локального поиска в алгоритмических задачах. Нейронные сети Хопфилда были предложены Хопфилдом (Hopfield, 1982) и проанализированы более подробно в книге Хайкина (Haykin, 1999). Эвристику разбиения графа из раздела 12.5 разработали Керниган и Лин (Kernighan, Lin, 1970).

Классификацию алгоритмов локального поиска, основанная на задаче разметки, разработали Бойков, Векслер и Забих (Boykov, Veksler, Zabih, 1999). Дальнейшие результаты и вычислительные эксперименты рассматриваются в диссертации Векслера (Veksler, 1999).

Задача многоагентной маршрутизации из раздела 12.7 поднимает вопросы, находящиеся на пересечении алгоритмов и теории игр — области, связанной с общими вопросами стратегического взаимодействия между агентами. Книга Осборна (Osborne, 2003) содержит введение в теорию игр; алгоритмические аспекты вопроса изложены в работах Пападимитриу (Papadimitriou, 2001) и Тардоса (Tardos, 2004), а также в диссертации и последующей книге Рафгардена (Roughgarden, 2002, 2004). Применение потенциальных функций для доказательства существования равновесия Нэша имеет долгую историю в теории игр (Beckmann, McGuire, Winsten, 1956; Rosenthal, 1973), а потенциальные функции были применены для анализа динамик наилучших ответов Мондерером и Шепли (Monderer, Shapley, 1996). Граница цены устойчивости для задачи маршрутизации из раздела 12.7 предложена Аншелевичем и др. (Anshelevich, 2004).