Главная arrow Поиск arrow Применение локального поиска
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Применение локального поиска для решения задач удовлетворения ограничений Печать

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

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

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


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

function Min-Conflicts{csp, max_steps) returns решение current
  или индикатор неудачи failure
  inputs: csp, определение задачи удовлетворения ограничений
  max_steps, количество шагов, которые разрешается
  выполнить,
  прежде чем отказаться от дальнейших попыток
  current <— первоначальное полное присваивание для csp
  for i = 1 to max_steps do
    if current представляет собой решение для задачи csp
    then return current
    var <— выбранная случайным образом, конфликтующая переменная
    из Variables[csp]
    value <— значение v для var, которое минимизирует
    значение Conflicts{var, v, current, csp)
    задать значение var=value в решении current
return failure



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

Алгоритм с минимальными конфликтами показал себя чрезвычайно эффективным при решении многих задач CSP, особенно при наличии подходящего начального состояния. Его производительность показана в последнем столбце таблице. Больше всего достойно удивления то, что при решении задачи с п ферзями время прогона алгоритма с минимальными конфликтами остается почти независимым от размера задачи (если не учитываются затраты времени на первоначальную расстановку ферзей).

Данный алгоритм решает в среднем за 50 этапов (после начального присваивания) даже задачу с миллионом ферзей. Это замечательное достижение стало стимулом, побудившим к проведению значительной части исследований по локальному поиску в 1990-х годах, а также позволило уточнить различие между легкими и трудными задачами. Грубо говоря, задача с n ферзями является легкой для локального поиска, поскольку решения плотно распределены по всему пространству состояний. Кроме того, алгоритм с минимальными конфликтами успешно применяется при решении трудных задач. Например, он использовался для планирования наблюдений на космическом телескопе Хаббл, что позволило сократить затраты времени на планирование наблюдений, намеченных для проведения в течение одной недели, с трех недель примерно до 10 минут.

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