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

Самым точным и надежным с вычислительной точки зрения является представление вещественного числа

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

Пусть мы имеем ограничение

, заданное в виде отношения равенства .

Будем говорить, что отношение

на множестве непрерывных переменных справедливо для множества значений , где каждое есть интервал, если .

Численной задачейудовлетворения ограничений (ЧЗУО) называется тройка

,

где

– конечное множество переменных ,

– функция, отображающая каждую переменную из на множество объектов произвольного типа:

Будем рассматривать

как множество объектов, отображенных из функцией . Эти объекты называются значениями переменной , а множество – областью [1].

– конечное (возможно пустое) множество ограничений на произвольном подмножестве переменных из .

Решением численной ЗУО

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

2 МЕТОДЫ РАСПРОСТРАНЕНИЯ ОГРАНИЧЕНИЙ

2.1 Алгоритм Indigo

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

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

. Если мы можем сжать границы любой переменной ограничения , мы добавляем в очередь другие ограничения, содержащие эту переменную. Продолжаем обрабатывать ограничения из очереди до тех пор, пока она не станет пустой. После того, как все ограничения были обработаны, мы получаем значения всех переменных [3].

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

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;

endproceduretighten_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)

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

Ограничения начинают обрабатываться от самого сильного к слабому. Так после обработки неравенства

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