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

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

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

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

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

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

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

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

{ Displaystyle X = {X_ {1}, ldots, X_ {n} }}

набор переменных,

{ Displaystyle D = {D_ {1}, ldots, D_ {п} }}

представляет собой набор их соответствующих областей значений, а

{ Displaystyle C = {C_ {1}, ldots, C_ {m} }}

это набор ограничений.

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

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

Разрешение

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

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

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

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

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

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

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

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

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

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

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

Варианты

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

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

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

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

Гибкие CSP

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

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

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

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

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

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

Краткое введение в удовлетворение ограничений на YouTube
Стивен Минтон; Энди Филипс; Марк Д. Джонстон; Филип Лэрд (1993). «Сведение к минимуму конфликтов: эвристический метод исправления ограничений-удовлетворения и задач планирования» (PDF). Журнал исследований искусственного интеллекта. 58 (1–3): 161–205. CiteSeerX 10.1.1.308.6637. Дои:10.1016 / 0004-3702 (92) 90007-к.^{[постоянная мертвая ссылка ]}
Цанг, Эдвард (1993). Основы удовлетворения ограничений. Академическая пресса. ISBN 0-12-701610-4
Чен, Хьюби (декабрь 2009 г.). «Встреча логики, сложности и алгебры». Опросы ACM Computing. 42 (1): 1–32. arXiv:cs / 0611018. Дои: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] Лекутр, Кристоф (2013). Сети ограничений: методы и алгоритмы. Вайли. п. 26. ISBN 978-1-118-61791-5.

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

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

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

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

[6] Удовлетворение динамических гибких ограничений и его применение в планировании ИИ, В архиве 2009-02-06 в Wayback Machine Ян Мигель - слайды.

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

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

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

[10] Моди, Прагнеш Джей и др. "Подход динамического распределенного удовлетворения ограничений к распределению ресурсов. »Международная конференция по принципам и практике программирования с ограничениями. Springer, Berlin, Heidelberg, 2001.

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

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

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

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

[15] Цай, Цзинь-И; Чен, Си (2012). Сложность подсчета CSP с комплексными весами. С. 909–920. arXiv:1111.2384. Дои:10.1145/2213977.2214059. ISBN 978-1-4503-1245-5. S2CID 53245129.

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

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

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

[cfl-19] Даффи, К.Р .; Лейт, Д.Дж. (Август 2013 г.), «Децентрализованное удовлетворение ограничений», Транзакции IEEE / ACM в сети, 21 (4), 21, стр. 1298–1308, arXiv:1103.3240, Дои:10.1109 / TNET.2012.2222923, S2CID 11504393

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]