Курсовая работа

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

Ярошук Юлия Викторовна – студентка 4 курса специальности «Экономическая кибернетика»

Печко Елена Владимировна – преподаватель кафедры математического моделирования

Брест 2010

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

Курсовая работа состоит из двух частей.

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

Во второй части рассмотрены два алгоритма распространения ограничений Indigo и IHCS (Incremental Hierarchical Constraint Solver.

1 ОБЩИЕ СВЕДЕНИЯ ОБ ИНТЕРВАЛЬНОЙ АРИФМЕТИКЕ

1.1 Интервальная арифметика. Интервальные числа

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

Множество всех интервалов обозначим через . Элементы обычно записывают прописными буквами. Если – элемент , , то его левый и правый концы обозначаются как . Элементы называются интервальными числами.

Символы и т. п. понимаются в обычном теоретико-множественном смысле, причем обозначает не обязательно строгое включение, то есть соотношение допускает равенство интервалов. Два интервала и равны тогда и только тогда, когда .

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

Пересечение интервалов и пусто, если или, в противном случае – снова интервал.

Симметричным является интервал , у которого .

Шириной интервала называется величина

. (1.1)

Середина есть полусумма концов интервала

: . (1.2)

Абсолютная величина определяется как

. (1.3)

Наконец, . Нетрудно заметить, что , когда , причем , если и .

Расстояние между элементами вводится равенством .

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

1.2 Стандартная интервальная арифметика

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

, (1.4)

причем в случае деления .

Легко проверить, что определение (1.4) эквивалентно соотношениям

, (1.5)

, (1.6)

, (1.7)

. (1.8)

Заметим, что операцию вычитания можно выразить через сложение и умножение, положив и .

В зависимости от знака чисел правило (1.7) для интервального умножения будет выглядеть так (мы полагаем ):

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. .

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

Если и – вырожденные интервалы, то равенства (1.5) – (1.8) совпадают с обычными арифметическими операциями над вещественными числами. Таким образом, интервальное число есть обобщение вещественного числа, а интервальная арифметика – обобщение вещественной.

Из определения (1.4) непосредственно видно, что интервальные сложение и умножение ассоциативны и коммутативны, иначе говоря, для имеют место равенства

,

.

Роль нуля и единицы играют обычные 0 и 1, которые, как отмечалось, отождествляются с вырожденными интервалами и . Другими словами,

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

Равенство (1.4) (как и (1.5) – (1.8)) показывает, что если один из операндов является невырожденным интервалом, то результат арифметической операции также невырожденный интервал. Исключение составляет умножение на . Отсюда, в частности, следует, что для невырожденного интервала не существует обратных по сложению и умножению элементов, так как если , то должны быть в силу сказанного вырожденными,
т.е вычитание не обратно сложению, деление не обратно умножению. Значит, , когда . Понятно, однако, что всегда .

1.3 Интервальная арифметика с нестандартными вычитанием и делением

Нестандартные операции вычитания и деления , определенные для элементов , вводятся следующим образом:

,

,

Обозначим и укажем некоторые свойства, связанные с операциями и .

1. .

2. , , для (по определению ).

3. Из равенства не следует ; например, .

4. Для уравнение имеет единственное решение: .

5. Для уравнение имеет решение . В случае у этого уравнения есть еще одно решение: .

6. Уравнение имеет решение . Если , то существует еще одно решение: .

7. тогда и только тогда, когда или , или .

8. .

9. , для (по определению ).

10. Из равенства не следует ; например, .

Определим для элементов функцию следующим образом:

.

11. Уравнение при имеет решение тогда и только тогда, когда , которое выражается в виде .

12. Уравнение при имеет решение . Если , то существует еще одно решение: .

13. Уравнение имеет решение . Если , то имеется еще одно решение: .

14. тогда и только тогда, когда или , или .

1.4 Теоретические аспекты методов распространения ограничений

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

Самым точным и надежным с вычислительной точки зрения является представление вещественного числа интервалом . Таким образом, мы аппроксимируем бесконечное множество значений конечным, заменяя одним элементом бесконечное множество значений, лежащих в данном интервале и не являющихся элементами из 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;

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. Должна быть достигнута глобальная совместимость нового хранилища активных ограничений, повторно выполняя при этом как можно меньше работы.

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

Ограничения, смягченные в предыдущих конфликтах, следует пересмотреть на предмет реактивации, если некоторые ограничения, вовлеченные в те конфликты, сейчас смягчены. Это даст шанс, что новое смягчение также разрешит эти ранние конфликты, следовательно, позволяет ранее смягченным ограничениям стать активными. За осуществление обратного правила отвечает функция 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;

Procedure ShowSteps;

var NewString : string;

i : integer;

IsNew : boolean;

begin

IsNew:=True;

t:=GetPVariable(V);

NewString:=t.VarName + ': [' + FloatToStr(t.LBound) + '; '
+ FloatToStr(t.RBound) + ']';

for i:=0 to Form1.ListBox1.Count-1 do

if Form1.ListBox1.Items.Strings[i] = NewString then

begin

IsNew:=False;

break;

end;

if IsNew then

Form1.ListBox1.Items.Append(NewString);

end;

begin

if (CType = 'l') or (CType = 'm') then

Result:=TightenBoundsForNoEqual(V)

else

if Prior <> 'w' then

Result:=TightenBoundsForEqual(V)

else

Result:=TightenBoundsForWeakEqual(V);

ShowSteps;

end;

Function TConstraint.IsElemInVars(Elem : string) : boolean;

var temp : boolean;

i : integer;

begin

temp:=False;

for i:=0 to VarCount-1 do

if Variables[i] = Elem then

begin

temp:=true;

break;

end;

Result:=temp;

end;

Procedure TVariable.SetBounds(pLBound, pRBound : extended);

begin

LBound:=pLBound;

RBound:=pRBound;

end;

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

begin

VarName:=pName;

LBound:=pLBound;

RBound:=pRBound;

end;

destructor TVariable.Free;

begin

end;

Procedure GetConstraintList(FileName : string; var List : TConstraintList);

var i : integer;

s : string;

begin

List.Count:=Form1.Memo1.Lines.Count;

SetLength(List.List,List.Count);

for i:=0 to List.Count-1 do

begin

s:=Form1.Memo1.Lines.Strings[i];

List.List[i]:=TConstraint.Create(s);

end;

end;

Procedure GetVariablesList(CList : TConstraintList; var VarList : TVariableList);

var i,j : integer;

Function IsNewVar : boolean;

var k : integer;

temp : boolean;

begin

temp:=true;

for k:=0 to VarList.Count-1 do

if VarList.List[k].VarName = CList.List[i].Variables[j] then

temp:=False;

Result:=temp;

end;

begin

VarList.Count:=CList.List[0].VarCount;

SetLength(VarList.List,VarList.Count+1);

for i:=0 to VarList.Count - 1 do

VarList.List[i]:=TVariable.Create(CList.List[0].Variables[i],

LInfinity,RInfinity);

for i:=1 to CList.Count-1 do

for j:=0 to CList.List[i].VarCount-1 do

if IsNewVar then

begin

inc(VarList.Count);

SetLength(VarList.List,VarList.Count);

VarList.List[VarList.Count-1]:=
Variable.Create(CList.List[i].Variables[j],LInfinity,RInfinity);

end;

end;

Procedure TightenBounds(cn : TConstraint; var Queue : TQueueOfC;

var TightVariables : TSetOfV; var ActiveConstraints : TSetOfC);

var i,j : integer;

TightenFlag : boolean;

v : string;

begin

for i:=0 to cn.VarCount-1 do

if not TightVariables.IsElemIn(cn.Variables[i]) then

begin

v:=cn.Variables[i];

TightenFlag:=cn.TightenBoundsFor(v);

TightVariables.Add(GetPVariable(v));

if TightenFlag then

for j:=0 to ConstraintList.Count-1 do

begin

if ConstraintList.List[j].IsElemInVars(v) then

if (ActiveConstraints.IsElemIn(ConstraintList.List[j]))

and (not Queue.IsElemIn(ConstraintList.List[j])) then

Queue.Add(ConstraintList.List[j]);

end;

end;

end;

Procedure CheckConstraints(cn : TConstraint; var ActiveConstraints : TSetOfC);

var i : integer;

temp : boolean;

v : TVariable;

begin

temp:=False; // не все переменные имеют уникальные значения

for i:=0 to cn.VarCount-1 do

begin

v:=GetPVariable(cn.Variables[i]);

if v.LBound <> v.RBound then

temp:=True;

end;

if temp then

ActiveConstraints.Add(cn)

else

ActiveConstraints.Delete(cn);

if cn.VarCount = 1 then

ActiveConstraints.Delete(cn);

end;

procedure TForm1.Button1Click(Sender: TObject);

var Queue : TQueueOfC; // очередь ограничений

ActiveConstraints : TSetOfC; // активное множество ограничений

TightVariables : TSetOfV; //

cn : TConstraint;

i : integer;

Procedure ShowDecision;

var i : integer;

begin

for i:=0 to VariableList.Count-1 do

Form2.ListBox2.Items.Append(VariableList.List[i].VarName + ' = '
+ FloatToStr(VariableList.List[i].LBound));

end;

begin

ListBox1.Clear;

Form2.Show;

Form2.ListBox2.Clear;

GetConstraintList('Data.txt',ConstraintList);

GetVariablesList(ConstraintList,VariableList);

ActiveConstraints:=TSetOfC.Create;

for i:=0 to ConstraintList.Count-1 do

begin

TightVariables:=TSetOfV.Create;

Queue:=TQueueOfC.Create;

Queue.Add(ConstraintList.List[i]);

while not Queue.IsEmpty do

begin

cn:=Queue.Front;

TightenBounds(cn,Queue,TightVariables,ActiveConstraints);

CheckConstraints(cn,ActiveConstraints);

Queue.Dequeue;

end;

end;

ShowDecision;

end;

end.

{=============================================================================}

unit Unit2;

interface

uses

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

Dialogs, StdCtrls;

type

TForm2 = class(TForm)

GroupBox2: TGroupBox;

ListBox2: TListBox;

private { Private declarations }

public { Public declarations }

end;

var

Form2: TForm2;

implementation

{$R *.dfm}

end.

{=============================================================================}

unit MyFunctions;

interface

type

TSArray = array of string;

Procedure GetLeftAndRightParts(var Constraint : string;

var LPart, RPart: string; var Prior, CType: char);

Procedure GetVarList(Constraint : string; var Variables : TSArray;

var VarCount: integer; var SVar: string);

implementation

// ВЫРЕЗАЕМ ЛЕВУЮ И ПРАВУЮ ЧАСТЬ В ОГРАНИЧЕНИИ, ОПРЕДЕЛЯЕМ ПРИОРИТЕТ И ТИП

Procedure GetLeftAndRightParts(var Constraint : string;

var LPart, RPart: string; var Prior, CType: char);

var i : integer;

begin

Prior:=Constraint[1]; // приоритет

Delete(Constraint,1,2);

i:=pos('<=',Constraint);

if i>0 then

begin

CType:='l';

LPart:=Copy(Constraint,1,i-1);

RPart:=Copy(Constraint,i+2,Length(Constraint)-i-1);

end

else

begin

i:=pos('>=',Constraint);

if i>0 then

begin

CType:='m';

LPart:=Copy(Constraint,1,i-1);

RPart:=Copy(Constraint,i+2,Length(Constraint)-i-1);

end

else

begin

i:=pos('=',Constraint);

CType:='e';

LPart:=Copy(Constraint,1,i-1);

RPart:=Copy(Constraint,i+1,Length(Constraint)-i);

end;

end;

end;

// ПОЛУЧАЕМ СПИСОК ПЕРЕМЕННЫХ

Procedure GetVarList(Constraint : string; var Variables : TSArray;

var VarCount: integer; var SVar: string);

var NumbersSet : set of char;

s : string;

LengthS, i, j : integer;

begin

NumbersSet:=['0'..'9','<','=','>','-','+','*',' '];

VarCount:=0;

s:=Constraint + '+';

lengthS:=length(s);

i:=1;

while i

begin

while (s[i] in NumbersSet) and (i

inc(i);

j:=i;

while (not(s[i] in NumbersSet)) and (i

inc(i);

if i > j then

begin

inc(VarCount);

SetLength(Variables,VarCount);

Variables[VarCount-1]:=Copy(s,j,i-j);

end;

end;

SVar:='';

for i:=0 to VarCount-1 do

SVar:=SVar + ',' + Variables[i];

Delete(SVar,1,1);

end;

end.

{=============================================================================}

unit CSet;

interface

uses Unit1;

type

TSetOfC = class

Count : integer;

Constraints : array of TConstraint;

constructor Create;

destructor Free;

procedure Add(Elem : TConstraint);

function IsElemIn(Elem : TConstraint) : boolean;

procedure Delete(cn : TConstraint);

end;

implementation

Constructor TSetOfC.Create;

begin

Count:=0;

end;

Destructor TSetOfC.Free;

begin

Count:=0;

Constraints:=nil;

end;

Procedure TSetOfC.Add(Elem : TConstraint);

begin

inc(Count);

SetLength(Constraints,Count);

Constraints[Count-1]:=Elem;

end;

Function TSetOfC.IsElemIn(Elem : TConstraint) : boolean;

var i : integer;

temp : boolean;

begin

temp:=False;

for i:=0 to Count-1 do

if Constraints[i] = Elem then

begin

temp:=True;

break;

end;

Result:=temp;

end;

Procedure TSetOfC.Delete(cn : TConstraint);

var i,j : integer;

begin

for i:=0 to Count-1 do

if cn = Constraints[i] then

begin

for j:=i to Count-2 do

Constraints[j]:=Constraints[j+1];

Dec(Count);

SetLength(Constraints,Count);

break;

end;

end;

end.

{=============================================================================}

unit CQueue;

interface

uses Unit1;

type

TQueueOfC = class

Count : integer;

Constraints : array of TConstraint;

constructor Create;

destructor Free;

procedure Add(Elem : TConstraint);

procedure Dequeue;

function IsEmpty : boolean;

function Front : TConstraint;

function IsElemIn(Elem : TConstraint) : boolean;

end;

implementation

Constructor TQueueOfC.Create;

begin

Count:=0;

end;

Destructor TQueueOfC.Free;

begin

Count:=0;

Constraints:=nil;

end;

Procedure TQueueOfC.Add(Elem : TConstraint);

begin

inc(Count);

SetLength(Constraints,Count);

Constraints[Count-1]:=Elem;

end;

Procedure TQueueOfC.Dequeue;

var i : integer;

begin

for i:=0 to Count-2 do

Constraints[i]:=Constraints[i+1];

dec(Count);

SetLength(Constraints,Count);

end;

Function TQueueOfC.IsEmpty : boolean;

begin

if Count = 0 then

Result:=True

else

Result:=False;

end;

Function TQueueOfC.Front : TConstraint;

begin

Result:=Constraints[0];

end;

Function TQueueOfC.IsElemIn(Elem : TConstraint) : boolean;

var i : integer;

temp : boolean;

begin

temp:=False;

for i:=0 to Count-1 do

if Constraints[i] = Elem then

begin

temp:=True;

break;

end;

Result:=temp;

end;

end.

{=============================================================================}

unit VSet;

interface

uses Unit1;

type

TSetOfV = class

Count : integer;

Variables : array of TVariable;

constructor Create;

destructor Free;

procedure Add(Elem : TVariable);

function IsElemIn(v : string) : boolean;

end;

implementation

Constructor TSetOfV.Create;

begin

Count:=0;

end;

Destructor TSetOfV.Free;

begin

Count:=0;

Variables:=nil;

end;

Procedure TSetOfV.Add(Elem : TVariable);

begin

inc(Count);

SetLength(Variables,Count);

Variables[Count-1]:=Elem;

end;

function TSetOfV.IsElemIn(v : string) : boolean;

var i : integer;

temp : boolean;

begin

temp:=False;

for i:=0 to Count-1 do

begin

if Variables[i].VarName = v then

temp:=True;

break;

end;

Result:=temp;

end;

end.