Глоссарий ИИ
Полный словарь искусственного интеллекта
Программирование в ограничениях
Декларативная парадигма программирования, где отношения между переменными выражаются в виде ограничений, а система автоматически находит удовлетворительные решения.
CSP (Задача удовлетворения ограничений)
Математическая задача, определяемая набором переменных, их областями определения и набором ограничений, связывающих эти переменные, целью которой является нахождение допустимого назначения.
Область определения
Конечное или бесконечное множество возможных значений, которые переменная решения может принимать в задаче удовлетворения ограничений.
Ограничение
Логическое или математическое отношение, ограничивающее возможные комбинации значений для подмножества переменных в задаче CSP.
Узловая согласованность
Свойство, согласно которому каждое значение в области определения переменной индивидуально удовлетворяет всем унарным ограничениям, связанным с этой переменной.
Дуговая согласованность
Свойство, гарантирующее, что для каждого значения переменной существует по крайней мере одно совместимое значение в области определения каждой соседней переменной согласно бинарным ограничениям.
Путевая согласованность
Расширение дуговой согласованности, обеспечивающее совместимость назначений для любого пути переменных в графе ограничений.
Распространение ограничений
Итеративный процесс автоматического сокращения областей определения переменных путем исключения значений, которые локально нарушают ограничения задачи.
Прямая проверка
Техника упреждающего отсечения, которая при назначении переменной немедленно проверяет и корректирует домены еще не назначенных переменных.
Эвристика переменных
Стратегия упорядочивания переменных по таким критериям, как наименьший оставшийся домен (MRV) или максимальная степень для оптимизации поиска.
Эвристика значений
Метод выбора порядка перебора значений для заданной переменной, часто основанный на принципе наименьшего ограничения (LCV).
Локальный поиск
Итеративный подход, постепенно улучшающий полное решение путем локального изменения назначений для уменьшения количества нарушенных ограничений.
Минимальные конфликты
Алгоритм локального поиска, который случайным образом выбирает конфликтную переменную и назначает ей значение, минимизирующее количество нарушенных ограничений.
AC-3 (Алгоритм согласованности дуг 3)
Эффективный алгоритм установления согласованности дуг с использованием очереди для распространения сокращений доменов между переменными.
Глобальное ограничение
Ограничение большой арности, захватывающее сложное отношение между многими переменными, часто обрабатываемое специализированными алгоритмами распространения.
Оптимизация с ограничениями
Расширение программирования с ограничениями, интегрирующее целевую функцию для оптимизации при условии соблюдения всех ограничений.
Логическое программирование с ограничениями
Парадигма, объединяющая логическое программирование и решение ограничений, позволяющая решать задачи в непрерывных или дискретных областях.
Система решения ограничений
Алгоритмический механизм, реализующий механизмы распространения, поиска и вывода, необходимые для автоматического решения проблем CSP.