Лекция: Локальный поиск.
Рассматривавшиеся до сих пор алгоритмы поиска предназначались для систематического исследования пространств поиска. Такая систематичность достигается благодаря тому, что один или несколько путей хранится в памяти и проводится регистрация того, какие альтернативы были исследованы в каждой точке вдоль этого пути, а какие нет. После того как цель найдена, путь к этой цели составляет также искомое решение данной задачи.
Но при решении многих задач путь к цели не представляет интереса. Например, в задаче с восемью ферзями важна лишь окончательная конфигурация ферзей, а не порядок, в котором они были поставлены на доску.
Цель задачи с восемью ферзями состоит в размещении восьми ферзей на шахматной доске таким образом, чтобы ни один ферзь не нападал на любого другого. (Ферзь атакует любую другую, находящуюся на одной и той же с ним горизонтали, вертикали или диагонали.) На рис. 10.26 показана неудачная попытка поиска решения: ферзь, находящийся на самой правой вертикали, атакован по диагонали ферзём, находящимся на самой левой вертикали
|
|
К этому классу задач относятся многие важные приложения, такие как проектирование интегральных схем, разработка плана цеха, составление производственного расписания, автоматическое программирование, оптимизация сети связи, составление маршрута транспортного средства и управление портфелем акций.
Если путь к цели не представляет интереса, то могут рассматриваться алгоритмы другого класса, в которых вообще не требуются какие-либо данные о путях. Алгоритмы локального поиска действуют с учетом единственного текущего состояния (а не многочисленных путей) и обычно предусматривают только переход в состояние, соседнее по отношению к текущему состоянию. Как правило, информация о путях, пройденных в процессе такого поиска, не сохраняется. Хотя алгоритмы локального поиска не предусматривают систематическое исследование пространства состояний (не являются систематическими), они обладают двумя важными преимуществами: во-первых, в них используется очень небольшой объем памяти, причем обычно постоянный, и, во-вторых, они часто позволяют находить приемлемые решения в больших или бесконечных (непрерывных) пространствах состояний, для которых систематические алгоритмы не применимы.
Кроме поиска целей, алгоритмы локального поиска являются полезным средством решения чистых задач оптимизации, назначение которых состоит в поиске состояния, наилучшего с точки зрения целевой функции. Многие задачи оптимизации не вписываются в «стандартную» модель поиска в пространстве состояний, представленную в предыдущих разделах данного пособия. Например, природа предусмотрела такую целевую функцию (пригодность для репродукции), что дарвиновская эволюция может рассматриваться как попытка ее оптимизации, но в этой задаче оптимизации нет компонентов «проверка цели» и «стоимость пути». Для понимания сути локального поиска очень полезно рассмотреть ландшафт пространства состояний (подобный показанному на рис. 10.27). Этот ландшафт характеризуется и «местонахождением» (которое определяется состоянием), и «возвышением» (определяемым значением эвристической функции стоимости или целевой функции). Если возвышение соответствует стоимости, то задача состоит в поиске самой глубокой долины — глобального минимума, а если возвышение соответствует целевой функции, то задача заключается в поиске высочайшего пика — глобального максимума. (Минимум и максимум можно поменять местами, взяв их с обратными знаками.) Алгоритмы локального поиска исследуют такой ландшафт. Алгоритм полного локального поиска всегда находит цель, если она существует, а оптимальный алгоритм всегда находит глобальный минимум/максимум.
Целевая функция Глобальный максимум Локальный максимум
Уступ «Плоский» локальный максимум
Текущее состояние Пространство состояний
Рис. 10.27. Ландшафт одномерного пространства состояний, в котором возвышение соответствует целевой функции. Задача состоит в поиске глобального максимума. Как обозначено стрелкой, в процессе поиска по принципу «подъема к вершине» осуществляются попытки модификации текущего состояния в целях его улучшения. Различные топографические особенности ландшафта определены в тексте