Поиск с восхождением к вершине
Алгоритм поиска с восхождением к вершине показан в листинге 4.2. Он представляет собой обычный цикл, в котором постоянно происходит перемещение в направлении возрастания некоторого значения, т.е. подъем. Работа этого алгоритма заканчивается после достижения "пика", в котором ни одно из соседних состояний не имеет более высокого значения. В данном алгоритме не предусмотрено сопровождение дерева поиска, поэтому в структуре данных текущего узла необходимо регистрировать только состояние и соответствующее ему значение целевой функции. В алгоритме с восхождением к вершине не осуществляется прогнозирование за пределами состояний, которые являются непосредственно соседними по отношению к текущему состоянию. Это напоминает попытку альпиниста, страдающего от амнезии, найти вершину горы Эверест в густом тумане.
Листинг 4.2. Алгоритм поиска с восхождением к вершине (версия с наиболее крутым подъемом), который представляет собой самый фундаментальный метод локального поиска. На каждом этапе текущий узел заменяется наилучшим соседним узлом; в данной версии таковым является узел с максимальным значением Value, но если используется эвристическая оценка стоимости h, то может быть предусмотрен поиск соседнего узла с минимальным значением h
function Hi11-Climbing(problem) returns состояние, которое представляет собой локальный максимум inputs: problem, задача local variables: current, узел neighbor, узел
current
State[current] current <— neighbor
Для иллюстрации поиска с восхождением к вершине воспользуемся задачей с восемью ферзями, которая представлена на с. 118. В алгоритмах локального поиска обычно применяется формулировка полного состояния, в которой в каждом состоянии на доске имеется восемь ферзей, по одному ферзю в каждом столбце. Функция определения преемника возвращает все возможные состояния, формируемые путем перемещения отдельного ферзя в другую клетку одного и того же столбца (поэтому каждое состояние имеет 8x7 = 5 6 преемников). Эвристическая функция стоимости h определяет количество пар ферзей, которые атакуют друг друга либо прямо, либо косвенно (атака называется косвенной, если на одной горизонтали, вертикали или диагонали стоят больше двух ферзей). Глобальный минимум этой функции становится равным нулю, и это происходит только в идеальных решениях. На рис. 4.8, а показано состояние со значением h=ll. На этом рисунке также показаны значения всех преемников данного состояния, притом что наилучшие преемники имеют значение h=12. Алгоритмы с восхождением к вершине обычно предусматривают случайный выбор в множестве наилучших преемников, если количество преемников больше одного.
Поиск с восхождением к вершине иногда называют жадным локальным поиском, поскольку в процессе его выполнения происходит захват самого хорошего соседнего состояния без предварительных рассуждений о том, куда следует отправиться дальше. Жадность считается одним из семи смертных грехов, но, как оказалось, жадные алгоритмы часто показывают весьма высокую производительность. Во время поиска с восхождением к вершине зачастую происходит очень быстрое продвижение в направлении к решению, поскольку обычно бывает чрезвычайно легко улучшить плохое состояние. Например, из состояния, показанного на рис. 4.8, я, достаточно сделать лишь пять ходов, чтобы достичь состояния, показанного на рис. 4.8, б, которое имеет оценку Ыи очень близко к одному из решений.
К сожалению, поиск с восхождением к вершине часто заходит в тупик по описанным ниже причинам.
• Локальные максимумы. Локальный максимум представляет собой пик, более высокий по сравнению с каждым из его соседних состояний, но более низкий, чем глобальный максимум. Алгоритмы с восхождением к вершине, которые достигают окрестностей локального максимума, обеспечивают продвижение вверх, к этому пику, но после этого заходят в тупик, из которого больше некуда двигаться. Такая проблема схематически показана на рис. 4.7. Более конкретный пример состоит в том, что состояние, показанное на рис. 4.8, б, фактически представляет собой локальный максимум (т.е. локальный минимум для оценки стоимости я); задача еще не решена, а при любом передвижении отдельно взятого ферзя ситуация становится еще хуже.
• Хребты. Пример хребта показан на рис. 4.9. При наличии хребтов возникают последовательности локальных максимумов, задача прохождения которых для жадных алгоритмов является очень трудной.
• Плато. Это область в ландшафте пространства состояний, в которой функция оценки является плоской. Оно может представлять собой плоский локальный максимум, из которого не существует выхода вверх, или уступ, из которого возможно дальнейшее успешное продвижение (см. рис. 4.7). Поиск с восхождением к вершине может оказаться неспособным выйти за пределы плато.
В каждом из этих случаев рассматриваемый алгоритм достигает такой точки, из которой не может осуществляться дальнейшее успешное продвижение. Начиная со случайно сформированного состояния с восемью ферзями, алгоритм поиска с восхождением к вершине по самому крутому подъему заходит в тупик в 86% случаях, решая только 14% экземпляров этой задачи. Но он работает очень быстро, выполняя в среднем только 4 этапа в случае успешного завершения и 3 этапа, когда заходит в тупик. Это не очень плохой результат для пространства состояний с 88=17 миллионами состояний.
Алгоритм, приведенный в листинге 4.2, останавливается, достигнув плато, на котором наилучший преемник имеет такое же значение, как и в текущем состоянии. Имеет ли смысл продолжать движение, разрешив движение в сторону в надежде на то, что это плато в действительности представляет собой уступ, как показано на рис. 4.7? Ответ на этот вопрос обычно является положительным, но необходимо соблюдать осторожность. Если будет всегда разрешено движение в сторону, притом что движение вверх невозможно, могут возникать бесконечные циклы после того, как алгоритм достигнет плоского локального максимума, не являющегося уступом. Одно из широко применяемых решений состоит в том, что устанавливается предел количества допустимых последовательных движений в сторону. Например, можно разрешить, допустим, 100 последовательных движений в сторону в задаче с восемью ферзями. В результате этого относительное количество экземпляров задачи, решаемых с помощью восхождения к вершине, возрастает с 14 до 94%. Но за этот успех приходится платить: алгоритм в среднем выполняет приблизительно 21 этап при каждом успешном решении экземпляра задачи и 64 этапа при каждой неудаче.
Разработано много вариантов поиска с восхождением к вершине. При стохастическом поиске с восхождением к вершине осуществляется выбор случайным образом одного из движений вверх; вероятность такого выбора может зависеть от крутизны движения вверх. Обычно этот алгоритм сходится более медленно по сравнению с вариантом, предусматривающим наиболее крутой подъем, но в некоторых ландшафтах состояний он находит лучшие решения. При поиске с восхождением к вершине с выбором первого варианта реализуется стохастический поиск с восхождением к вершине путем формирования преемников случайным образом до тех пор, пока не будет сформирован преемник, лучший по сравнению с текущим состоянием. Это — хорошая стратегия, если любое состояние имеет большое количество преемников (измеряемое тысячами). В упр. 4.16 предлагается исследовать этот алгоритм.
Алгоритмы с восхождением к вершине, описанные выше, являются неполными, поскольку часто оказываются неспособными найти цель, притом что она существует, из-за того, что могут зайти в тупик, достигнув локального максимума, Поиск с восхождением к вершине и перезапуском случайным образом руководствуется широко известной рекомендацией: "Если первая попытка оказалась неудачной, пробуйте снова и снова". В этом алгоритме предусмотрено проведение ряда поисков из сформированных случайным образом начальных состояний8 и останов после достижения цели. Он является полным с вероятностью, достигающей 1, даже по той тривиальной причине, что в нем в конечном итоге в качестве начального состояния формируется одно из целевых состояний. Если вероятность успеха каждого поиска с восхождением к вершине равна р, то ожидаемое количество требуемых перезапусков составляет 1/р. Для экземпляров задачи с восемью ферзями, если не разрешено движение в сторону, р=0 .14, поэтому для нахождения цели требуется приблизительно 7 итераций (6 неудачных и 1 успешная). Ожидаемое количество этапов решения равно стоимости одной успешной итерации, которая складывается с увеличенной в (1-р) /р раз стоимостью неудачи, или составляет приблизительно 22 этапа. Если разрешено движение в сторону, то в среднем требуется 1/0.94=1.06 итераций и (1x21) + (0 . 06/0 . 94) х64=25 этапов. Поэтому алгоритм поиска с восхождением к вершине и перезапуском случайным образом действительно является очень эффективным применительно к задаче с восемью ферзями. Даже для варианта с тремя миллионами ферзей этот подход позволяет находить решения меньше чем за минуту9.
Успех поиска с восхождением к вершине в значительной степени зависит от формы ландшафта пространства состояний: если в нем есть лишь немного локальных максимумов и плато, то поиск с восхождением к вершине и перезапуском случайным образом позволяет очень быстро найти хорошее решение. С другой стороны, многие реальные задачи имеют ландшафт, который больше напоминает семейство дикобразов на плоском полу, где на вершине иглы каждого дикобраза живут другие миниатюрные дикобразы и т.д., до бесконечности. NP-трудные задачи обычно имеют экспоненциальное количество локальных максимумов, способных завести алгоритм в тупик. Несмогря на это, часто существует возможность найти достаточно хороший локальный максимум после небольшого количества перезапусков.