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

     Псевдокод алгоритм выглядит следующим образом: 

all constraints := list of all constraints, strongest first;

all variables := set of all variables;

active_constraints := new set;

for v in all variables do

  initialize v.bounds to unbounded;

end for; 

for current constraint in all constraints do

  tight_variables := new set;

  queue := new queue;

  queue.add(current_constraint);

  while queue not empty do

     cn := queue.front;

     tighten_bounds(cn, queue, tight_variables,

     active_constraints);

     check_constraint(cn, active_constraints);

     queue.dequeue;

  end while;

end for; 

     Переменная  active_constraints содержит множество ограничений, которые уже были рассмотрены, но которые могут быть рассмотрены опять, если мы сожмем границы одной из переменной ограничений. Во время обработки каждого ограничения очередь (queue) содержит множество ограничений, границы чьих переменных может потребоваться сжать, и tight_variables – это множество переменных, чьи границы были сжаты во время обработки текущего ограничения. Во время обработки текущего ограничения мы никогда не сжимаем границы одной переменной дважды.

     Процедура tighten_bounds сжимает границы переменных ограничения , и добавляет в очередь другие затронутые ограничения. Процедура check_constraint проверяет на неудовлетворенность требуемые ограничения и также определяет, когда ограничения должны быть добавлены или удалены из множества active_constraints. 

Procedure tighten_bounds(cn, queue, tight variables, active constraints)

  for v in cn.variables and v not in tight_variables do

    tighten_flag := cn.tighten_bounds_for(v);

    tight_variables.add(v);

    if tighten_flag then

 for c in v.constraints do

if c in active_constraints and c not in queue then

     queue.add(c);

   end if;

       end for;

    end if;

  end for;

end procedure tighten_bounds; 

     В процедуре tighten_bounds процедура tighten_bounds_for сжимает границы переданной переменной, на сколько это возможно, и возвращает истину, если границы изменились. 

Procedure check_constraint(cn, active constraints)

  If cn is unary then

    If cn is required and cn is not satisfiable then

       exception(required_constraint_not_satisfied);

    end if;

    return;

  end if;

  if not all of c’s variables have unique values then

    active_constraints.add(cn);

    return;

  end if;

  if cn is satisfied then

    active_constraints.delete(cn);

  else if cn is required then

    exception(required_constraint_not_satisfied);

  else exception(constraints_too_difficult);

  end if;

end procedure check_constraint; 

     В процедуре check_constraint мы в первую очередь смотрим, унарное ли ограничение . Унарным является то ограничение, которое содержат только одну переменную. Унарное ограничение должно быть обработано только один раз, т.к. нет больше причин рассматривать его, потому что его влияние полностью представлено в текущих границах переменной, которую оно содержит. Иначе ограничение является -арным. Если не все переменные имеют уникальные значения, то нам необходимо добавить в active_constraints, т.к. нам будет необходимо рассмотреть опять, когда границы одной из его переменных будут сжаты. Однако, если все переменные имеют уникальные значения, больше никогда не нужно будет рассматривать, и ограничение нужно удалить из active_constraints, если оно там находится.

     Рассмотрим  применение алгоритма Indigo на следующем примере. Пусть нам дана система уравнений

        (2.1)

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

      Ограничения начинают обрабатываться от самого сильного к слабому. Так после обработки  неравенства  мы сжимаем границы до . Затем обрабатываем следующее сильное ограничение , сжимая границы к . Оба из этих ограничений одноместны, так что они не добавляются к активным ограничениям. Затем, мы обрабатываем , сжимая границы до . С этого момента переменные этого ограничения имеют уникальную ценность, поэтому мы записываем это ограничение в активные ограничения. Последнее требуемое ограничение – . Мы обрабатываем его и сжимаем границы до , и также добавляем его в активные ограничения.

     Теперь  переходим к строгому ограничению  . Благодаря этому неравенству границы сжимаются до . Сжатие границ приводит к тому, что нам необходимо пересмотреть через неравенство , которое находится в активных ограничениях, т.е. новые границы будут . А так как границы изменились, пересматриваем еще одно активное ограничение , получаем, что границы равны , а границы  равны .

     Затем мы обрабатываем среднее ограничение  . С этих пор границы переменной устанавливаем и сжимаем границы до , до , и до .

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

      2.2 Реализация на ЭВМ алгоритма  Indigo

     На  основе материала данной курсовой работы была разработана программа «Метод Индиго» на языке программирования Delphi, реализующая применение алгоритма Indigo для решения системы ограничений (2.1).

     После запуска программы перед пользователем  появляется диалоговое окно, наглядный вид которого представлен на рис.2.1.

