Локальный поиск в задаче о вершинном покрытии

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

Итак, имеется граф G = (V, E); множество C возможных решений состоит из всех подмножеств S множества V, образующих вершинные покрытия. Например, всегда выполняется V Ѯ C.

Стоимость c(S) вершинного покрытия S равна его размеру; таким образом, минимизация стоимости вершинного покрытия эквивалентна нахождению покрытия с минимальным размером.

Наконец, в наших примерах алгоритмов локального поиска будет использоваться очень простое соседское отношение: мы говорим, что S Ң S’, если решение S’ может быть получено из S добавлением или удалением одного узла.

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

У этого соседского отношения есть одно полезное свойство:

(12.1) Каждое вершинное покрытие S имеет не более n соседних решений. Утверждение доказывается попросту тем, что каждое соседнее решение S получается добавлением или удалением узла.

Для начала рассмотрим очень простой алгоритм локального поиска — метод градиентного спуска. Градиентный спуск начинает с полного вершинного покрытия V и использует следующее правило выбора соседнего решения.

Обозначим S текущее решение. Если существует соседнее решение S’ со строго меньшей стоимостью, то выбрать соседа, имеющего как можно меньшую стоимость. В противном случае завершить работу алгоритма.

Итак, метод градиентного спуска двигается строго вниз, пока может; когда дальнейшее движение становится невозможным, он останавливается.

Мы видим, что градиентный спуск завершается точно в тех решениях, которые являются локальными минимумами: то есть в таких решениях S, что для всех соседних S’ выполняется c(S) ≤ c(S’).