Проблема удовлетворения ограничений

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найдите источники: «Проблема удовлетворения ограничений» - новости · газеты · книги · ученый · JSTOR ( ноябрь 2014 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Задачи удовлетворения ограничений ( CSP ) - это математические вопросы, определяемые как набор объектов, состояние которых должно удовлетворять ряду ограничений или ограничений . CSP представляют сущности в проблеме как однородный набор конечных ограничений по переменным , который решается с помощью методов удовлетворения ограничений . CSP являются предметом исследований как в области искусственного интеллекта, так и в исследованиях операций , поскольку регулярность их формулировки обеспечивает общую основу для анализа и решения проблем многих, казалось бы, не связанных между собой семейств. CSP часто демонстрируют высокую сложность, требующий сочетания эвристики и комбинаторных методов поиска для решения в разумные сроки. Программирование с ограничениями (CP) - это область исследований, которая специализируется на решении подобных проблем. ^[1]^[2] Кроме того, задача логической выполнимости (SAT), теории выполнимости по модулю (SMT), смешанное целочисленное программирование (MIP) и программирование набора ответов (ASP) - все это области исследований, в которых основное внимание уделяется разрешению конкретных форм проблемы. проблема удовлетворения ограничений.

Примеры проблем, которые можно смоделировать как проблему удовлетворения ограничений, включают:

Вывод типа ^[3]^[4]
Пазл о восьми ферзях
Проблема раскраски карты
Судоку , Кроссворды , Футосики , Какуро (кросс-суммы), Нумбрикс , Хидато и многие другие логические головоломки

К ним часто прилагаются учебные пособия по решателям CP , ASP, Boolean SAT и SMT. В общем случае проблемы с ограничениями могут быть намного сложнее и не могут быть выражены в некоторых из этих более простых систем. Примеры «реальной жизни» включают автоматическое планирование , ^[5]^[6] устранение лексической неоднозначности , ^[7]^[8] музыковедение , ^[9] конфигурацию продукта ^[10] и распределение ресурсов . ^[11]

Существование решения для CSP можно рассматривать как проблему принятия решения . Это может быть решено путем поиска решения или неспособности найти решение после исчерпывающего поиска (стохастические алгоритмы обычно никогда не приходят к исчерпывающему выводу, в то время как направленный поиск часто делает, для достаточно небольших проблем). В некоторых случаях может быть известно, что у CSP есть решения заранее, с помощью какого-либо другого процесса математического вывода.

Формальное определение

Формально проблема удовлетворения ограничений определяется как тройка , где ^[12] ${\ displaystyle \ langle X, D, C \ rangle}$

$X=\{X_{1},\ldots ,X_{n}\}$ набор переменных,
$D=\{D_{1},\ldots ,D_{n}\}$ представляет собой набор их соответствующих доменов значений, и
$C=\{C_{1},\ldots ,C_{m}\}$ набор ограничений.

Каждая переменная может принимать значения в непустой области . Каждое ограничение в своей очереди является парой , где представляет собой подмножество переменных и является -ичным соотношением на соответствующем множестве областей . Оценка переменных является функцией из подмножества переменных к определенному набору значений в соответствующем множестве областей. Оценка удовлетворяет ограничению, если значения, присвоенные переменным, удовлетворяют соотношению . $X_{i}$ $D_{i}$ $C_{j}\in C$ $\langle t_{j},R_{j}\rangle$ $t_{j}\subset X$ $k$ $R_{j}$ $k$ $D_{j}$ $v$ $\langle t_{j},R_{j}\rangle$ $t_{j}$ $R_{j}$

Оценка является непротиворечивой, если она не нарушает никаких ограничений. Оценка считается полной, если она включает все переменные. Оценка - это решение, если она последовательна и полна; такая оценка, как говорят, решает проблему удовлетворения ограничений.

Решение

Проблемы удовлетворения ограничений в конечных областях обычно решаются с использованием формы поиска . Наиболее часто используемые методы - это варианты с возвратом , распространение ограничений и локальный поиск . Эти методы также часто комбинируются, как в методе VLNS , и текущие исследования включают другие технологии, такие как линейное программирование . ^[13]

Отслеживание с возвратом - это рекурсивный алгоритм. Он поддерживает частичное присвоение переменных. Изначально все переменные не присвоены. На каждом шаге выбирается переменная, и ей по очереди присваиваются все возможные значения. Для каждого значения проверяется соответствие частичного присвоения ограничениям; в случае согласованности выполняется рекурсивный вызов. Когда все значения перепробованы, алгоритм возвращается к исходному состоянию. В этом базовом алгоритме поиска с возвратом согласованность определяется как удовлетворение всех ограничений, все переменные которых присвоены. Существует несколько вариантов поиска с возвратом. Backmarking повышает эффективность проверки согласованности. Обратный прыжокпозволяет сохранить часть поиска, в некоторых случаях возвращая "более одной переменной". Изучение ограничений позволяет вывести и сохранить новые ограничения, которые впоследствии можно использовать, чтобы избежать части поиска. Прогнозирование также часто используется при отслеживании с возвратом, чтобы попытаться предвидеть последствия выбора переменной или значения, таким образом иногда определяя заранее, когда подзадача является выполнимой или невыполнимой.

Методы распространения ограничений - это методы, используемые для изменения проблемы удовлетворения ограничений. Точнее, это методы, обеспечивающие некоторую форму локальной согласованности , то есть условия, связанные с согласованностью группы переменных и / или ограничений. Распространение ограничений может использоваться по-разному. Во-первых, он превращает проблему в эквивалентную, но обычно более простую для решения. Во-вторых, это может свидетельствовать об удовлетворительности или неудовлетворенности проблем. Обычно это не гарантируется; однако это всегда происходит для некоторых форм распространения ограничений и / или для определенных типов проблем. Наиболее известно и используются формами местных консистенций являются дуги консистенции , гипер-дуговой консистенция и консистенцией пути. Самым популярным методом распространения ограничений является алгоритм AC-3 , который обеспечивает согласованность дуги.

Методы локального поиска - это алгоритмы неполной выполнимости. Они могут найти решение проблемы, но могут потерпеть неудачу, даже если проблема удовлетворительна. Они работают, итеративно улучшая полное присвоение переменных. На каждом этапе небольшое количество переменных изменяется в значении с общей целью увеличения количества ограничений, которым удовлетворяет это присвоение. Алгоритм мин-конфликты является локальным алгоритмом поиска конкретным ПСА и основан на этом принципе. На практике локальный поиск работает хорошо, когда на эти изменения также влияет случайный выбор. Была разработана интеграция поиска с локальным поиском, что привело к гибридным алгоритмам .

Теоретические аспекты

Проблемы с решением

CSP также изучаются в теории сложности вычислений и теории конечных моделей . Важный вопрос заключается в том, является ли для каждого набора отношений набор всех CSP, которые могут быть представлены с использованием только отношений, выбранных из этого набора, либо в P, либо в NP-полном . Если такая теорема о дихотомии верна, то CSP обеспечивают одно из крупнейших известных подмножеств NP, которое позволяет избежать NP-промежуточных проблем, существование которых было продемонстрировано теоремой Ладнера в предположении, что P ≠ NP . Теорема о дихотомии Шефера рассматривает случай, когда все доступные соотношенияБулевы операторы , то есть для области размера 2. Теорема Шефера о дихотомии недавно была обобщена на более широкий класс отношений. ^[14]

Большинство классов CSP, которые известны своей управляемостью, - это те, в которых гиперграф ограничений имеет ограниченную ширину дерева (и нет ограничений на набор отношений ограничений) или где ограничения имеют произвольную форму, но существуют существенно не унарные полиморфизмы ^{[ требуется разъяснение ]} набора отношений ограничений.

Каждый CSP можно также рассматривать как проблему ограничения конъюнктивного запроса . ^[15]

Функциональные проблемы

Аналогичная ситуация существует между функциональными классами FP и #P . По обобщению теоремы Ладнера также не существует проблем ни в FP, ни в # P-полных, пока FP ≠ #P. Как и в случае принятия решения, проблема в #CSP определяется набором отношений. Каждая задача принимает булеву формулу в качестве входных данных, и задача состоит в том, чтобы вычислить количество удовлетворяющих назначений. Это может быть дополнительно обобщено, используя больший размер домена и добавляя вес к каждому удовлетворяющему назначению и вычисляя сумму этих весов. Известно, что любая сложновзвешенная задача #CSP находится либо в FP, либо в # P-hard. ^[16]

Варианты

Классическая модель проблемы удовлетворения ограничений определяет модель статических, негибких ограничений. Эта жесткая модель является недостатком, который затрудняет легкое представление проблем. ^[17] Было предложено несколько модификаций основного определения CSP для адаптации модели к широкому кругу задач.

Динамические CSP

Динамические CSP ^[18] ( DCSP ) полезны, когда исходная формулировка проблемы каким-либо образом изменяется, обычно из-за того, что набор ограничений, которые необходимо учитывать, развивается из-за окружающей среды. ^[19] DCSP рассматриваются как последовательность статических CSP, каждый из которых является преобразованием предыдущего, в котором переменные и ограничения могут быть добавлены (ограничение) или удалены (ослабление). Информация, содержащаяся в первоначальных формулировках задачи, может быть использована для уточнения следующих. Метод решения можно классифицировать по способу передачи информации:

Оракулы: решение, найденное для предыдущих CSP в последовательности, используется в качестве эвристики для определения разрешения текущего CSP с нуля.
Локальное исправление: каждый CSP рассчитывается, начиная с частичного решения предыдущего и исправляя противоречивые ограничения с помощью локального поиска .
Запись ограничений: новые ограничения определяются на каждом этапе поиска, чтобы представить изучение противоречивой группы решений. Эти ограничения переносятся на новые задачи CSP.

Гибкие CSP

Классические CSP рассматривают ограничения как жесткие, что означает, что они являются императивными (каждое решение должно удовлетворять всем из них) и негибкими (в том смысле, что они должны быть полностью удовлетворены, иначе они будут полностью нарушены). Гибкие CSP ослабляют эти предположения, частично ослабляя ограничения и позволяя решению не соответствовать всем из них. Это похоже на предпочтения при планировании на основе предпочтений . Некоторые типы гибких CSP включают:

MAX-CSP, где разрешено нарушать ряд ограничений, а качество решения измеряется количеством удовлетворенных ограничений.
Взвешенный CSP , MAX-CSP, в котором каждое нарушение ограничения взвешивается в соответствии с предопределенным предпочтением. Таким образом, предпочтение отдается ограничению с большим весом.
Нечеткие ограничения модели CSP как нечеткие отношения, в которых выполнение ограничения является непрерывной функцией значений его переменных, переходя от полностью удовлетворенных к полностью нарушенным.

Децентрализованные CSP

В DCSP ^[20] каждая ограничивающая переменная рассматривается как имеющая отдельное географическое положение. На обмен информацией между переменными накладываются строгие ограничения, требующие использования полностью распределенных алгоритмов для решения проблемы удовлетворения ограничений.

Смотрите также

Составной граф ограничений
Ограниченное программирование
Декларативное программирование
Задача ограниченной оптимизации (COP)
Оптимизация распределенных ограничений
Гомоморфизм графов
Гипотеза уникальных игр
Проблема удовлетворения взвешенных ограничений (WCSP)

использованная литература

^ Lecoutre, Christophe (2013). Сети ограничений: методы и алгоритмы . Вайли. п. 26. ISBN 978-1-118-61791-5.
^ «Ограничения - включая возможность публикации в открытом доступе» . springer.com . Проверено 3 октября 2019 .
^ Чандра, Сатиш и др. « Вывод типа для статической компиляции JavaScript ». Уведомления ACM SIGPLAN 51.10 (2016): 410-429.
^ Джим, Тревор и Йенс Палсберг. « Вывод типов в системах рекурсивных типов с подтипами ». Доступно на домашней странице авторов (1999 г.).
^ Малик Галлаб; Дана Нау; Паоло Траверсо (21 мая 2004 г.). Автоматизированное планирование: теория и практика . Эльзевир. стр. 1–. ISBN 978-0-08-049051-9.
^ Удовлетворение динамических гибких ограничений и его применение в планировании искусственного интеллекта , Архивировано 6 февраля2009 г. в Wayback Machine Иэн Мигель - слайды.
^ Деметриу, Джордж К. « Устранение лексической неоднозначности с использованием обработки ограничений в Prolog (CHIP) ». Труды шестой конференции Европейского отделения Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 1993.
^ Макдональд, Мэриеллен С. и Марк С. Зайденберг. « Счета удовлетворения ограничений лексического понимания и понимания предложений ». Справочник по психолингвистике (второе издание). 2006. 581–611.
^ Маурисио Торо, Карлос Агон, Камило Руэда, Жерар Ассаяг. « GELISP: ОСНОВА ДЛЯ ПРЕДСТАВЛЕНИЯ ПРОБЛЕМ УДОВЛЕТВОРЕНИЯ МУЗЫКАЛЬНЫХ ОГРАНИЧЕНИЙ И СТРАТЕГИЙ ПОИСКА ». Журнал теоретических и прикладных информационных технологий 86 (2). 2016. 327–331.
^ Применение подхода удовлетворения ограничений для решения проблем конфигурации продукта с помощью правил конфигурации на основе количества элементов, Донг Ян и Мин Донг, Журнал интеллектуального производства, том 24, страницы 99–111 (2013)
^ Моди, Прагнеш Джей и др. « Подход динамического распределенного удовлетворения ограничений к распределению ресурсов ». Международная конференция по принципам и практике программирования ограничений. Шпрингер, Берлин, Гейдельберг, 2001.
^ Стюарт Джонатан Рассел; Питер Норвиг (2010). Искусственный интеллект: современный подход . Прентис Холл. п. Глава 6. ISBN 9780136042594.
^ Гибридная оптимизация: десять лет CPAIOR . Милано, Микела., Ван Хентенрик, Паскаль, Международная конференция по интеграции методов ИИ и ИЛИ в программировании с ограничениями для задач комбинаторной оптимизации. Нью-Йорк: Спрингер. 2011. ISBN. 9781441916440. OCLC 695387020 .CS1 maint: другие ( ссылка )
^ Бодирски, Мануэль; Пинскер, Майкл (2011). «Теорема Шефера для графов». Материалы 43-го ежегодного симпозиума по теории вычислений (STOC '11) . Ассоциация вычислительной техники . С. 655–664. arXiv : 1011.2894 . Bibcode : 2010arXiv1011.2894B . DOI : 10.1145 / 1993636.1993724 . ISBN 978-1-4503-0691-1. S2CID 47097319 .
^ Kolaitis, Phokion G .; Варди, Моше Ю. (2000). «Сдерживание конъюнктивного запроса и удовлетворение ограничений» . Журнал компьютерных и системных наук . 61 (2): 302–332. DOI : 10,1006 / jcss.2000.1713 .
^ Цай, Цзинь-И; Чен, Си (2012). «Сложность подсчета CSP с комплексными весами». Материалы Сорок четвертого ежегодного симпозиума ACM по теории вычислений (STOC '12) . С. 909–920. arXiv : 1111.2384 . DOI : 10.1145 / 2213977.2214059 . ISBN 978-1-4503-1245-5. S2CID 53245129 .
↑ Мигель, Ян (июль 2001 г.). Удовлетворение динамических гибких ограничений и его применение в планировании искусственного интеллекта (кандидатская диссертация). Школа информатики Эдинбургского университета . CiteSeerX 10.1.1.9.6733 . hdl : 1842/326 .
^ Dechter, R. и Dechter, A., Поддержание убеждений в сетях с динамическими ограничениями. Архивировано 17ноября2012 г. в Wayback Machine In Proc. AAAI-88, 37–42.
^ Повторное использование решения в задачах удовлетворения динамических ограничений , Томас Шикс
^ Даффи, КР; Leith, DJ (август 2013 г.), «Decentralized Constraint Satisfaction», IEEE / ACM Transactions on Networking, 21 (4) , 21 , стр. 1298–1308, arXiv : 1103.3240 , doi : 10.1109 / TNET.2012.2222923 , S2CID 11504393

дальнейшее чтение

Краткое введение в удовлетворение ограничений на YouTube
Стивен Минтон; Энди Филипс; Марк Д. Джонстон; Филип Лэрд (1993). «Сведение к минимуму конфликтов: эвристический метод исправления ограничений-удовлетворения и задач планирования». Журнал исследований искусственного интеллекта . 58 (1–3): 161–205. CiteSeerX 10.1.1.308.6637 . DOI : 10.1016 / 0004-3702 (92) 90007-к .
Цанг, Эдвард (1993). Основы удовлетворения ограничений . Академическая пресса. ISBN 0-12-701610-4
Чен, Хуби (декабрь 2009 г.). «Встреча логики, сложности и алгебры». ACM Computing Surveys . 42 (1): 1–32. arXiv : cs / 0611018 . DOI : 10.1145 / 1592451.1592453 . S2CID 11975818 .
Дехтер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 1-55860-890-7
Апт, Кшиштоф (2003). Принципы программирования ограничений . Издательство Кембриджского университета. ISBN 0-521-82583-0
Лекутр, Кристоф (2009). Сети ограничений: методы и алгоритмы . ISTE / Wiley. ISBN 978-1-84821-106-3
Томас Федер, Удовлетворение ограничениями: личная точка зрения , рукопись.
Архив ограничений
Тесты принудительного выполнения CSP модели RB
Тесты - XML-представление экземпляров CSP
XCSP3 - формат на основе XML, предназначенный для представления экземпляров CSP.
Распространение ограничений - Диссертация Гвидо Такка, дающая хороший обзор теории и проблем реализации

[1] Lecoutre, Christophe (2013). Сети ограничений: методы и алгоритмы . Вайли. п. 26. ISBN 978-1-118-61791-5.

[2] «Ограничения - включая возможность публикации в открытом доступе» . springer.com . Проверено 3 октября 2019 .

[3] Чандра, Сатиш и др. « Вывод типа для статической компиляции JavaScript ». Уведомления ACM SIGPLAN 51.10 (2016): 410-429.

[4] Джим, Тревор и Йенс Палсберг. « Вывод типов в системах рекурсивных типов с подтипами ». Доступно на домашней странице авторов (1999 г.).

[GhallabNau2004-5] Малик Галлаб; Дана Нау; Паоло Траверсо (21 мая 2004 г.). Автоматизированное планирование: теория и практика . Эльзевир. стр. 1–. ISBN 978-0-08-049051-9.

[6] Удовлетворение динамических гибких ограничений и его применение в планировании искусственного интеллекта , Архивировано 6 февраля2009 г. в Wayback Machine Иэн Мигель - слайды.

[7] Деметриу, Джордж К. « Устранение лексической неоднозначности с использованием обработки ограничений в Prolog (CHIP) ». Труды шестой конференции Европейского отделения Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 1993.

[8] Макдональд, Мэриеллен С. и Марк С. Зайденберг. « Счета удовлетворения ограничений лексического понимания и понимания предложений ». Справочник по психолингвистике (второе издание). 2006. 581–611.

[9] Маурисио Торо, Карлос Агон, Камило Руэда, Жерар Ассаяг. « GELISP: ОСНОВА ДЛЯ ПРЕДСТАВЛЕНИЯ ПРОБЛЕМ УДОВЛЕТВОРЕНИЯ МУЗЫКАЛЬНЫХ ОГРАНИЧЕНИЙ И СТРАТЕГИЙ ПОИСКА ». Журнал теоретических и прикладных информационных технологий 86 (2). 2016. 327–331.

[10] Применение подхода удовлетворения ограничений для решения проблем конфигурации продукта с помощью правил конфигурации на основе количества элементов, Донг Ян и Мин Донг, Журнал интеллектуального производства, том 24, страницы 99–111 (2013)

[11] Моди, Прагнеш Джей и др. « Подход динамического распределенного удовлетворения ограничений к распределению ресурсов ». Международная конференция по принципам и практике программирования ограничений. Шпрингер, Берлин, Гейдельберг, 2001.

[Russell2010-12] Стюарт Джонатан Рассел; Питер Норвиг (2010). Искусственный интеллект: современный подход . Прентис Холл. п. Глава 6. ISBN 9780136042594.

[13] Гибридная оптимизация: десять лет CPAIOR . Милано, Микела., Ван Хентенрик, Паскаль, Международная конференция по интеграции методов ИИ и ИЛИ в программировании с ограничениями для задач комбинаторной оптимизации. Нью-Йорк: Спрингер. 2011. ISBN. 9781441916440. OCLC 695387020 .CS1 maint: другие ( ссылка )

[14] Бодирски, Мануэль; Пинскер, Майкл (2011). «Теорема Шефера для графов». Материалы 43-го ежегодного симпозиума по теории вычислений (STOC '11) . Ассоциация вычислительной техники . С. 655–664. arXiv : 1011.2894 . Bibcode : 2010arXiv1011.2894B . DOI : 10.1145 / 1993636.1993724 . ISBN 978-1-4503-0691-1. S2CID 47097319 .

[15] Kolaitis, Phokion G .; Варди, Моше Ю. (2000). «Сдерживание конъюнктивного запроса и удовлетворение ограничений» . Журнал компьютерных и системных наук . 61 (2): 302–332. DOI : 10,1006 / jcss.2000.1713 .

[16] Цай, Цзинь-И; Чен, Си (2012). «Сложность подсчета CSP с комплексными весами». Материалы Сорок четвертого ежегодного симпозиума ACM по теории вычислений (STOC '12) . С. 909–920. arXiv : 1111.2384 . DOI : 10.1145 / 2213977.2214059 . ISBN 978-1-4503-1245-5. S2CID 53245129 .

[17] Мигель, Ян (июль 2001 г.). Удовлетворение динамических гибких ограничений и его применение в планировании искусственного интеллекта (кандидатская диссертация). Школа информатики Эдинбургского университета . CiteSeerX 10.1.1.9.6733 . hdl : 1842/326 .

[18] Dechter, R. и Dechter, A., Поддержание убеждений в сетях с динамическими ограничениями. Архивировано 17ноября2012 г. в Wayback Machine In Proc. AAAI-88, 37–42.

[19] Повторное использование решения в задачах удовлетворения динамических ограничений , Томас Шикс

[cfl-20] Даффи, КР; Leith, DJ (август 2013 г.), «Decentralized Constraint Satisfaction», IEEE / ACM Transactions on Networking, 21 (4) , 21 , стр. 1298–1308, arXiv : 1103.3240 , doi : 10.1109 / TNET.2012.2222923 , S2CID 11504393

[1]