logo
УП_САОД_2003

Локальные и глобальные оптимальные решения

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

  1. находится произвольное решение;

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

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

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

Этот метод имеет смысл лишь в том случае, когда можно ограничить совокупность преобразований небольшим ее подмножеством, что дает возможность выполнить все преобразования за относительно короткое время: если «размер» задачи равняется n, то можно допустить O(n2) или O(n3) преобразований. Если совокупность преобразований невелика, естественно рассматривать решения, которые можно преобразовывать одно в другое за один шаг, как «близкие». Такие преобразования называются «локальными», а соответствующий метод называется локальным поиском.

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

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

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

Рисунок 25. Локальный поиск в пространстве решений

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