Главная arrow книги arrow Копия Глава 4. arrow Поиск с восхождением к вершине
Поиск с восхождением к вершине

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

Алгоритмы с восхождением к вершине, описанные выше, являются неполными, поскольку часто оказываются неспособными найти цель, притом что она существует, из-за того, что могут зайти в тупик, достигнув локального максимума, Поиск с восхождением к вершине и перезапуском случайным образом руководствуется широко известной рекомендацией: "Если первая попытка оказалась неудачной, пробуйте снова и снова". В этом алгоритме предусмотрено проведение ряда поисков из сформированных случайным образом начальных состояний и останов после достижения цели. Он является полным с вероятностью, достигающей 1, даже по той тривиальной причине, что в нем в конечном итоге в качестве начального состояния формируется одно из целевых состояний. Если вероятность успеха каждого поиска с восхождением к вершине равна р, то ожидаемое количество требуемых перезапусков составляет 1/р. Для экземпляров задачи с восемью ферзями, если не разрешено движение в сторону,, поэтому для нахождения цели требуется приблизительно 7 итераций (6 неудачных и 1 успешная). Ожидаемое количество этапов решения равно стоимости одной успешной итерации, которая складывается с увеличенной в (1-р) /р раз стоимостью неудачи, или составляет приблизительно 22 этапа. Если разрешено движение в сторону, то в среднем требуется итераций и этапов. Поэтому алгоритм поиска с восхождением к вершине и перезапуском случайным образом действительно является очень эффективным применительно к задаче с восемью ферзями. Даже для варианта с тремя миллионами ферзей этот подход позволяет находить решения меньше чем за минуту.

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