Лекция: Алгоритм поиска с восхождением к вершине

Алгоритм поиска с восхождением к вершине показан на рис. 10.28. Он пред­ставляет собой обычный цикл, в котором постоянно происходит перемещение в на­правлении возрастания некоторого значения, т.е. подъем. Работа этого алгоритма заканчивается после достижения «пика», в котором ни одно из соседних состояний не имеет более высокого значения. В данном алгоритме не предусмотрено сопрово­ждение дерева поиска, поэтому в структуре данных текущего узла необходимо реги­стрировать только состояние и соответствующее ему значение целевой функции. В алгоритме с восхождением к вершине не осуществляется прогнозирование за пре­делами состояний, которые являются непосредственно соседними по отношению к текущему состоянию. Это напоминает попытку альпиниста, страдающего от амне­зии, найти вершину горы Эверест в густом тумане, отсюда и название алгоритма.

Рисунок 10.28. Алгоритм поиска с восхождением к вершине (версия с наиболее крутым подъемом), который представляет собой самый фундаментальный метод локального поиска. На каждом эта­пе текущий узел заменяется наилучшим соседним узлом — преемником; в данной версии таковым является узел с максимальным значением своего состояния, но если необходимо определить состояние с минимальным значением, то может быть предусмотрен поиск соседнего узла с минимальным значением своего состояния.

Для иллюстрации поиска с восхождением к вершине воспользуемся задачей с во­семью ферзями. В алгоритмах локального поиска обычно применяется формулировка полного состояния, в которой в каждом состоя­нии на доске имеется восемь ферзей, по одному ферзю в каждом столбце. Функция определения преемника возвращает все возможные состояния, формируемые путем перемещения отдельного ферзя в другую клетку одного и того же столбца (поэтому каждое состояние имеет 8х7=56 преемников). Эвристическая функция стоимости h определяет количество пар ферзей, которые атакуют друг друга либо прямо, либо косвенно (атака называется косвенной, если на одной горизонтали, вертикали или диагонали стоят больше двух ферзей). Глобальный минимум этой функции стано­вится равным нулю, и это происходит только в идеальных решениях. На рис. 10.29, а показано состояние со значением h=17. На этом рисунке также показаны значения всех преемников данного состояния, притом что наилучшие преемники имеют зна­чение h=12. Алгоритмы с восхождением к вершине обычно предусматривают слу­чайный выбор в множестве наилучших преемников, если количество преемников больше одного.

Поиск с восхождением к вершине иногда называют жадным локальным поис­ком, поскольку в процессе его выполнения происходит захват самого хорошего со­седнего состояния без предварительных рассуждений о том, куда следует отправить­ся дальше. Жадность считается одним из семи смертных грехов, но, как оказалось, жадные алгоритмы часто показывают весьма высокую производительность. Во вре­мя поиска с восхождением к вершине зачастую происходит очень быстрое продви­жение в направлении к решению, поскольку обычно бывает чрезвычайно легко улучшить плохое состояние. Например, из состояния, показанного на рис. 10.29, а, достаточно сделать лишь пять ходов, чтобы достичь состояния, показанного на рис. 10.29, б, которое имеет оценку h=1 и очень близко к одному из решений.

а) б) в)

Рис. 10.29. Пример применения алгоритма с восхождением к вершине: диаграмма состояния за­дачи с восемью ферзями, характеризующегося эвристической оценкой стоимости h=17; на этой диаграмме показано значение h для каждого возможного преемника, полученное путем передвижения ферзя в пределах своего столбца; отмечены наилучшие ходы (а); локальный ми­нимум в пространстве состояний задачи с восемью ферзями; это состояние имеет оценку h=1, но каждый преемник характеризуется более высокой стоимостью (б). Одно из 92 решений задачи 8 ферзей (в).

Рассмотрим пошаговую работу алгоритма крутого восхождения (Таблица 10.5.) для решения задачи о восьми ферзях для их начального положения, отображённого на рис 10.29. а.

Каждый ход делается ферзём в пределах своего столбца, нумерация столбцов идёт слева направо, а нумерация строк – сверху вниз. Из двух состояний с одинаковой оценкой выбирается первое встреченное, если новый ход увеличивает оценку состояния, за счёт положения ферзей, установленных в предыдущих ходах – он не производится.

Таблица 10.11

Таблица 10.5. Пошаговая работа алгоритма крутого восхождения для решения задачи о восьми ферзях.

К сожалению, поиск с восхождением к вершине часто заходит в тупик по описан­ным ниже причинам.

· Локальные максимумы. Локальный максимум представляет собой пик, более высокий по сравнению с каждым из его соседних состояний, но более низкий, чем глобальный максимум. Алгоритмы с восхождением к вершине, которые достигают окрестностей локального максимума, обеспечивают продвижение вверх, к этому пику, но после этого заходят в тупик, из которого больше неку­да двигаться. Такая проблема схематически показана на рис. 10.27. Более кон­кретный пример состоит в том, что состояние, показанное на рис. 10.29, б, фак­тически представляет собой локальный максимум (т.е. локальный минимум для оценки стоимости h); задача еще не решена, а при любом передвижении отдельно взятого ферзя ситуация становится еще хуже.

