Применение методов распространения ограничений при поиске допустимых решений (стр. 4 из 6)

Теперь переходим к строгому ограничению

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

Затем мы обрабатываем среднее ограничение

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

Наконец мы обрабатываем самое слабое ограничение

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

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

endIHCS

Алгоритм начинается с конфигурации

. Затем, поочередно от сильного ограничения к слабому, неравенства перемещают из хранилища неисследованных (изначально ) в хранилище активных (изначально пустого). 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

returntrue

Счетчик

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

Функция Revise осуществляет удаление несовместимых ограничений из области переменных

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