ЦЕЛЬ. Актуальность представленных исследований определяется важностью моделирования слабо формализованных предметных областей, знания о которых разнородны, носят как количественный, так и качественный характер. С появлением технологии программирования в ограничениях появились предпосылки для унификации совместной обработки разнородных ограничений предметной области, однако, на настоящий момент обработка качественных зависимостей реализуется недостаточно эффективно. Статья посвящена разработке способов экономного представления нечисловых ограничений, а также эффективных методов их удовлетворения. Исследования направлены на ускорение процедур комбинаторного поиска при решении задач удовлетворения ограничений в слабо формализованных предметных областях. МЕТОДЫ. Предлагаемые методы развивают теорию удовлетворения ограничений в части представления и повышения эффективности совместной обработки количественных и качественных зависимостей слабо формализованной предметной области. Для представления и обработки нечисловых (качественных) ограничений предметной области предполагается использовать специализированные матрицеподобные структуры ( С - и D -системы), а рассуждения на данных структурах реализовывать в форме процедур удовлетворения ограничений. РЕЗУЛЬТАТЫ И ИХ ОБСУЖДЕНИЕ. Сформулированы две теоремы о свойствах матрицеподобных структур и следствия из них, которые в совокупности с предлагаемыми правилами редукции позволяют успешно распространять нечисловые ограничения: выявлять в пространстве поиска подпространства допустимых и недопустимых присваиваний, проверяя лишь часть значений из области определения переменной. На основе следствий из упомянутых теорем разработаны модификации известных методов распространения ограничений, обеспечивающие достижение вершинной и дуговой совместностей для случая нечисловых ограничений. Данные модификации, в отличие от большинства аналогов, позволяют эффективно редуцировать задачу CSP, даже если она изначально не была представлена посредством совокупности лишь унарных и бинарных ограничений. ВЫВОДЫ. В работе предложен комплексный подход к представлению и обработке качественных зависимостей в слабо формализованных предметных областях, позволяющий обеспечить приемлемую скорость вычислений при исследовании предметных областей со сложными многочисленными связями.
PURPOSE. The relevance of the presented studies is determined by the importance of modeling of poorly formalized subject domains, the knowledge of which is heterogeneous and has both quantitative and qualitative nature. With the advent of constraint programming technology the conditions for unifying the joint processing of heterogeneous constraints of the subject domain have emerged. However, today qualitative dependencies are not processed effectively enough. The article is devoted to the development of methods for economical representation of non-numerical constraints, as well as effective methods for their satisfaction. The research is aimed at acceleration of the combinatorial search procedures when solving constraint satisfaction problems in poorly formalized subject domains. METHODS. The methods proposed in the article develop the constraint satisfaction theory in the part of representing and improving the efficiency of joint processing of quantitative and qualitative relationships of a poorly formalized subject domain. Presentation and processing of non-numerical (qualitative) constraints of the subject domain is proposed to perform with the use of specialized matrix-like structures ( C- and D- systems). The reasoning on these structures should be implemented in the form of constraint satisfaction procedures. RESULTS AND THEIR DISCUSSION. Two theorems on the properties of matrix-like structures and their corollaries are formulated. Together with the proposed reduction rules they can successfully propagate non-numerical constraints: identify the subspaces of legal and illegal assignments in the search space by checking only a part of the values from the variable domain. Based on the corollaries of the theorems mentioned above, the modifications are developed to the known methods of constraint propagation, which provide node and arc consistency for the case of non-numerical constraints. Unlike most analogs these modifications allow the CSP to be effectively reduced, even if it was not originally represented by a set of unary and binary constraints only. CONCLUSIONS. The paper offers a complex approach to the representation and processing of qualitative dependencies in poorly formalized subject domains, which allows to provide an acceptable computational speed in the study of subject domains with complicated multiple relationships.
The authors declare that there are no conflicts of interest present.