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

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

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

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

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

     В данной системе ограничений первых два неравенства являются строгими, а вторые два – слабыми. На первом шаге первое сильное ограничение помещается в хранилище . Затем оно попадает в , где проверяются значения параметров и . , тогда по правилу разности интервалов получим , далее находим пересечение . Таким образом, получили новые границы : . Аналогично для получаем .

     На  втором шаге из в попадает второе ограничение . Попробуем удовлетворить его. По правилу умножения и разности интервалов: . Как видно это неравенство не удовлетворяется, поэтому оно перемещается в хранилище .

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

 

ЗАКЛЮЧЕНИЕ

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

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

      Для решения задач распространения  ограничений существует различное  множество алгоритмов. В курсовой работе были рассмотрены два из них: алгоритм распространения ограничений Indigo и IHCS (Incremental Hierarchical Constraint Solver). Алгоритм 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);

 var SLPart, SRPart : string;

    SVar : string;

begin

  GetLeftAndRightParts(Constraint,SLPart,SRPart,Prior,CType);

  GetVarList(Constraint,Variables,VarCount,SVar);

  LPart:=TMathParser.create;

  RPart:=TMathParser.create;

  LPart.Translate(SLPart,SVar);

  RPart.Translate(SRPart,SVar);

end; 

destructor TConstraint.Free;

begin

  VarCount:=0;

  Variables:=nil;

  LPart.Free;

  RPart.Free;

end; 

// возвращает указатель на переменную с именем Name

Function GetPVariable(Name : string) : TVariable;

 var i : integer;

  begin

  i:=0;

  while VariableList.List[i].VarName <> Name do

  inc(i);

  Result:=VariableList.List[i];

end; 

Function Svertka(var OldL, OldR: extended; NewL, NewR: extended): boolean;

 var tempL, tempR : extended;

  begin

  tempL:=OldL;

  tempR:=OldR; 

  if NewL <= NewR then

     begin

         if NewR < OldL then

             OldR:=OldL

         else

         if OldR < NewL then

             OldL:=OldR                     // свертка

         else

             begin

                OldL:=max(OldL,NewL);

                 OldR:=min(OldR,NewR);

             end;

  end; 

  if (tempL <> OldL) or (tempR <> OldR) then

   Result:=true

  else

   Result:=false;

end; 

// СЖАТИЕ ПЕРЕМЕННЫХ ДЛЯ РАВЕНСТВА

Function TConstraint.TightenBoundsForEqual(V : string) : boolean;

 type ArrayOfE = array of extended;

 var Number : integer; // номер переменной v в списке переменных

    i : integer;

    NumberArray : ArrayOfE;

    IndexMassiv : ArrayOfE;

    Svob : extended; // свободный член

    PVar,tempP : TVariable;

    tempLBound, tempRBound, Coef : extended; 

    Function FillArray(Place : integer; Chislo : integer) : ArrayOfE;

    var i : integer;

     begin

      for i:=0 to VarCount-1 do

       NumberArray[i]:=0;

      NumberArray[Place]:=Chislo;

      Result:=NumberArray;

     end;

begin

  Number:=0;

  while Variables[Number] <> V do

   inc(Number);

  SetLength(NumberArray,VarCount);

  SetLength(IndexMassiv,VarCount);     // получаем коэффициенты

  for i:=0 to VarCount-1 do

   IndexMassiv[i]:=LPart.Get(FillArray(i,1)) - LPart.Get(FillArray(i,0)) -  
   RPart.Get(FillArray(i,1)) + RPart.Get(FillArray(i,0));

  Svob:=LPart.Get(FillArray(0,0)) - RPart.Get(FillArray(0,0));

  if IndexMassiv[Number] < 0 then

   begin

    for i:=0 to VarCount-1 do

     IndexMassiv[i]:=-IndexMassiv[i];

    Svob:=-Svob;

   end;

  Coef:=IndexMassiv[Number]; 

  PVar:=GetPVariable(V);

  tempLBound:=-Svob/Coef;

  tempRBound:=-Svob/Coef;

  for i:=0 to VarCount-1 do

   if i <> Number then

    begin

     tempP:=GetPVariable(Variables[i]);

     if IndexMassiv[i] > 0 then

      begin

       tempLBound:=tempLBound - IndexMassiv[i]*tempP.RBound/coef;

       tempRBound:=tempRBound - IndexMassiv[i]*tempP.LBound/coef;

      end

     else

      begin

       tempLBound:=tempLBound - IndexMassiv[i]*tempP.LBound/coef;

       tempRBound:=tempRBound - IndexMassiv[i]*tempP.RBound/coef;

      end;

    end;

  Result:=Svertka(PVar.LBound,PVar.RBound,tempLBound,tempRBound);

end; 

//   СЖАТИЕ  ПЕРЕМЕННЫХ ДЛЯ НЕРАВЕНСТВА

Function TConstraint.TightenBoundsForNoEqual(V : string) : boolean;

 var PVar : TVariable;

  begin

  PVar:=GetPVariable(V);

  if CType = 'l' then

   PVar.RBound:=RPart.Get([1])

  else

   PVar.LBound:=RPart.Get([1]);

  Result:=True;

end; 
 

//  СЖАТИЕ ПЕРЕМЕННЫХ  ДЛЯ СЛАБЫХ РАВЕНСТВ

 Function TConstraint.TightenBoundsForWeakEqual(V : string) : boolean;

  var PVar : TVariable;

   begin

    PVar:=GetPVariable(V);

    Result:=Svertka(PVar.LBound,PVar.RBound,RPart.Get([1]), 
             RPart.Get([1]));

end; 

// СЖАТИЕ ПЕРЕМЕННЫХ

 Function TConstraint.TightenBoundsFor(V : string) : boolean;

  var t : TVariable;