· Хребты. Пример хребта показан на рис. 10.30. При наличии хребтов возникают последовательности локальных максимумов, задача прохождения которых для жадных алгоритмов является очень трудной.

· Плато. Это область в ландшафте пространства состояний, в которой функция оценки является плоской. Оно может представлять собой плоский локальный максимум, из которого не существует выхода вверх, или уступ, из которого возможно дальнейшее успешное продвижение (см. рис. 10.27). Поиск с восхож­дением к вершине может оказаться неспособным выйти за пределы плато.

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

В каждом из этих случаев рассматриваемый алгоритм достигает такой точки, из которой не может осуществляться дальнейшее успешное продвижение. Начиная со случайно сформированного состояния с восемью ферзями, алгоритм поиска с вос­хождением к вершине по самому крутому подъему заходит в тупик в 86% случаях, решая только 14% экземпляров этой задачи. Но он работает очень быстро, выполняя в среднем только 4 этапа в случае успешного завершения и 3 этапа, когда заходит в тупик. Это не очень плохой результат для пространства состояний с 88 = 17 миллио­нами состояний.

Алгоритм, приведенный на рис. 10.28., останавливается, достигнув плато, на ко­тором наилучший преемник имеет такое же значение, как и в текущем состоянии. Имеет ли смысл продолжать движение, разрешив движение в сторону в надежде на то, что это плато в действительности представляет собой уступ, как показано на рис. 10.27? Ответ на этот вопрос обычно является положительным, но необходимо со­блюдать осторожность. Если будет всегда разрешено движение в сторону, притом что движение вверх невозможно, могут возникать бесконечные циклы после того, как алгоритм достигнет плоского локального максимума, не являющегося уступом. Одно из широко применяемых решений состоит в том, что устанавливается предел количества допустимых последовательных движений в сторону. Например, можно разрешить, допустим, 100 последовательных движений в сторону в задаче с восемью ферзями. В результате этого относительное количество экземпляров задачи, решае­мых с помощью восхождения к вершине, возрастает с 14 до 94%. Но за этот успех приходится платить: алгоритм в среднем выполняет приблизительно 21 этап при ка­ждом успешном решении экземпляра задачи и 64 этапа при каждой неудаче.

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

При поиске с восхождением к вершине с выбором первого варианта реализуется

стохастический поиск с восхождением к вершине путем формирования преем­ников случайным образом до тех пор, пока не будет сформирован преемник, лучший по сравнению с текущим состоянием. Это — хорошая стратегия, если любое состояние имеет большое количество преемников (измеряемое тысяча­ми).

Алгоритмы с восхождением к вершине, описанные выше, являются неполными, по­скольку часто оказываются неспособными найти цель, притом что она существует, из-за того, что могут зайти в тупик, достигнув локального максимума. Поиск с восхождением к вершине и перезапуском случайным образом руководствуется широко известной ре­комендацией: «Если первая попытка оказалась неудачной, пробуйте снова и снова».

В этом алгоритме предусмотрено проведение ряда поисков из сформированных случай­ным образом начальных состояний8 и останов после достижения цели. Он является полным с вероятностью, достигающей 1, даже по той тривиальной причине, что в нём в ко­нечном итоге в качестве начального состояния формируется одно из целевых состояний.

Если вероятность успеха каждого поиска с восхождением к вершине равна р, то ожидае­мое количество требуемых перезапусков составляет 1/ р. Для экземпляров задачи с восе­мью ферзями, если не разрешено движение в сторону, р=0.14, поэтому для нахождения цели требуется приблизительно 7 итераций (6 неудачных и 1 успешная). Ожидаемое ко­личество этапов решения равно стоимости одной успешной итерации, которая складывается с увеличенной в (1- р)/рраз стоимостью неудачи, или составляет приблизительно 22 этапа. Если разрешено движение в сторону, то в среднем требуется 1/0.94=1.06 итераций и (lХ21) + (0.06/0.94)Х64=25 этапов. Поэтому алгоритм поиска с восхождением к вершине и перезапуском случайным образом действительно является очень эффективным применительно к задаче с восемью ферзями. Даже для варианта с тремя миллионами ферзей этот подход позволяет находить ре­шения меньше чем за минуту.

Успех поиска с восхождением к вершине в значительной степени зависит от

формы ландшафта пространства состояний: если в нем есть лишь немного локаль­ных максимумов и плато, то поиск с восхождением к вершине и перезапуском слу­чайным образом позволяет очень быстро найти хорошее решение. С другой сторо­ны, многие реальные задачи имеют ландшафт, который больше напоминает семей­ство дикобразов на плоском полу, где на вершине иглы каждого дикобраза живут другие миниатюрные дикобразы и т.д., до бесконечности. NР-трудные задачи обыч­но имеют экспоненциальное количество локальных максимумов, способных завести алгоритм в тупик. Несмотря на это, часто существует возможность найти достаточно хороший локальный максимум после небольшого количества перезапусков.