Некоторые примеры
Напомним, что задачи в ограничениях обычно описываются путем определения множества неизвестных переменных и зависимостей между ними. При этом процесс решения заключается в локализации областей значений переменных или в поиске значений, удовлетворяющих заданным зависимостям. Перечислим основные особенности постановки таких задач.
Спецификации ограничений в рассматриваемых задачах носят декларативный характер, исключающий явное описание способов решения задачи (в качестве исключения здесь следует указать императивные языки ограничений, на которых пользователь описывает и некоторые методики решения). Спецификации обладают свойством нейтральности по отношению к неизвестным переменным и возможным альтернативным способам выражения и пересчета их друг через друга.
Спецификации обладают также свойством аддитивности, предполагающим, что порядок задания ограничений не существенен для постановки исходной задачи, логические условия которой всегда могут быть представлены в эквивалентной конъюктивной форме. Исключение составляют так называемые иерархические системы, в которых разрешение ограничений осуществляется поэтапно в соответствии с предварительно назначенными приоритетами.
Наконец, спецификации ограничений носят неопределенный характер с точки зрения их алгоритмической разрешимости. Поскольку система ограничений может быть недоопределена или переопределена, постановка задачи в ограничениях априори не предполагает ни существования, ни единственности решения, и его поиск должен вестись с учетом всех этих обстоятельств. Обсудим перечисленные свойства в контексте постановки и решения задач в классе CLP(O).
С этой целью рассмотрим классическую математическую задачу о ферзях и приведем возможные способы ее описания и решения на языках логического, функционального и объектно-ориентированного программирования. Задача формулируется следующим образом: необходимо расставить на шахматной доске восемь ферзей так, чтобы ни один из них не оказался под боем остальных фигур. Один из вариантов решения приведен на рисунке 1.
Рис. 1. Один из вариантов решения задачи о восьми ферзях
Положение каждой фигуры на шахматной доске характеризуется парой координат x/y, каждая из которых принимает целые значения от 1 до 8 (здесь мы отступим от традиционной буквенно-цифровой нотации ходов в шахматной партии, подобной “e2-e4”, и будем использовать оператор «/» для объединения координат в один элемент списка). Тогда шахматная позиция представляется списком вида [xl/yl, x2/y2, x3/y3, x4/y4, x5/y5, x6/y6, x7/y7, x8/y8]. В этом представлении решение на рис. 1 выглядит, как [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1].
Если принять во внимание необходимость расположения ферзей на разных вертикалях (или на разных горизонталях), то представление списка можно сразу уточнить, как [l/yl, 2/y2, 3/y3, 4/y4, 5/y5, 6/y6, 7/y7, 8/y8]. Таким образом, задача сводится к определению горизонтальных (или вертикальных) координат, исключающих расположение нескольких фигур на одних и тех же линиях шахматной доски.
Обсудим, каким образом задача может быть описана и решена на языке логического программирования Prolog. Уточненный список может использоваться в качестве шаблона решения, к которому последовательно применяются правила вывода в рамках общей схемы рекурсивного программирования. Будем считать список координат согласованным, если он определяет позицию, в которой ни один из ферзей не находится под боем. Возможны два случая:
Данные условия могут быть описаны на языке Prolog в виде следующей программы (см. рис. 2).
?- шаблон( S), решение( S). решение( [ ] ). решение( [x/y | Остальные ] ) :- % Первый ферзь на поле x/y, % остальные ферзи на полях из списка Остальные решение( Остальные ), принадлежит( y, [1, 2, 3, 4, 5, 6, 7, 8] ), не_бьет( x/y | Остальные ). % Первый ферзь не бьет остальных не_бьет( x/y, [ ]). % Некого бить не_бьет( x/y, [x1/y1 | Остальные] ) :- y =\= y1, % Разные y-координаты y1 - x1 =\= y - x, % Разные диагонали y1 + x1 =\= y + x, не_бьет( x/y, Остальные). принадлежит( x, [x | L] ). принадлежит( x, [y | L] ) :- принадлежит( x, L). % Шаблон решения шаблон( [1/y1, 2/y2, 3/y3, 4/y4, 5/y5, 6/y6, 7/y7, 8/y8] ).
Рис. 2. Программа решения задачи о ферзях на языке Prolog
Обсудим возможность описания этой же задачи на языке ConstraintLisp , представляющим собой расширение стандарта ANSI Common Lisp для программирования в ограничениях. Нововведением в ConstraintLisp является набор функций, который позволяет описывать арифметические ограничения в рамках функциональной и объектно-ориентированной парадигм, поддерживаемых языком ANSI Common Lisp.
В программе на рис. 3 определяется класс Queen с двумя атрибутами x и y для задания положения фигуры на шахматной доске. Для представления шахматной позиции используется массив Сhessboard, в котором хранится восемь экземпляров класса Queen. Массив конструируется и инициализируется в результате вызова соответствующей функции make-queens. Отметим, что содержательные ограничения задачи определяются в виде вспомогательной функции constraints с формальными параметрами, соответствующими координатам анализируемых фигур. При этом фактическое назначение ограничений объектам массива Сhessboard осуществляется в теле вложенного цикла, где описанный вид ограничений применяется ко всем парам итерируемых объектов. Решение генерируется и выводится на печать при вызове специальных функций generateObjs и printArrayObjs.
;;; определение класса Queen (defclass Queen ( ) (( x :initarg :x :accessor x ) ;;; координата по горизонтали ( y :initarg :y :accessor y))) ;;; координата по вертикали ;;; основная процедура поиска решения (define Queens ( ) (let ((Chessboard ( make-queens)) ) ;;; создаем массив из восьми ферзей (cldotimes ( I 7 ) ;;; начальное значение переменной I 0 (cldotimes ( J (- 7 I )) ;;; начальное значение переменной J 0 (constraints ( x (aref Chessboard I )) ( x (aref Chessboard (+ J I 1 ))) (1+ I) (+ J I 2 )))) ( generateObjs Chessboard ) ;;; генерация решения ( printArrayObjs Chessboard ))) ;;; вывод результатов ;;; ограничения отсутствия вертикальных и диагональных атак (define constraints (x1 x2 y1 y2) (constr (/= x1 x2)) ;;; по вертикали (constr (/= (+ x1 y1 ) (+ x2 y2 ))) ;;; по главной диагонали (constr (/= (- x1 y1 ) (- x2 y2 )))) ;;; по второй диагонали ;;; создаем массив ферзей (defun make-queens ( ) (let ( (queen-array (make-array 8 ))) (dotimes (I 8 queen-array ) (setf (aref queen-array I ) (make-instance 'queen :x (make-cvar-in '((1 ,8 ))) :y (1+ I) )))))
Рис. 3. Программа решения задачи о ферзях на языке ConstraintLisp
Наконец, опишем задачу о ферзях, используя декларативный язык объектно-ориентированного моделирования UML/OCL. Для этого определим необходимые объектные типы данных и инвариантные условия на них. На диаграмме классов языка UML (см. рис. 4) представлен объектный тип Queen с соответствующими целочисленными атрибутами x и y, задающими положение фигуры на шахматной доске. В виде инвариантов контекста Queen на языке OCL описаны исходные условия задачи о ферзях. Инвариант A задает необходимое число фигур на шахматной доске. Инвариант B определяет допустимую область значений для координат фигур, ограниченных полем 8x8 клеток. Условие расположения ферзей на разных вертикалях и горизонталях выражается инвариантом C, а условие расположения ферзей на разных диагоналях — инвариантом D.
context Queen -- (A) inv: self.AllInstances()->size() = 8 -- (B) inv: self.x >= 1 and self.x = 1 and self.y forAll(q1, q2 | q1 <> q2 implies (q1.x <> q2.x and q1.y <> q2.y)) -- (D) inv: self.allInstances()->forAll(q1, q2 | q1 <> q2 implies ((q1.x – q1.y) <> (q2.x – q2.y) and (q1.x + q1.y) <> (q2.x + q2.y)))
Рис. 4. Описание задачи о ферзях в виде диаграммы классов и спецификации ограничений на языке UML/OCL
Несмотря на декларативность всех языков, использованных в примерах, спецификации на языке UML/OCL обладают большей выразительностью для моделирования данных и постановки соответствующих задач в ограничениях. Для описания задачи о ферзях потребовалось лишь структурировать данные и определить ограничения, которым они должны удовлетворять. Подобный способ исключает задание каких-либо вспомогательных методик или схем решения, присущих языкам логического и функционального программирования.
В самом деле, вычислительная модель Prolog подразумевает редукцию исходной постановки к рекурсивной или итерационной схеме поиска решений на основе определяемых пользователем правил логического вывода и целей. Заметим, что порядок определения правил и целей может существенно влиять на ход решения.
В рассмотренном примере на ConstraintLisp помимо определения объектной модели данных потребовалось явно сконструировать неизвестные переменные и для них задать схему применения ограничений. Отметим громоздкость подобного функционального способа постановки задач в ограничениях по сравнению с декларациями на UML/OCL.
