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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Формальне визначення[ред.ред. код]

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

Розвязання[ред.ред. код]

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

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

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

Проблеми розв'язання[ред.ред. код]

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

Посилання[ред.ред. код]

  1. Schaefer's theorem for graphs // CoRR. — abs/1011.2894 (2010) С. 2894.

Використані посилання[ред.ред. код]