Алгоритмы локального поиска.

Алгоритмы локального поиска

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

1. Начните с произвольного решения.

2. Для улучшения текущего решения примените к нему какое-либо преобразование из некоторой заданной совокупности преобразований. Это улучшенное решение становится новым "текущим" решением.

3. Повторяйте указанную процедуру до тех пор, пока ни одно из преобразований в заданной их совокупности не позволит улучшить текущее решение.

Результирующее решение может, хотя и необязательно, оказаться оптимальным. В принципе, если "заданная совокупность преобразований" включает все преобразования, которые берут в качестве исходного одно решение и заменяют его каким-либо другим, процесс "улучшений" не закончится до тех пор, пока мы не получим оптимальное решение. Но в таком случае время выполнения пункта 2) окажется таким же, как и время, требующееся для анализа всех решений, поэтому описываемый подход в целом окажется достаточно бессмысленным. Этот метод имеет смысл лишь в том случае, когда мы можем ограничить нашу совокупность преобразований небольшим ее подмножеством, что дает возможность выполнить все преобразования за относительно короткое время: если "размер" задачи равняется , то мы можем допустить или преобразований. Если совокупность преобразований невелика, естественно рассматривать решения, которые можно преобразовывать одно в другое за один шаг, как "близкие". Такие преобразования называются "локальными", а соответствующий метод называется локальным поиском.

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

Продолжение 31

 

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

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

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

Задача коммивояжера

Методы локального поиска особенно хорошо подходят для решения задачи коммивояжера. Простейшим преобразованием, которым можно в этом случае воспользоваться, является так называемый "двойной выбор". Он заключается в том, что мы выбираем любые два ребра, например ребра (А, В) и (С, D), показанные на рис. 10.20, удаляем их и "перекоммутируем" соединявшиеся ими точки так, чтобы образовался новый маршрут. На рис. 10.20 этот новый маршрут начинается в точке В, продолжается по часовой стрелке до С, проходит по ребру (С, А), затем — против часовой стрелки от А к D и наконец по ребру (D, В). Если сумма длин (А, С) и (В, D) оказывается меньше суммы длин (А, В) и (С, D), значит, нам удалось получить улучшенный маршрут.1 Обратите внимание, что мы не можем соединить точки А и D, В ~и С, поскольку полученный результат будет являться не маршрутом, а двумя изолированными друг от друга циклами.

 

Приближенные алгоритмы.

 

Многие задачи, представляющие практический интерес – NP- полные.

‡ Для них маловероятно найти точный алгоритм с полиномиальным временем работы.

‡ При небольшом объеме входных данных может подойти алгоритм, время работы которого выражается показательной функцией.

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

‡ Можно найти в течение полиномиального времени решение, близкое к оптимальному.

‡ Алгоритм, возвращающий решения, близкие к оптимальным, называется приближенным алгоритмом.

----------------------

Пусть дан вход I оптимизационной задачи Π. Через sol(I) обозначим множество всех возможных решений.

Будем считать, что sol(I) ̸= ∅ для любого входа I. Каждому возможному решению x ∈ sol(I) сопоставлена стоимость cost(x). Требуется найти x ∈ sol(I), на котором cost достигает своего оптимального (минимального или максимального) значения. Приближенным алгоритмом (approximation algorithm) для задачи

Π называется полиномиальный по времени алгоритм, возращающий для каждого входа I какое-то решение x ∈ sol(I). Через A(I) мы обозначаем стоимость решения, найденного алгоритмом A на входе I.

Приближенный алгоритм A имеет абсолютную оценку точности (absolute performance guarantee) c, если для любого входа I выполняется неравенство |OPT(I) − A(I)| ≤ c.

Приближенный алгоритм A имеет относительную оценку точности (relative performance guarantee) 𝛼, если для любого входа I выполняется неравенство

A(I)/OPT(I) ≥ 𝛼 для максимизационной задачи;

A(I)/OPT(I) ≤ 𝛼 для минимизационной задачи.

Такие алгоритмы мы называем 𝛼-приближенными.

Для оптимизационных задач 𝛼 ≤ 1, для минимизационных — 𝛼 ≥ 1.

Алгоритм тем лучше, чем ближе 𝛼 к 1.

Пусть дана максимизационная задача Π. Π имеет полиномиальную приближенную схему (polynomial time approximation scheme, PTAS), если

1 для любого 𝜖 ≥ 0 существует (1 − 𝜖)-приближенный алгоритм для Π;

2 для любого 𝜖 > 0 время работы такого алгоритма зависит от n полиномиально.

Если же время работы такого алгоритма полиномиально не только по n, но и по 1/𝜖, то полученная схема называется полностью полиномиальной приближенной схемой (fully

polynomial time approximation scheme, FPTAS). Определение для минимизационной задачи полностью

аналогично.