Задача виконання обмежень

Зада́ча викона́ння обме́жень (Constraint satisfaction problem) (ЗВО) — це математичні проблеми, визначені як сукупність об'єктів, стан яких має задовільняти ряду обмежень. ЗВО представляє сутності проблеми як однорідний набір обмежень, що накладаються на змінні, які розв'язуються методами . ЗВО є предметом інтенсивних досліджень і в галузі штучного інтелекту, і дослідженні операцій, оскільки закономірності у формулюванні цих задач складають загальну основу для аналізу та вирішення проблем в багатьох неспоріднених областях. , що вимагає поєднання евристичних та комбінаторних методів пошуку для швидкого вирішення.
Приклади простих задач, які можуть розглядатись як задачі виконання обмежень: Задача про вісім ферзів, Проблема чотирьох фарб, Судоку.

В загальному випадку, проблема виконання обмежень може бути складнішою і не зводитись до цих простих систем.

Формальне визначення

Формально задача виконання обмежень визначається трійкою ${\displaystyle \langle X,D,C\rangle }$, де ${\displaystyle X}$ — множина змінних, ${\displaystyle D}$ — область значень і ${\displaystyle C}$ — множина обмежень. Кожне обмеження, своєю чергою, є парою ${\displaystyle \langle t,R\rangle }$ (зазвичай представляються матрицею), де ${\displaystyle t}$ — кортеж з ${\displaystyle n}$ змінних та ${\displaystyle R}$ — ${\displaystyle n}$-місне відношення ${\displaystyle D}$. Оцінка змінної — це функція, що відображає множину змінних на область значень, ${\displaystyle v:X\rightarrow D}$. Оцінка ${\displaystyle v}$ задовільняє обмеження ${\displaystyle \langle (x_{1},\ldots ,x_{n}),R\rangle }$ якщо ${\displaystyle (v(x_{1}),\ldots ,v(x_{n}))\in R}$. Розв'язок — це оцінка, що задовільняє всім обмеженням.

Розв'язання

Задача виконання обмежень на скінченних областях зазвичай вирішується за допомогою алгоритмів пошуку. Найчастіше використовуються пошук з поверненнями, з обмеженням глибини та локальний пошук.

Пошук з вертанням — це рекурсивний алгоритм. Він підтримує часткове означення змінних. Спочатку всі змінні невизначені. На кожному кроці обираємо змінну та по черзі перебираємо всі можливі її значення. Кожне значення з послідовності зіставляється з обмеженнями; при невідповідності значення обмеженням рекурсивний виклик не виконується. Коли всі значення було переглянуто, алгоритм повертається. В цьому простому алгоритмі з поверненнями під відповідністю розуміємо задоволення всіх обмежень, всі змінні яких були визначені. Існує кілька варіантів повернення. Пошук з вертанням підвищує ефективність перевірки відповідності. Пошук з вертанням дозволяє в деяких випадках пришвидшити пошук за рахунок виключення «більше ніж однієї змінної».

Теоретичні аспекти задачі виконання обмежень

Проблеми розв'язання

Задачі виконання обмежень також вивчаються в теорії складності обчислень та теорії кінцевої моделі. Важливе питання полягає в тому, що для кожного набору відношень, множина всіх задач виконання обмежень, що може бути представлена лише за допомогою відношень з цієї множини, є P- або NP-повною задачею. Якщо така дихотомічна теорема справедлива, то задачі виконання обмежень забезпечують одну з найбільших відомих підмножин складності NP, що дозволяє уникнути проміжних задач NP-складності, існування якої було продемонстровано в в припущенні, що P ≠ NP. оброблює той випадок, коли всі наявні відношення є логічними операторами, тобто множина значень має розмір 2. Дихотомічна теорема Шафера була узагальнена до ширшого класу відношень.

Див. також

• Зворотний перехід

Примітки

1. Bodirsky, Manuel; Pinsker, Michael (2010). Schaefer's theorem for graphs. CoRR. abs/1011.2894: 2894. arXiv:1011.2894. Bibcode:2010arXiv1011.2894B.

Використані посилання

• Tsang, Edward (1993). . Academic Press. Архів оригіналу за 23 квітня 2021. Процитовано 6 березня 2012.
• Chen, Hubie (December 2009). A Rendezvous of Logic, Complexity, and Algebra. ACM Computing Surveys. ACM. 42 (1): 1—32. doi:10.1145/1592451.1592453.
• Dechter, Rina (2003). . Morgan Kaufmann. Архів оригіналу за 25 квітня 2021. Процитовано 6 березня 2012.
• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press.
• Lecoutre, Christophe (2009). . ISTE/Wiley. Архів оригіналу за 7 листопада 2017. Процитовано 6 березня 2012.
• Tomás Feder, Constraint satisfaction: a personal perspective [ 19 січня 2021 у Wayback Machine.], manuscript.
• Forced Satisfiable CSP Benchmarks of Model RB [ 25 січня 2021 у Wayback Machine.]
• , Ian Miguel — slides.
• Constraint Propagation [ 19 квітня 2009 у Wayback Machine.] — Dissertation by Guido Tack giving a good survey of theory and implementation issues