Современные программные системы программирования в ограничениях.


CHIP был первым языком ЛПО, использующим рас­пространение ограничений. Другими примерами систем ЛПО могут служить библиотеки поддержки ограничений ILOG и COSYTEC, а также языки логического про­граммирования в ограничениях Prolog III, Prolog IV, CLP(R), ECLiPSe, CIAO, clp(fd).

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

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

Ниже приведена программа на языке Prolog, решающая классический

кроссворд SEND+MORE=MONEY:

 

 

Интерпретатор создает переменную для каждой буквы кроссворда. Символ :: используется для задания доменов этих переменных, так что они принимают множество значений . Ограничения S\#=0 и M\#=0 означают, что эти переменные не могут принимать значение 0.

При оценке интерпретатором этих ограничений он уменьшает домены этих двух переменных, удаляя значение 0 из них. Затем рассматривается и запоминается ограничение all-different(Digits).

Последнее алгебраическое ограничение выражает тот факт, что цифры, присвоенные буквам, должны быть такими, чтобы “SEND+MORE=MONEY” выполнялось при замене каждой буквы на соответствующую ей цифру.

Языки программирования в ограничениях постепенно расширяли диа­пазон типов решающих переменных. Например, язык Eclipse поддерживает решающие переменные, элементы доменов которых являются множествами; аналогично F поддерживает функции, ESRAпод­держивает отношения и функции, а NP-Spec поддерживает множества, пере­становки, разбиения и целые функции. Усиление абстракции позволяет поль­зователю избежать поиска дополнительных усилий при моделировании, пе­редавая это все компилятору. ESSENCE сделал большой скачок в этом на­правлении, обеспечивая более широкий диапазон типов, чем это было в предшествующих языках и, что уникально, конструкторы типов, которые мо­гут быть как угодно вложенными.

Zinc[21] ‑ это новый язык спецификаций, использующий, как и ESSENCE}, вложенные конструкторы типов, но, кроме того, в отличие от ESSENCE, имеет возможность определять предикаты.

Кроме ESSENCE, известны лишь три языка программирования в огра­ничениях с подобными возможностями: ESRA, F и LOCALIZER.

Язык Alloy[22] позволяет избежать некоторых недостатков языка Z путем ограничивания его до логики первого порядка. Alloy дает естественный и выразительный способ спецификации задач в тер­минах отношений и атомов и отображает эти спецификации в эффективные модели выполнимости SAT.

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

 


[1] Сараев А. Д., Щербина О. А. Системный анализ и современные информационные технологии // Труды Крымской академии наук. ‑ Симферополь: СОНАТ. ‑ 2006. ‑ С. 47-59.

[2] Montanari U. Networks of constraints: Fundamental properties and applications to picture processing // Information Sciences. ‑ 1974. ‑ 7(2). ‑ P. 95-132.

[3] Allen J.F. Maintaining knowledge about temporal intervals // Comm. ACM. ‑ 1983. ‑ 26. ‑ P.832-843.

[4] По оценке Bartak (1999), вероятно, более 95% приложений УО используют конечные домены.

 

[5] Распространение ограничений описано в разделе 10.2.2.

[6] для этого может потребоваться много времени.

[7] max-cardinality ‑ максимальное количество элементов.

[8] Bitner J. R., Reingold E. M. Backtrack programming techniques // Communications of the Association for Computing Machinery. ‑ 1975. ‑ 18(11). ‑ P. 651-656.

[9] Это понятие встреча­лось под именами релаксации ограничения (constraint relaxation), фильтрую­щих алгоритмов (filtering algorithms), сужающих алгоритмов (narrowing algorithms), вывода ограничений (constraint inference), алгоритмов упрощения (simplification algorithms) и др.

[10] Mackworth A.K. Consistency in networks of relations // Artificial Intelligence. ‑ 1977. ‑ 8(1). ‑ P. 99-118.

[11] Dechter R. Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition // Artificial Intelligence. ‑ 1990. ‑ 41. ‑ P. 273-312.

[12] Even S. Graph Algorithms. ‑ Potomac: Computer Science Press, 1979.

[13] Dechter R., Pearl J. Network-based heuristics for constraint-satisfaction problems //Artificial Intelligence. ‑ 1987. ‑ 34(1). ‑ P. 1-38.

[14] Dechter R., Pearl J. Tree clustering for constraint networks // Artificial Intelligence. ‑ 1989. ‑ 38(3). ‑ P. 353-366.

[15] Tarjan R.E., Yannakakis M. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs // SIAM Journal of Computing. ‑ 1984. ‑ V. 13. ‑ P. 566_579.

[16] Dechter R., Pearl J. Tree clustering for constraint networks // Artificial Intelligence. ‑ 1989. ‑ 38(3). ‑ P. 353-366.

 

[17] Robertson N., Seymour P. D. Graph minors, ii. Algorithmic aspects of tree-width // Journal of Algorithms. ‑1986. ‑ 7(3). ‑ P. 309-322.

[18] Seidel R. A new method for solving constraint satisfaction problems // Proceedings of IJCAI-81, 1981, pp. 338-342.

[19] Laburthe F., Caseau Y. SALSA: A language for search algorithms // Proceedings of the 4h International Conference on the Principles and Practice of Constraint Programming (CP'98) (Pisa, Italy), 1998.

[20] Van Hentenryck P., Saraswat V. (eds.) Special issue on Strategic Directions on Constraint Programming // CONSTRAINTS: An International Journal. ‑ 1997. ‑ V.2, N 1.

[21] Marriott K., Rafeh R., Wallace M., de la Banda M.G., and Nethercote N. Zinc 0.1: Language and libraries. Technical report, Monash University, 2006.

[22] Jackson D. Software Abstractions: Logic, Language, and Analysis. ‑ The MIT Press, 2006.



Дата добавления: 2016-06-05; просмотров: 1552;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.