Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ) вып. 9/2019(10)

распространителями или алгоритмами-пропагаторами. Данные алгоритмы исключают из областей определения переменных заведомо лишние значения, то есть значения, которые не входят ни в одно из допустимых присваиваний. Завершение алгоритмов-распространителей может произойти с тремя возможными исходами. Во-первых, в результате работы алгоритмов- распространителей может быть получено решение исходной задачи CSP: все домены переменных сужаются до одноэлементных множеств. Во-вторых, может быть установлено, что область определения некоторой переменной пуста, и тогда решения соответствующей задачи CSP не существует. Наконец, алгоритмы- распространители могут остановиться, достигнув некоторой неподвижной точки, а решение задачи CSP еще не получено. В этом случае в дело вступают методы, реализующие стратегии интеллектуального поиска. Эти методы, в отличие от методов вывода, имеет существенную вычислительную сложность, поскольку сопряжены с перебором вариантов гипотез о возможных значениях тех или иных переменных. В отличие от методов динамического программирования, например метода перемножения числовых матриц (matrix multiplication method), в качестве стратегий поиска в рамках парадигмы программирования в ограничениях, в основном, используются различные варианты информированного поиска в глубину с возвратами, а также методы локального поиска. Архитектура систем программирования в ограничениях напоминает архитектуру вычислительных машин (рис. 1). В качестве своеобразной шины данных в системах программирования в ограничениях выступает так называемое хранилище ограничений, представляющее собой, список пар «переменная — перечень значений переменной, которые она может принимать на текущем этапе вывода». Аналогом центрального процессора выступает алгоритм — дирижер (управляющая подпрограмма), реализующий базовую стратегию поиска. В качестве сопрограмм выступают подпрограммы, реализующие вывод на ограничениях, — распространители ограничений. Для различных типов ограничений и типов областей определения переменных разрабатываются различные алгоритмы-распространители. В частности, для арифметических и логических ограничений целесообразно иметь различные алгоритмы- распространители, учитывающие специфику данных типов ограничений. Продолжая аналогию с архитектурой вычислительных машин, процедуры- распространители соотносятся с дополнительными устройствами (оперативная память, жесткий диск и т.п.), достаточно гибко подключаемыми через шину данных. Кроме стандартных типов ограничений и алгоритмов- распространителей, в рамках библиотек программирования в ограничениях существует возможность создания пользовательских типов ограничений и соответствующих процедур распространения. В частности, автором были введены новые типы ограничений — С- и D -системы, и созданы высокоэффективные методы рассуждений на данных структурах, которые подробно описаны ниже. 129