Современные программные системы программирования в ограничениях.
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; просмотров: 1565;
Поиск по сайту
Узнать еще
- Cимпатическая нервная система. Центральный и периферический отдел симпатической нервной системы.
- I.2. Антигены системы АВ0. Генетика. Структура
- I.2.1 ПЕРВЫЙ ЗАКОН НЬЮТОНА. ИНЕРЦИАЛЬНЫЕ СИСТЕМЫ ОТСЧЁТА.
- I.2.1 ПОЛНАЯ И ВНУТРЕННЯЯ ЭНЕРГИЯ СИСТЕМЫ. ТЕПЛОТА И РАБОТА
- I.3. Антитела системы АВ0
- I.5.4 НЕИНЕРЦИАЛЬНЫЕ СИСТЕМЫ ОТСЧЁТА. СИЛЫ ИНЕРЦИИ
- II. ЭЛЕКТРИЧЕСКИЙ ДИПОЛЬ. ДИПОЛЬНЫЙ МОМЕНТ СИСТЕМЫ ЭЛЕКТРИЧЕСКИХ ЗАРЯДОВ
- III. Избирательные системы.
Публикации по технике и механике
Публикации по биологии
Публикации по информатике
Публикации по строительству
Публикации по физике
Публикации по химии
Публикации по электронике
Публикации по искусству
Публикации по истории
Публикации по медицине
