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

<13 14 15 16 17 1819>

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.

<13 14 15 16 17 1819>

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