МЕТОДЫ УСКОРЕНИЯ КОМБИНАТОРНОГО ПОИСКА НА ОСНОВЕ МАТРИЧНОГО ПРЕДСТАВЛЕНИЯ КАЧЕСТВЕННЫХ ЗАВИСИМОСТЕЙ В ЗАДАЧАХ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ

ЦЕЛЬ. Актуальность представленных исследований определяется важностью моделирования слабо формализованных предметных областей, знания о которых разнородны, носят как количественный, так и качественный характер. С появлением технологии программирования в ограничениях появились предпосылки для унификации совместной обработки разнородных ограничений предметной области, однако, на настоящий момент обработка качественных зависимостей реализуется недостаточно эффективно. Статья посвящена разработке способов экономного представления нечисловых ограничений, а также эффективных методов их удовлетворения. Исследования направлены на ускорение процедур комбинаторного поиска при решении задач удовлетворения ограничений в слабо формализованных предметных областях. МЕТОДЫ. Предлагаемые методы развивают теорию удовлетворения ограничений в части представления и повышения эффективности совместной обработки количественных и качественных зависимостей слабо формализованной предметной области. Для представления и обработки нечисловых (качественных) ограничений предметной области предполагается использовать специализированные матрицеподобные структуры ( С - и D -системы), а рассуждения на данных структурах реализовывать в форме процедур удовлетворения ограничений. РЕЗУЛЬТАТЫ И ИХ ОБСУЖДЕНИЕ. Сформулированы две теоремы о свойствах матрицеподобных структур и следствия из них, которые в совокупности с предлагаемыми правилами редукции позволяют успешно распространять нечисловые ограничения: выявлять в пространстве поиска подпространства допустимых и недопустимых присваиваний, проверяя лишь часть значений из области определения переменной. На основе следствий из упомянутых теорем разработаны модификации известных методов распространения ограничений, обеспечивающие достижение вершинной и дуговой совместностей для случая нечисловых ограничений. Данные модификации, в отличие от большинства аналогов, позволяют эффективно редуцировать задачу CSP, даже если она изначально не была представлена посредством совокупности лишь унарных и бинарных ограничений. ВЫВОДЫ. В работе предложен комплексный подход к представлению и обработке качественных зависимостей в слабо формализованных предметных областях, позволяющий обеспечить приемлемую скорость вычислений при исследовании предметных областей со сложными многочисленными связями.

теория удовлетворения ограничений, распространение ограничений, матрицеподобные структуры, нечисловые ограничения, алгоритмы достижения совместности, нечисловые ограничения над конечными доменами

1. Bartak R. Constraint Programming: In Pursuit of the Holy Grail: Proceedings of the Week of Doctoral Students (WDS99). Prague: MatFyzPress. 1999. Vol. IV. P. 555-564.

2. Russel S., Norvig P. Artificial Intelligence: A Modern Approach. 3nd ed. Pearson Education. (2010).

3. Кулик Б.А. Зуенко А.А., Фридман А.Я. Алгебраический подход к интеллектуальной обработке данных и знаний. СПб.: Изд-во Политехнического ун-та. 2010. 235 с.

4. Zakrevskij A. Integrated Model of Inductive-Deductive Inference Based on Finite Predicates and Implicative Regularities // In Diagnostic Test Approaches to Machine Learning and Commonsense Reasoning Systems. IGI Global. 2013. P. 1-12. DOI:10.4018/978-1-4666-1900-5.ch001

5. Mackworth A.K. Consistency in Networks of Relations // Artificial Intelligence. 1977. Vol. 8. No. 1. P. 99-118.

6. Mackworth A.K. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems // Artificial Intelligence. 1997. Vol. 8. P. 99-118.

7. Bessiere C. Using constraint metaknowledge to reduce arc consistency computation // Artificial Intelligence. 1994. Vol. 65. P. 179-190.

8. Régin J-C. A Filtering Algorithm for constraints of difference in CSPs. Proceedings AAAI-94. Seattle. Washington. 1994. P. 362-367.

9. Ruttkay Zs. Constraint satisfaction a survey // CWI Quarterly. 1998. Vol. 11. P. 163-214.

10. Régin J-C. Generalized arc consistency for global cardinality constraint. Proceedings of the Thirteenth National Conference on Artificial Intelligence. Portland. 1996. P. 209-215.

11. Rossi F., van Beek P. & Walsh T. Constraint Programming. In F. van Harmelen, V. Lifschitz, B. Porter (Eds.). Foundations of Artificial Intelligence. Handbook of Knowledge Representation. 2008. Vol. 3. P. 181-211.

12. Зуенко А.А. Вывод на ограничениях с применением матричного представления конечных предикатов // Искусственный интеллект и принятие решений. 2014. Вып. 3. С. 21-31.

13. Зуенко А.А., Очинская А.А. Эвристический метод удовлетворения ограничений на основе их матричного представления // Открытые семантические технологии проектирования интеллектуальных систем: материалы IV Междунар. научн.-техн. конф. (Минск, 19-21 февраля 2015 г.). Минск: Изд-во БГУИР. 2015. С. 297-302.