ПРИМЕНЕНИЕ ЛОКАЛЬНОГО ПОИСКА ДЛЯ РЕШЕНИЯ ЗАДАЧ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ

Как оказалось, алгоритмы локального поиска (см. раздел 4.3) являются очень эффективными средствами решения многих задач CSP. В них используется следующая формулировка с полным состоянием: в начальном состоянии присваивается значение каждой переменной, а функция определения преемника обычно действует по принципу изменения за один раз значения одной переменной. Например, в задаче с восемью ферзями начальное состояние может представлять собой случайную конфигурацию из 8 ферзей, стоящих на 8 столбцах, а функция определения преемника выбирает одного ферзя и рассматривает возможность перемещения его на какую-то другую клетку в том же столбце. Еще одна возможность предусматривает, чтобы поиск начинался с 8 ферзей (по одному на каждом столбце) в виде какой-то перестановки из 8 строк, а преемник формировался путем обмена двумя строками с двумя ферзями1. В этой книге уже фактически был приведен пример применениялокального поиска для решения задачи CSP — применение поиска с восхождением к вершине для решения задачи с п ферзями (с. 1). Еще одним примером может служить использование алгоритма WalkSAT (с. 1) для решения задач удовлетворения ограничений, которые представляют собой частный случай задач CSP.
Наиболее очевидная эвристика, которая может применяться при выборе нового значения для какой-либо переменной, состоит в определении того, приводит ли выбранное значение к минимальному количеству конфликтов с другими переменными; таковой является эвристика с минимальными конфликтами. Соответствующий алгоритм приведен в листинге 5.3, пример его применения в задаче с восемью ферзями схематически показан на рис. 5.5, а полученные при этом результаты даны в табл. 5.1.
Листинг 5.3. Алгоритм 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, особенно при наличии подходящего начального состояния. Его производительность показана в последнем столбце табл. 5.1. Больше всего достойно удивления то, что при решении задачи с п ферзями время прогона алгоритма с минимальными конфликтами остается почти независимым от размера задачи (если не учитываются затраты времени на первоначальную расстановку ферзей). Данный алгоритм решает в среднем за 50 этапов (после начального присваивания) даже задачу с миллионом ферзей. Это замечательное достижение стало стимулом, побудившим к проведению значительной части исследований по локальному поиску в 1990-х годах, а также позволило уточнить различие между легкими и трудными задачами, которое дополнительно будет рассматриваться в главе 7. Грубо говоря, задача с п ферзями является легкой для локального поиска, поскольку решения плотно распределены по всему пространству состояний. Кроме того, алгоритм с минимальными конфликтами успешно применяется при решении трудных задач. Например, он использовался для планирования наблюдений на космическом телескопе Хаббл, что позволило сократить затраты времени на планирование наблюдений, намеченных для проведения в течение одной недели, с трех недель (!) примерно до 10 минут.
Еще одним преимуществом локального поиска является то, что он может использоваться для оперативной корректировки в случае изменения условий задачи. Это особенно важно при решении задач планирования. Недельный график работы авиакомпании может включать тысячи рейсов и десятки тысяч персональных назначений, но из-за плохой погоды в одном аэропорту весь этот график может стать невыполнимым. Поэтому желательно иметь возможность откорректировать график с минимальным количеством изменений. Такую задачу легко выполнить с помощью алгоритма локального поиска, начинающего свою работу с текущего графика. Поиск с возвратами, выполняемый с учетом нового множества ограничений, обычно требует гораздо больше времени и может найти менее удачное решение, требующее внести много изменений в текущий график.







Материалы

Яндекс.Метрика