АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА И ЗАДАЧИ ОПТИМИЗАЦИИ
Рассматривавшиеся до сих пор алгоритмы поиска предназначались для систематического исследования пространств поиска. Такая систематичность достигается благодаря тому, что один или несколько путей хранится в памяти и проводится регистрация того, какие альтернативы были исследованы в каждой точке вдоль этого пути, а какие нет. После того как цель найдена, путь к этой цели составляет также искомое решение данной задачи.
Но при решении многих задач путь к цели не представляет интереса. Например, в задаче с восемью ферзями (см. с. 1) важна лишь окончательная конфигурация ферзей, а не порядок, в котором они были поставлены на доску. К этому классу задач относятся многие важные приложения, такие как проектирование интегральных схем, разработка плана цеха, составление производственного расписания, автоматическое программирование, оптимизация сети связи, составление маршрута транспортного средства и управление портфелем акций.
Если путь к цели не представляет интереса, то могут рассматриваться алгоритмы другого класса, в которых вообще не требуются какие-либо данные о путях. Алгоритмы локального поиска действуют с учетом единственного текущего состояния (а не многочисленных путей) и обычно предусматривают только переход в состояние, соседнее по отношению к текущему состоянию. Как правило, информация о путях, пройденных в процессе такого поиска, не сохраняется. Хотя алгоритмы локального поиска не предусматривают систематическое исследование пространства состояний (не являются систематическими), они обладают двумя важными преимуществами: во-первых, в них используется очень небольшой объем памяти, причем обычно постоянный, и, во-вторых, они часто позволяют находить приемлемые решения в больших или бесконечных (непрерывных) пространствах состояний, для которых систематические алгоритмы не применимы.
Кроме поиска целей, алгоритмы локального поиска являются полезным средством решения чистых задач оптимизации, назначение которых состоит в поиске состояния, наилучшего с точки зрения целевой функции. Многие задачи оптимизации не вписываются в "стандартную" модель поиска, представленную в главе 3. Например, природа предусмотрела такую целевую функцию (пригодность для репродукции), что дарвиновская эволюция может рассматриваться как попытка ее оптимизации, но в этой задаче оптимизации нет компонентов "проверка цели" и "стоимость пути".
Авторы пришли к выводу, что для понимания сути локального поиска очень полезно рассмотреть ландшафт пространства состояний (подобный показанному на рис. 4.7). Этот ландшафт характеризуется и "местонахождением" (которое определяется состоянием), и "возвышением" (определяемым значением эвристической функции стоимости или целевой функции). Если возвышение соответствует стоимости, то задача состоит в поиске самой глубокой долины — глобального минимума, а если возвышение соответствует целевой функции, то задача заключается в поиске высочайшего пика — глобального максимума. (Минимум и максимум можно поменять местами, взяв их с обратными знаками.) Алгоритмы локального поиска исследуют такой ландшафт. Алгоритм полного локального поиска всегда находит цель, если она существует, а оптимальный алгоритм всегда находит глобальный минимум/максимум.