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

Аннотация

Для повышения эффективности представления и обработки качественных зависимостей предметной области в рамках технологии программирования в ограничениях, в статье предлагается использовать специализированные табличные структуры: C- и D-системы. С точки зрения технологии программирования в ограничениях данные структуры могут быть отнесены к такому классу глобальных ограничений как compressed таблицы. Впервые разработаны гибридные методы решения задач удовлетворения нечисловых ограничений, формализованных с помощью предлагаемых C- и D-систем. Отличительной чертой авторских методов является то, что они не используют стратегий поиска в глубину с возвратами, приводящих к экспоненциальному росту времени выполнения вычислительных процедур при росте размерности задачи. Первый из предложенных гибридных методов интегрирует авторские методы распространения нечисловых ограничений с существующими алгоритмами структурной декомпозиции графа ограничений. В результате декомпозиции задача разбивается на подзадачи, граф ограничений каждой из которых представляет собой дерево. В этом случае подзадачи решаются за полиномиальное время с помощью авторских алгоритмов распространения нечисловых ограничений. Метод хорошо подходит для ситуации, когда имеется серия задач с одной и той же структурой графа ограничений, например при анализе типовых запросов к хранилищам данных. Второй из разработанных гибридных методов интегрирует следующие компоненты: авторские методы распространения нечисловых ограничений для сокращения размерности пространства поиска; метод локального поиска на частичных присваиваниях для быстрого выхода из подпространств, не содержащих решение; поиск с запретами (tabu search) для избегания повторного прохождения уже исследованных состояний. Он предназначен для ситуаций, когда требуется найти решение на основе больших объемом информации, но при этом отсутствуют априорные сведения о структуре графа задачи удовлетворения ограничений.