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

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

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

Журнал: Онтология проектирования @ontology-of-designing

Рубрика: Методы и технологии принятия решений

Статья в выпуске: 4 (42) т.11, 2021 года.

Бесплатный доступ

В рамках технологии программирования в ограничениях широко применяются табличные ограничения: обычные таблицы, compressed -таблицы, smart -таблицы, сегментированные таблицы и т.п. С их помощью могут быть представлены любые другие виды ограничений, а алгоритмы распространения табличных ограничений (логического вывода на табличных ограничениях) позволяют отфильтровывать «лишние» значения из доменов переменных, обладая при этом низкой вычислительной сложностью. В предыдущих исследованиях автора было предложено smart -таблицы подразделять на структуры С - и D -типов. Общепринятая методология решения задач удовлетворения ограничений заключается в совместном применении методов распространения ограничений и методов поиска в глубину с возвратами. В настоящем исследовании предлагается интегрировать методы поиска в ширину с авторским методом распространения табличных ограничений. Smart -таблицы D -типа предлагается представлять как соединение нескольких ортогонализованных smart -таблиц С -типа. Шаг поиска заключается в выборе пары smart -таблиц С -типа для соединения и последующем распространении ограничений. Для определения порядка соединения ортогонализованных smart -таблиц на каждом шаге поиска используется специализированная эвристика, которая обеспечивает сокращение пространства поиска с учётом дальнейших вычислений. При распространении ограничений ускорение процесса вычислений достигается за счёт применения разработанных правил редукции для случая smart -таблиц C -типа. Разработанный гибридный метод позволяет отыскивать все решения задач удовлетворения ограничений, моделируемых с помощью одной или нескольких smart -таблиц D -типа, без разложения табличных ограничений в элементарные кортежи.

Еще

Программирование в ограничениях, smart-таблицы, поиск в ширину, распространение ограничений, задача удовлетворения ограничений

Короткий адрес: https://sciup.org/170191753

IDR: 170191753   |   DOI: 10.18287/2223-9537-2021-11-4-521-532

Список литературы Интеграция методов поиска в ширину и логического вывода для удовлетворения табличных ограничений

  • Russel, S. Artificial Intelligence: A Modern Approach. 3rd edition / S. Russel, P. Norvig. - Prentice Hall, 2010. -1132 p.
  • Mackworth, A. Consistency in networks of relations / A. Mackworth // Artificial Intelligence. - 1977. - 8(1). -P. 99-118. DOI: 10.1016/0004-3702(77)90007-8.
  • Bartak, R. Constraint Programming: In Pursuit of the Holy Grail / R. Bartak // Proceedings of the Week of Doctoral Students (WDS99), Part IV. - Prague: MatFyzPress, 1999. P.555-564.
  • Charlier, B. Automatic Synthesis of Smart Table Constraints by Abstraction of Table Constraints / B. Charlier, M. Khong, C. Lecoutre, Y. Deville // Proceedings of IJCAI 2017. 2017. P. 681-687. DOI: https://doi.org/10.24963/ijcai.2017/95.
  • Audemard, G. Segmented Tables: An Efficient Modeling Tool for Constraint Reasoning / G. Audemard, C. Lecoutre, M. Maamar // Proceedings of ECAI 2020. 2020. P.315-322.
  • Yap, R. Generalized Arc Consistency Algorithms for Table Constraints: A Summary of Algorithmic Ideas / R. Yap, W. Wang // Proceedings of AAAI 2020. 2020. P.13590-13597.
  • DOI: https://doi.org/10.1609/aaai.v34i09.7086.
  • Perez, G. Improving GAC-4 for table and MDD constraints / G. Perez, J.C. Regin // CP 2014. LNCS. 2014. 8656. P.606-621. DOI: http://dx.doi.org/10.1007/978-3-319-10428-7_44.
  • Verhaeghe, H. Extending compact-table to negative and short tables / H. Verhaeghe, C. Lecoutre, P. Schaus // Proceedings of AAAI 17. 2017. P.3951-3957. DOI: https://dl.acm.org/doi/abs/10.5555/3298023.3298142.
  • Ingmar, L. Making Compact-Table Compact / L. Ingmar, C. Schulte // Proceedings of CP 2018, Lecture Notes in Computer Science. 2018. Vol.11008. P.210-218. DOI: https://doi.org/10.1007/978-3-319-98334-9_14.
  • Cheng, K. An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints / K. Cheng, R. Yap // Constraints. 2010. 15(2). P.265-304. DOI: http://dx.doi.org/10.1007/s10601-009-9087-y.
  • Jefferson, C. Extending simple tabular reduction with short supports / C. Jefferson, P. Nightingale // Proceedings of IJCAI 2013, 2013. P.573-579.
  • Mairy, J. The Smart Table Constraint / J. Mairy, Y. Deville, C. Lecoutre // In: Michel, L. (eds.) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015. Lecture Notes in Computer Science. - Springer. Cham, 2015. Vol.9075. P.271-287.
  • Verhaeghe, H. Extending Compact-Table to Basic Smart Tables. Principles and Practice of Constraint Programming / H. Verhaeghe, C. Lecoutre, Y. Deville, P. Schaus // CP 2017, Lecture Notes in Computer Science. 2017. 10416. P.297-307. DOI: http://dx.doi.org/10.1007/978-3-319-66158-2_19.
  • Schneider, A. PW-CT: Extending Compact-Table to Enforce Pairwise Consistency on Table Constraints / A. Schneider, B. Choueiry // CP 2018, Lecture Notes in Computer Science. 2018. 11008. P.345-361. DOI: https://doi.org/10.1007/978-3-319-98334-9_23.
  • Zuenko, A. Development of n-tuple algebra for logical analysis of databases with the use of two-place predicates / A. Zuenko, A. Fridman // Journal of Computer and Systems Sciences International. 2009. Vol.48(2). P.254-261. DOI: http://dx.doi.org/10.1134/S1064230709020099.
  • Zuenko, A. Local Search in Solution of Constraint Satisfaction Problems Represented by Non-Numerical Matrices / A. Zuenko // Proceedings of the 2nd International Conference on Computer Science and Application Engineering (CSAE '18) 2018. 45. DOI: 10.1145/3207677.3277959.
  • Зуенко А.А. Компактное представление ограничений на основе новой интерпретации понятия «кортеж многоместного отношения» / А.А. Зуенко // Онтология проектирования. 2020. Т.10. №4(38). С.503-515. DOI: 10.18287/2223-9537-2020-10-4-503-515.
  • Moller, G. On the Technology of Array-Based Logic. / G. M0ller // Ph. D. thesis. - 1995. -http://www.arraytechnology.com/documents/lic.pdf
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp