Локальный поиск (удовлетворение ограничений)

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

Все алгоритмы локального поиска используют функцию, которая оценивает качество присвоения, например количество ограничений, нарушенных присваиванием. Эта сумма называется стоимостью задания. Целью локального поиска является поиск задания с минимальной стоимостью, которое является решением, если таковое существует.

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

Самая простая форма локального поиска основана на выборе изменения, которое максимально снижает стоимость решения. Этот метод, называемый восхождением на холм , действует следующим образом: сначала выбирается случайное назначение; затем значение изменяется так, чтобы максимально улучшить качество результирующего назначения. Если после заданного количества изменений решение не найдено, выбирается новое случайное задание. Алгоритмы подъема в гору могут выйти из плато, только внося изменения, которые не влияют на качество задания. В результате они могут застрять на плато, где качество присвоения имеет локальные максимумы.

GSAT (greedy sat) был первым алгоритмом локального поиска выполнимости и формой восхождения в гору.

Метод выхода из локального минимума заключается в использовании взвешенной суммы нарушенных ограничений в качестве меры стоимости и изменении некоторых весов, когда нет доступных улучшающих ходов. Точнее, если никакое изменение не снижает стоимость задания, алгоритм увеличивает вес ограничений, нарушаемых текущим заданием.

Точка А не является решением, но никакое локальное перемещение оттуда не снижает стоимость. Однако решение существует в точке B.