Задачи удовлетворения ограничений (ЗУО) — это математические задачи, определяемые как набор объектов, состояние которых должно соответствовать ряду или рамок. ЗУО представляют сущности в задаче как однородную совокупность конечных ограничений над переменными, которые решаются методами . ЗУО являются предметом исследований как в области искусственного интеллекта и исследования операций, поскольку регулярность их формулировки обеспечивает общую основу для анализа и решения задач из многих, казалось бы, несвязанных семейств. , требуя комбинации эвристических методов и методов комбинаторного поиска для решения в разумные сроки. Программирование в ограничениях — это область исследований, которая главным образом фокусируется на решении такого рода задач. Кроме того, задача выполнимости булевых формул, задача выполнимости формул в теориях, смешанное целочисленное программирование и программирование на основе набора ответов — всё это области исследований, сосредоточенные на решении конкретных форм задачи удовлетворения ограничений.
Примеры задач, которые могут быть смоделированы как задача удовлетворения ограничений: Вывод типов Задача о восьми ферзях и Задача о ходе коня Задача раскраски карты Выделение частот для систем собильной связи Задача коммивояжёра Задача максимального разреза Судоку, Кроссворды, Футошики, Какуро («пересекающиеся суммы»), /, Загадка Эйнштейна и много других логических головоломок.
Эти примеры часто используются в учебных пособиях для решения задач программирования в ограничениях, программирования на основе набора ответов, выполнимости булевых формул и выполнимости формул в теориях. В общем случае задачи с ограничениями могут быть гораздо сложнее и не всегда выразимы в некоторых из этих более простых систем. Примеры из «реальной жизни» включают автоматизированное планирование, разрешение лексической многозначности, музыковедение, системы и оптимальное распределение ресурсов.
Некоторые задачи искусственного интеллекта и комбинаторной оптимизации, а также некоторые индустриальные применений, обсуждались в терминах ЗУО. К ним относятся задачи планирование, в управление воздушным движением, гражданское строительство, машиностроение, когнитивные процессы, веб-приложения, сетевая безопасность, защита персональных данных или конфиденциальности, и даже контекст осведомлённости.
Существование решения ЗУО может рассматриваться как задача разрешимости. Её можно решить, найдя решение или не найдя его после исчерпывающего поиска (стохастические алгоритмы обычно никогда не приходят к исчерпывающему заключению, в то время как направленные поиски часто это делают на достаточно малых задачах). В некоторых случаях заранее известно, что ЗУО имеет решения, благодаря другому процессу математического вывода.
Формальное определение Формально задача удовлетворения ограничений определяется как тройка , где — набор переменных, — набор областей значений этих переменных — набор ограничений. Каждая переменная может принимать значения из непустой области . Каждое ограничение , в свою очередь, является парой , где — набор из индексов, а — набор -арное отношение на соответствующем произведении областей , где произведение берётся с индексами в возрастающем порядке. Подстановка переменных — это функция из подмножества переменных в определённое множество значений в соответствующем подмножестве областей. Подстановка удовлетворяет ограничению , если значения, присвоенные переменным , удовлетворяют отношению .
Подстановка является согласованной, если она не нарушает ни одно из ограничений. Подстановка является полной, если она включает все переменные. Подстановка является решением, если она согласованная и полная.
Решение Задачи удовлетворения ограничений на конечных областях обычно решаются с помощью различных методов поиска. Наиболее распространёнными из них являются варианты поиска с возвратом, методы и локального поиска. Эти методы часто комбинируются, как, например, в методе , а современные исследования включают и другие технологии, такие как линейное программирование.
Поиск с возвратом — это рекурсивный алгоритм. Он поддерживает частичное присвоение значений переменным. Изначально все переменные не имеют значений. На каждом шаге выбирается переменная, и ей поочерёдно присваиваются все возможные значения. Для каждого значения проверяется согласованность частичного присвоения с ограничениями. В случае согласованности выполняется рекурсивный вызов. Когда все значения испробованы, алгоритм возвращается назад. В этом базовом алгоритме поиска с возвратом согласованность определяется как выполнение всех ограничений, чьи переменные уже имеют значения. Существует несколько вариантов поиска с возвратом. повышает эффективность проверки согласованности. позволяет сэкономить часть поиска, в некоторых случаях возвращаясь назад «более чем на одну переменную». выводит и сохраняет новые ограничения, которые могут быть использованы позже для избежания части поиска. также часто используется в поиске с возвратом для попытки предвидеть последствия выбора переменной или значения, тем самым иногда заранее определяя, когда подзадача является разрешимой или неразрешимой.
Техники используются для изменения задач удовлетворения ограничений. Точнее, они являются методами, обеспечивающими , которая относится к согласованности группы переменных и/или ограничений. Распространение ограничений имеет несколько применений. Во-первых, оно преобразует задачу в эквивалентную, но обычно более простую для решения. Во-вторых, оно может доказать разрешимость или неразрешимость задач. Это не гарантируется в общем случае, но всегда происходит для некоторых форм распространения ограничений и/или для определённых типов задач. Наиболее известные и используемые формы локальной согласованности — это , и . Самый популярный метод распространения ограничений — , который обеспечивает совместимость по дугам.
Методы локального поиска — это неполные алгоритмы разрешимости. Они могут найти решение задачи, но могут потерпеть неудачу, даже если задача разрешима. Они работают путём итеративного улучшения полного присвоения значений переменным. На каждом шаге изменяется значение небольшого числа переменных с общей целью увеличения числа ограничений, удовлетворяемых этим присвоением. — это алгоритм локального поиска, специфичный для ЗУО и основанный на этом принципе. На практике локальный поиск хорошо работает, когда эти изменения также зависят от случайного выбора. Была разработана интеграция поиска с локальным поиском, что привело к .
Теоретические аспекты Вычислительная сложность ЗУО также изучаются в теории сложности вычислений, и универсальной алгебре. Выяснилось, что вопросы о сложности ЗУО сводятся к важным универсально-алгебраическим вопросам о базовых алгебрах. Этот подход известен как алгебраический подход к ЗУО.
Поскольку любая вычислительная задача разрешимости полиномиально эквивалентна ЗУО с бесконечным шаблоном, общие ЗУО могут иметь произвольную сложность. В частности, существуют ЗУО, относящиеся к классу задач, существование которых было продемонстрировано при условии, что P ≠ NP.
Однако большой класс ЗУО, возникающих из естественных приложений, удовлетворяет дихотомии сложности, что означает, что каждая ЗУО в этом классе либо принадлежит P либо является NP-полной задачей. Таким образом, эти ЗУО представляют собой одно из крупнейших известных подмножеств NP, которое избегает задач. Дихотомия сложности была впервые доказана для булевых ЗУО, то есть ЗУО с двуэлементной областью и где все доступные отношения являются булевыми операторами. Этот результат был обобщён для различных классов ЗУО, в первую очередь для всех ЗУО с конечными областями. Эта гипотеза о дихотомии для конечных областей была впервые сформулирована Томасом Федером и Моше Варди, а окончательно доказана независимо Андреем Булатовым и Дмитрием Жуком в 2017 году.
Другие классы, для которых подтверждена дихотомия сложности, включают
все первого порядка , все счётного случайного графа, все первого порядка редукции класса всех C-отношений, все первого порядка редукции универсального однородного частично упорядоченного множества, все первого порядка редукции однородных неориентированных графов, все первого порядка редукции всех унарных структур, все ЗУО в классе сложности MMSNP.
Большинство классов ЗУО, которые известны как разрешимые, это те, где гиперграф ограничений имеет ограниченную древовидную ширину, или где ограничения имеют произвольную форму, но существуют эквационально нетривиальные полиморфизмы множества отношений ограничений.
Гипотеза дихотомии для бесконечных областей была сформулирована для всех ЗУО редукций конечных однородных структур, утверждающая, что ЗУО такой структуры находится в P тогда и только тогда, когда её эквационально нетривиален, и в противном случае задача является NP-трудной.
Сложность таких ЗУО, а также других обобщений, (ЗУО с оценками, кванторная ЗУО, «ЗУО с обещаниями») остаётся областью активных исследований.
Любая ЗУО может рассматриваться как задача содержания .
Функциональные классы Аналогичная ситуация наблюдается между функциональными классами и #P. Согласно обобщению существуют задачи, которые не относятся ни к FP, ни к задачам, при условии, что FP ≠ #P. Как и в случае с задачами разрешимости, задача в #ЗУО определяется набором отношений. Каждая задача принимает на вход булеву формулу, и цель состоит в вычислении количества удовлетворяющих присваиваний. Это можно дополнительно обобщить, используя большие размеры доменов и присваивая вес каждому удовлетворяющему присваиванию, а затем вычисляя сумму этих весов. Известно, что любая сложная взвешенная задача #ЗУО либо относится к FP, либо является #P-трудной.
Варианты Классическая модель задачи удовлетворения ограничений определяет модель статических, негибких ограничений. Эта жёсткая модель является недостатком, затрудняющим простое представление задач. Было предложено несколько модификаций базового определения ЗУО для адаптации модели к широкому кругу задач.
Динамические ЗУО Динамические ЗУО (ДЗУО) полезны, когда исходная формулировка задачи каким-либо образом изменяется, обычно потому, что набор рассматриваемых ограничений меняется из-за окружающей среды. ДЗУО рассматриваются как последовательность статических ЗУО, каждая из которых является преобразованием предыдущей, в которой переменные и ограничения могут быть добавлены (усиление ограничений) или удалены (ослабление ограничений). Информация, найденная в исходных формулировках задачи, может быть использована для уточнения последующих. Метод решения может быть классифицирован в соответствии со способом передачи информации: Оракулы: решения, найденные для предыдущих ЗУО в последовательности, используются как эвристики для решения текущей задачи ЗУО с нуля. Локальное исправление: каждая ЗУО рассчитывается, начиная с частичного решения предыдущей, и исправляет несогласованные ограничения с помощью локального поиска. Запись ограничений: на каждом этапе поиска определяются новые ограничения, чтобы отразить усвоение несовместимых групп решений. Эти ограничения переносятся на новые задачи ЗУО.
Гибкие ЗУО Классические ЗУО рассматривают ограничения как жёсткие, то есть они обязательны (каждое решение должно им соответствовать) и негибкие (в том смысле, что они должны быть полностью удовлетворены, иначе они полностью нарушены). Гибкие ЗУО ослабляют эти предположения, частично ослабляя ограничения и позволяя решению не соответствовать всем из них. Это похоже на предпочтения в планировании, . Некоторые типы гибких задач ЗУО включают: MAX-ЗУО, допускается нарушение некоторого количества ограничений, а качество решения измеряется количеством удовлетворённых ограничений. — это, MAX-ЗУО, в котором каждое нарушение ограничения взвешивается в соответствии с заранее определённым предпочтением. Удовлетворение ограничения с бо́льшим весом является предпочтительным.