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

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

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

2. Повторно должна быть достигнута потенциально лучшая конфигурация, чтобы добиться значимого результата.

3. Никакая перспективная конфигурация не должна использоваться повторно, чтобы избежать циклов.

4. Для полноты алгоритма никакая перспективная конфигурация не должна быть пропущена.

5. Должна быть достигнута глобальная совместимость нового хранилища активных ограничений, повторно выполняя при этом как можно меньше работы.

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

Ограничения, смягченные в предыдущих конфликтах, следует пересмотреть на предмет реактивации, если некоторые ограничения, вовлеченные в те конфликты, сейчас смягчены. Это даст шанс, что новое смягчение также разрешит эти ранние конфликты, следовательно, позволяет ранее смягченным ограничениям стать активными. За осуществление обратного правила отвечает функция Backward.

И наконец, алгоритм IHCSостанавливается, как только конфигурация становится

Рассмотрим следующий пример:

при этом начальные значения

равны

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

помещается в хранилище

. Затем оно попадает в

, где проверяются значения параметров

, тогда по правилу разности интервалов получим

, далее находим пересечение

. Таким образом, получили новые границы

. Аналогично для

получаем

На втором шаге из

попадает второе ограничение

. Попробуем удовлетворить его. По правилу умножения и разности интервалов:

. Как видно это неравенство не удовлетворяется, поэтому оно перемещается в хранилище

Учитывая третье ограничение

, мы пересчитываем границы

, откуда получаем

соответственно. Рассматривая последнее ограничение, можно сделать вывод, что это ограничение у нас, также как и второе, не удовлетворяется.

ЗАКЛЮЧЕНИЕ

В данной курсовой работе были рассмотрены основные понятия интервальной арифметики и задачи распространения ограничений.

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

Для решения задач распространения ограничений существует различное множество алгоритмов. В курсовой работе были рассмотрены два из них: алгоритм распространения ограничений Indigo и IHCS (IncrementalHierarchicalConstraintSolver). Алгоритм Indigo заключается в том, что при обработке ограничений от самого сильного к самому слабому мы пытаемся удовлетворить каждое ограничение путем сжимания границ переменных, входящих в него, при этом сжимание границ одних переменных ограничения может стать причиной сжимания границ других переменных. Для выполнения этих действий в алгоритме используется очередь ограничений, которые необходимо проверить. Изначально очередь содержит только исходные ограничения

. Если мы можем сжать границы любой переменной ограничения

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

Алгоритм IHCSбазируется на идее преобразования начальной конфигурации

, соответствующей иерархии ограничений, в конфигурацию решения. Конфигурация иерархии

представляет собой тройку

, таких, что их объединение равно

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

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

(изначально

) в хранилище активных

(изначально пустого). IHCSостанавливается, как только конфигурация становится

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Семенов, А.Л. Методы распространения ограничений: основные концепции / А.Л. Семенов // Международное совещание по интервальной математике и методам распространения ограничений: труды совещания. – Новосибирск. – 2003. – С. 6–20.

2. Лоенко, М. Решение систем нелинейных уравнений методами интервального распространения ограничений / М. Лоенко // Новосибирский филиал Российского научно-исследовательского института искусственного интеллекта. – Россия. – Том 7. – №2. – 2002.– С.84–93.

3. Borning, A. The Indigo Algorithm / A. Borning, R. Anderson, B. Freeman-Benson // TR 96-05-01, Department of Computer Science and Engineering, University of Washington. – 1996.

4. Menezes, F. Incremental Hierarchical Constraint Solver (IHCS) / F. Menezes, P. Barahoma, P. Codognet // An Incremental Hierarchical Constraint Solver, in: Proceedings of PPCP93, – Newport, 1993. – pp. 190-199.

5. Barták, R. Constraint Guide – Constraint Hierarchy Solvers / R. Barták // Guide to Constraint Programming [Электронныйресурс]. – 1998. – Режимдоступа : http://kti.mff.cuni.cz/~bartak/constraints/ch_solvers.html. – Датадоступа : 25.04.2010.

ПРОЛОЖЕНИЕ А

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, UMathParser, MyFunctions;

type

TForm1 = class(TForm)

Button1: TButton;

GroupBox1: TGroupBox;

ListBox1: TListBox;

GroupBox3: TGroupBox;

Memo1: TMemo;

procedure Button1Click(Sender: TObject);

private { Private declarations }

public { Public declarations }

end;

TConstraint = class

constructor Create(Constraint : string);

destructor Free;

function TightenBoundsForEqual(V : string) : boolean;

function TightenBoundsForNoEqual(V : string) : boolean;

function TightenBoundsForWeakEqual(V : string) : boolean;

function TightenBoundsFor(V : string) : boolean;

function IsElemInVars(Elem : string) : boolean;

public

Prior : char; // приоритет ограничения

CType : char; // тип ограничения <= = >= 'l' 'e' 'm'

Variables : TSArray; // переменные

VarCount : integer; // число переменных

LPart, RPart : TMathParser;

end;

TVariable = class

VarName : string;

LBound, RBound : extended; // границы интервала

constructor Create(pName: string; pLBound, pRBound: extended);

destructor Free;

procedure SetBounds(pLBound,pRBound : extended);

end;

TConstraintList = record

Count : integer;

List : array of TConstraint;

end;

TVariableList = record

Count : integer;

List : array of TVariable;

end;

const

LInfinity = -1e50; // минус бесконечность

RInfinity = 1e50; // плюс бесконечность

var Form1: TForm1;

implementation

uses CQueue, CSet, Math, VSet, Unit2;

{$R *.dfm}

var ConstraintList : TConstraintList; // список ограничений

VariableList : TVariableList; // список переменных

constructor TConstraint.Create(Constraint : string);