Рисунок 2.1 – Диалоговое окно метода Indigo

      Основная  часть данного окна разделена  на две составляющие:

      – текстовое поле «Условие», предназначенное для ввода исходной системы ограничений;

      – текстовое поле «Шаги решения», отображающее этапы решения алгоритма.

      При вводе ограничений в текстовое поле «Условие» пользователю необходимо указать статус каждого уравнения: сильное – r, строгое – s, среднее – m или слабое – w (рис. 2.2)

Рисунок 2.2 – Исходные данные

      В нижней части диалогового окна расположена кнопка «Решить».  При нажатии на данную кнопку в правой части диалогового окна появляются пошаговые изменения переменных системы (рис 2.3), благодаря этому можно проследить на каком этапе и границы какой переменной были сжаты, а также можно увидеть решение системы в диалоговом окне «Решение» (рис. 2.4).

Рисунок 2.3 – Этапы решения 

Рисунок 2.4 – Результат реализации алгоритма

      Текс  программной реализации алгоритма находится в приложении А. 

      2.3 Алгоритм Incremental Hierarchical Constraint Solver (IHCS)

     Incremental Hierarchical Constraint Solver (IHCS) – алгоритм пошагового иерархического решения системы ограничений. В алгоритме IHCS, как и в Indigo, система ограничений может содержать как равенства, так и неравенства. Алгоритм базируется на идее преобразования начальной конфигурации , соответствующей иерархии ограничений, в конфигурацию решения. При этом алгоритм обрабатывает ограничения от сильного к слабому. Конфигурация иерархии представляет собой тройку , таких, что их объединение равно , где – хранилище активных ограничений, т.е. тех, которые уже были обработаны и удовлетворены; – хранилище смягченных ограничений, т.е. обработанных, но неудовлетворенных неравенств; – хранилище неисследованных уравнений, которые в дальнейшем будут обработаны.

     Псевдокод данного алгоритма выглядит следующим  образом:

procedure IHCS(H: constraint hierarchy)

 AS•RS•US <- 0•0•H;

 while US not empty do

  apply forward rule to AS•RS•US, i.e., move c from US to AS

  if conflict in AS then

   apply backward rule to AS•RS•US;

  endif

 endwhile

end IHCS 

     Алгоритм  начинается с конфигурации . Затем, поочередно от сильного ограничения к слабому, неравенства перемещают из хранилища неисследованных (изначально ) в хранилище активных (изначально пустого). IHCS разделен на 2 фазы: прямой ход, в ходе которого используется «прямое правило», и обратный ход, соответствующий «обратному правилу», которое вызывается для разрешения любых конфликтов, возникающих во время прямого хода.

     Прямой  алгоритм – это адаптация алгоритма совместимости по дугам (arc consistency), основанного на распространении ограничений, обобщенного на случай ограничений с произвольным числом переменных. Прямой ход реализуется с помощью функции Forward. 

Function Forward()

      while US = c_jUS^’ do

      US ¬ US^’

      AS ¬ ASÈ{c_j}

      AO ¬ AO+1

      AO_cj ¬ AO

      Enqueue(c_j,Q)  ‘Q initially epty

            while Dequeue(Q,c_k) do

                  if not Revise(c_k,T_cj,Q) then

                        if not Backward(c_k) then return false

      return true 

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

     Функция Revise осуществляет удаление несовместимых ограничений из области переменных и обновляет информацию о зависимости между ограничениями. Все эти преобразования запоминаются в стеке , а активные ограничения, содержащие затронутые ограничения, ставятся в очередь  (очередь распространения). Если там нет значений, удовлетворяющих , тогда Revise возвращает false, иначе true.

     Во  время работы обратного алгоритма  должны выполняться следующие условия:

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

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