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

Зуенко Александр Анатольевич

2018 / Том 22, №7 (138) 2018 [ Информатика, вычислительная техника и управление ]

ЦЕЛЬ. Актуальность представленных исследований определяется важностью моделирования слабо формализованных предметных областей, знания о которых разнородны, носят как количественный, так и качественный характер. С появлением технологии программирования в ограничениях появились предпосылки для унификации совместной обработки разнородных ограничений предметной области, однако, на настоящий момент обработка качественных зависимостей реализуется недостаточно эффективно. Статья посвящена разработке способов экономного представления нечисловых ограничений, а также эффективных методов их удовлетворения. Исследования направлены на ускорение процедур комбинаторного поиска при решении задач удовлетворения ограничений в слабо формализованных предметных областях. МЕТОДЫ. Предлагаемые методы развивают теорию удовлетворения ограничений в части представления и повышения эффективности совместной обработки количественных и качественных зависимостей слабо формализованной предметной области. Для представления и обработки нечисловых (качественных) ограничений предметной области предполагается использовать специализированные матрицеподобные структуры ( С - и 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.

Файлы:

• 5._Зуенко_А.А..pdf (скачать | просмотреть) - скачано 47 раз