Как оказалось, алгоритмы локального поиска (см. раздел 4.3) являются очень эффективными средствами решения многих задач CSP. В них используется следующая формулировка с полным состоянием: в начальном состоянии присваивается значение каждой переменной, а функция определения преемника обычно действует по принципу изменения за один раз значения одной переменной. Например, в задаче с восемью ферзями начальное состояние может представлять собой случайную конфигурацию из 8 ферзей, стоящих на 8 столбцах, а функция определения преемника выбирает одного ферзя и рассматривает возможность перемещения его на какую-то другую клетку в том же столбце. Еще одна возможность предусматривает, чтобы поиск начинался с 8 ферзей (по одному на каждом столбце) в виде какой-то перестановки из 8 строк, а преемник формировался путем обмена двумя строками с двумя ферзями. В этой книге уже фактически был приведен пример применения локального поиска для решения задачи CSP — применение поиска с восхождением к вершине для решения задачи с п ферзями (с. 1). Еще одним примером может служить использование алгоритма Walks AT (с. 1) для решения задач удовлетворения ограничений, которые представляют собой частный случай задач CSP.

Наиболее очевидная эвристика, которая может применяться при выборе нового значения для какой-либо переменной, состоит в определении того, приводит ли выбранное значение к минимальному количеству конфликтов с другими переменными; таковой является эвристика с минимальными конфликтами. Соответствующий алгоритм приведен в листинге 5.3, пример его применения в задаче с восемью ферзями схематически показан на рис. 5.5, а полученные при этом результаты даны в табл. 5.1.

Листинг 5.3. Алгоритм Min-Conf licts, применяемый для решения задач CSP с помощью локального поиска. Начальное состояние может быть выбрано либо случайным образом, либо с помощью жадного процесса присваивания, в котором выбирается значение с минимальными конфликтами для каждой переменной по очереди. Функция Conflicts вычисляет количество ограничений, нарушенных данным конкретным значением, с учетом остальной части текущего присваивания

Рис. 5.5. Двухэтапный процесс решения задачи с восемью ферзями на основе эвристики с минимальными конфликтами. На каждом этапе выбирается ферзь для повторного назначения ему места в том же столбце. Количество конфликтов (в данном случае количество атакующих ферзей) показано в каждой клетке. Применяемый алгоритм предусматривает перемещение ферзя в клетку с минимальными конфликтами, разрешая неопределенность с помощью случайного выбора