| dbo:abstract
|
- Constraint satisfaction problems (CSPs) are mathematical questions defined as the set of objects whose state must satisfy a number of constraints or/ limitations. CSPs represent a entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, Boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem. Examples of problems that can be modeled as a constraint satisfaction problem include:
* Type inference
* Eight queens puzzle
* Map coloring problem
* Maximum cut problem
* Sudoku, Crosswords, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato and many other logic puzzles These are often provided with tutorials of CP, ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include automated planning, lexical disambiguation, musicology, product configuration and resource allocation. The existence of a solution to a CSP can be viewed as a decision problem. This can be decided by finding a solution, or failing to find a solution after exhaustive search (stochastic algorithms typically never reach an exhaustive conclusion, while directed searches often do, on sufficiently small problems). In some cases the CSP might be known to have solutions beforehand, through some other mathematical inference process. (en)
- Ein Constraint-Satisfaction-Problem (CSP; deutsch: Bedingungserfüllungsproblem) ist eine Aufgabenstellung aus der künstlichen Intelligenz und aus dem Operations Research. Aufgabe ist es, einen Zustand (d. h. Belegungen von Variablen) zu finden, der alle aufgestellten Bedingungen (Constraints) erfüllt. Ein Constraint-Satisfaction-Problem besteht aus einer Menge von Variablen, ihren Wertebereichen und den Bedingungen, die Verknüpfungen zwischen den Variablen herstellen und dadurch festlegen, welche Kombinationen von Werten der Variablen zulässig sind. Auf diese Weise lassen sich eine Vielfalt von Problemen aus Informatik, Mathematik und weiteren Anwendungsgebieten formulieren. Einfache Beispiele für solche Probleme sind das Damenproblem, das Vier-Farben-Problem, Sudoku, Str8ts oder das Erfüllbarkeitsproblem der Aussagenlogik (SAT bzw. SAT-k), Erfüllbarkeitsproblem für quantifizierte boolesche Formeln, Graphenfärbung oder Erfüllbarkeitsproblem für Schaltkreise, aber auch physikalische Probleme wie das Isingmodell und andere Spinmodelle auf Gittern. Dem entspricht in der elementaren Mathematik das Lösen einer Gleichung oder eines Gleichungssystems – als Constraint-Satisfaction-Probleme bezeichnet man speziell die Fragestellungen, die sich analytisch so nicht oder nur aufwändig lösen lassen. Ein CSP wird gelöst, indem eine Belegung der Variablen gefunden wird, die allen Bedingungen genügt. Im Unterschied zu anderen Optimierungsproblemen, in denen eine „möglichst gute“ Lösung gesucht wird, fordern Constraint-Satisfaction-Probleme eine vollständige Erfüllung jeder einzelnen Vorbedingung. Sind die aufgestellten Bedingungen widersprüchlich, so gibt es keine Lösung des Problems (respektive umgekehrt: gibt es nachweislich keine Lösung, sind die Vorbedingungen als unvereinbar bewiesen). Es kann aber durchaus mehrere oder viele Lösungen geben. Gibt es nur eine, spricht man wie bei anderen Optimierungsfragen von einer „eindeutigen Lösung“ und bei dem entsprechenden SAT-Problem zu entscheiden, ob es nur eine Lösung gibt von unique SAT. Constraint-Satisfaction-Probleme werden in verschiedene Beschränkungs- bzw. Bedingungstypen unterteilt:
* unäre Bedingungen (Bedingungen, die den Wert einer einzelnen Variable kontrollieren)
* binäre Bedingungen (Verknüpfungen zwischen zwei Variablen)
* Bedingungen höherer Ordnung (Verknüpfungen, die drei oder mehrere Variablen umfassen) Zur Lösung von Constraint-Satisfaction-Problemen werden verschiedene Ansätze kombiniert:
* Aus bestehenden Bedingungen werden neue Bedingungen berechnet, die den Wertebereich von Variablen zusätzlich einschränken oder zu einem Widerspruch führen (Bedingungsfortpflanzung, engl. Constraint Propagation).
* Im Lösungsraum der Variablen wird systematisch nach einer Lösung gesucht. Grundsätzlich können für die Lösung von CSPs allgemeine Suchalgorithmen verwendet werden. Allerdings lässt die Besonderheit der Problemklasse Algorithmen zu, die um einiges effizienter arbeiten als allgemeine Suchalgorithmen.
* Zustände sind durch Werte von Variablen definiert.
* Operatoren belegen eine Variable mit einem Wert.
* Der Zieltest wird durch Bedingungen spezifiziert, welche die Variablenbelegungen erfüllen müssen.
* Ein Zielzustand ist eine Belegung der Variablen mit Werten, die alle Bedingungen erfüllen. Beispiele für Algorithmen, die sich besonders für die Lösung von Constraint-Satisfaction-Problemen eignen, sind der AC-3-Algorithmus, Backtracking oder die . Die CSP sind ein häufiger Testboden für Methoden der Komplexitätstheorie. Für die Komplexität in einer breiten Klasse von CSP-Abzählproblemen wurde 2021 der Gödel-Preis an Andrei Bulatov, Martin Dyer, David Richerby, Jin-Yi Cai und Xi Chen verliehen. Die Dichotomie besteht darin, dass sie entweder in Polynomzeit lösbar sind oder Sharp-P-schwer sind. (de)
- Problemas de satisfacción de restricciones (CSP, por sus siglas en inglés), son problemas matemáticos definidos como un conjunto de objetos tal que su estado debe satisfacer un número de restricciones o limitaciones. Los CSP representan las entidades de un problema como una colección homogénea finita de restricciones sobre variables, las que son resueltas por métodos de satisfacción de restricciones. Los CSP son el tema de una intensa investigación en Inteligencia Artificial e Investigación de operaciones, dado que la generalidad en su formulación provee un principio básico para analizar y resolver problemas de distintos tipos. Los CSP a menudo muestran gran complejidad, requiriendo una combinación de métodos heurísticos y búsqueda combinatoria para ser resueltos en un tiempo razonable. El Problema de satisfacibilidad booleana (SAT), las Teorías de módulo de satisfacibilidad (SMT) y la Programación de conjuntos de respuestas (ASP) pueden ser a grandes rasgos modelados como una forma de problema de satisfacción de restricciones. Ejemplos de problemas sencillos que pueden ser modelados como problema de satisfacción de restricciones.
* Problema de las ocho reinas
* Teorema de los cuatro colores Problema de coloración de mapas
* Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato y muchos otros puzles De forma general, problemas de restricciones pueden ser más difíciles o complejos, y pueden no ser expresables en alguno de estos sistemas simples. Ejemplos de la vida real son Planeamiento y Asignación de recursos. (es)
- Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable. Ils sont notamment au cœur de la programmation par contraintes, un domaine fournissant des langages de modélisation de problèmes et des outils informatiques les résolvant. (fr)
- 制約充足問題（せいやくじゅうそくもんだい、英: Constraint satisfaction problem, CSP）は、複数の制約条件を満たすオブジェクトや状態を見つけるという数学の問題を指す。CSPは特に人工知能やオペレーションズ・リサーチで研究されている。多くのCSPでは、それなりの時間内に解くのにヒューリスティクスと組合せ最適化手法を組み合わせる必要がある。 制約充足問題の具体例:
* エイト・クイーン
* 四色問題
* 数独
* 充足可能性問題 制約充足問題を解くアルゴリズムとしては、、バックトラッキング、などがある。 (ja)
- Molti problemi nell'ambito dell'Intelligenza Artificiale sono classificabili come Problemi di Soddisfacimento di Vincoli (Constraint Satisfaction Problem o CSP); fra questi citiamo problemi di complessità combinatorica, di allocazione di risorse, pianificazione e ragionamento temporale. Questi problemi possono essere risolti efficientemente attraverso tecniche ben note di risoluzione di CSP. (it)
- 제약 충족 문제(Constraint satisfaction problem, CSP)는 복수의 조건을 충족하는 상태를 찾아내는 수학 문제를 가리킨다. CSP는 특히 인공지능이나 운용 과학 분야에서 심도 있게 연구되고 있다. 보통 을 보이기 때문에 적정한 시간 내에 문제를 풀기 위해서는 휴리스틱과 조합 최적화 기법을 조합할 필요가 있다. 제약 충족 문제의 구체적인 예:
* 8퀸 문제
* 4색 문제
* 스도쿠
* 충족 가능성 문제 제약 충족 문제를 푸는 알고리즘은 AC-3 알고리즘, 백트랙킹, 등이 있다. (ko)
- Одной из важных задач искусственного интеллекта (ИИ) является задача удовлетворения ограничений (УО) (constraint satisfaction problem). Теория УО предлагает удобный аппарат и простую формальную схему для представления и решения комбинаторных задач ИИ. Целью решения задачи УО является нахождение значений переменных, удовлетворяющих заданным ограничениям. Проблема существования решений задачи УО является NP-полной. Тесно связано с теорией УО программирование в ограничениях, которое является парадигмой программирования для декларативного описания и эффективного решения комбинаторных задач.Многие классические комбинаторные задачи, такие как известная теорема Ферма, задача выполнимости (SAT) из пропозициональной логики, задача раскраски графа и задача изоморфизма графов из теории графов могут формулироваться в виде задач УО (ЗУО).Остановимся подробнее на одной из давно поставленных задач в математике - задаче о раскраске графа, частным случаем которой является известная задача о раскраске карты. Формулировка задачи о раскраске в виде задачи УО ставит в соответствие вершинам раскрашиваемого графа переменные, возможные цвета представляют собой домены (области определения) переменных, а ограничения-неравенства между смежными вершинами являются ограничениями задачи. Разумеется, здесь невозможно подробно описатьвсе аспекты и направления теории удовлетворения ограничений и программирования вограничениях, поэтому более полную информацию и библиографию можно найти в переводной монографии Рассел С., Норвиг П., в которой освещаются вопросы УО и в обзоре О.А.Щербины. Обзор основных направлений программирования в ограничениях до 2000 г. сделан в работе Ушакова и Телермана (2000). (ru)
- O problema da satisfação de restrições do inglês constraint satisfaction problems (CSPs) são problemas matemáticos definidos como um conjunto de objetos cujo estado dos mesmos deve satisfazer uma série de restrições. CSPs representam as entidades de um problema como um conjunto homogêneo de restrições finitas sobre as variável do problema, tal problema é resolvido por métodos de satisfação de restrições. Temos que CSPs são alvos de pesquisa tanto em Inteligência Artificial quanto em Pesquisa Operacional , uma vez a regularidade presente em sua formulação proporciona uma base comum para analise e resolução de problemas de famílias não relacionadas. CSPs geralmente apresentam alta complexidade e são custosos exigindo que sejam usadas métodos heurísticos e de busca combinatória para que se possa resolver tais problemas em tempo aceitável. O problema da satisfabilidade booleana (SAT), o Problema da Satisfabilidade de Módulos Teóricos (SMT) e a programação de conjunto de respostas (ASP) pode ser aproximado pensando-se em certas formas do problema da satisfação de restrições. Como exemplo de problemas simples que podem ser modelados como um problema de satisfação de restrições temos:
* O problema das oito rainhas
* Coloração de grafos
* Sudoku, Futoshiki, Kakuro (Somas cruzadas), Numbrix, Hidato e muitos outros puzzles lógicos Estes exemplos acima geralmente são usados para demonstrar a teoria em tutoriais de ASP, SAT e solucionados SMT. No caso geral tais problemas de restrição podem ser muito mais complicados de serem resolvidos, ou tais sistemas simples não são capazes de expressar tais problemas. Como exemplos mais próximos da vida real temos os problemas de alocação de recursos e alocação de horários. (pt)
- 約束滿足問題（CSPs）是種數學的問題，其定義為一組物件(object)，而這些物件需要滿足一些限制或條件。 CSPs將其問題中的單元(entities)表示成在變數上有限條件的一組同質(homogeneous)的集合, 這類問題透過"約束滿足方法"來解決。CSPs是人工智慧和運籌學 的熱門主題,因為它們公式中的規律，提供了共同基礎來分析、解決很多看似不相關的問題。 , 需要同時透過啟發式搜索 和 的方法，來在合理的時間內解決問題。 布林可滿足性問題 (SAT), (SMT)和回答集程式設計 (ASP) 可以算是某種程度上的約束滿足問題。 以下舉例為幾個簡單的約束滿足問題:
* 八皇后問題
* 圖著色問題
* 填字遊戲、數獨及其他一些邏輯益智遊戲 這些是提供的ASP,Boolean SAT和SMT教學課程的人通常會教的。在一般情况下，約束滿足問題會是更困難，而且可能難以用這些簡單系統的例子來表達。 現實生活中的例子包含和資源配置。 (zh)
- Зада́ча викона́ння обме́жень (Constraint satisfaction problem) (ЗВО) — це математичні проблеми, визначені як сукупність об'єктів, стан яких має задовільняти ряду обмежень. ЗВО представляє сутності проблеми як однорідний набір обмежень, що накладаються на змінні, які розв'язуються методами . ЗВО є предметом інтенсивних досліджень і в галузі штучного інтелекту, і дослідженні операцій, оскільки закономірності у формулюванні цих задач складають загальну основу для аналізу та вирішення проблем в багатьох неспоріднених областях. , що вимагає поєднання евристичних та комбінаторних методів пошуку для швидкого вирішення.Приклади простих задач, які можуть розглядатись як задачі виконання обмежень: Задача про вісім ферзів, Проблема чотирьох фарб, Судоку. В загальному випадку, проблема виконання обмежень може бути складнішою і не зводитись до цих простих систем. (uk)
|
| rdfs:comment
|
- Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable. Ils sont notamment au cœur de la programmation par contraintes, un domaine fournissant des langages de modélisation de problèmes et des outils informatiques les résolvant. (fr)
- 制約充足問題（せいやくじゅうそくもんだい、英: Constraint satisfaction problem, CSP）は、複数の制約条件を満たすオブジェクトや状態を見つけるという数学の問題を指す。CSPは特に人工知能やオペレーションズ・リサーチで研究されている。多くのCSPでは、それなりの時間内に解くのにヒューリスティクスと組合せ最適化手法を組み合わせる必要がある。 制約充足問題の具体例:
* エイト・クイーン
* 四色問題
* 数独
* 充足可能性問題 制約充足問題を解くアルゴリズムとしては、、バックトラッキング、などがある。 (ja)
- Molti problemi nell'ambito dell'Intelligenza Artificiale sono classificabili come Problemi di Soddisfacimento di Vincoli (Constraint Satisfaction Problem o CSP); fra questi citiamo problemi di complessità combinatorica, di allocazione di risorse, pianificazione e ragionamento temporale. Questi problemi possono essere risolti efficientemente attraverso tecniche ben note di risoluzione di CSP. (it)
- 제약 충족 문제(Constraint satisfaction problem, CSP)는 복수의 조건을 충족하는 상태를 찾아내는 수학 문제를 가리킨다. CSP는 특히 인공지능이나 운용 과학 분야에서 심도 있게 연구되고 있다. 보통 을 보이기 때문에 적정한 시간 내에 문제를 풀기 위해서는 휴리스틱과 조합 최적화 기법을 조합할 필요가 있다. 제약 충족 문제의 구체적인 예:
* 8퀸 문제
* 4색 문제
* 스도쿠
* 충족 가능성 문제 제약 충족 문제를 푸는 알고리즘은 AC-3 알고리즘, 백트랙킹, 등이 있다. (ko)
- 約束滿足問題（CSPs）是種數學的問題，其定義為一組物件(object)，而這些物件需要滿足一些限制或條件。 CSPs將其問題中的單元(entities)表示成在變數上有限條件的一組同質(homogeneous)的集合, 這類問題透過"約束滿足方法"來解決。CSPs是人工智慧和運籌學 的熱門主題,因為它們公式中的規律，提供了共同基礎來分析、解決很多看似不相關的問題。 , 需要同時透過啟發式搜索 和 的方法，來在合理的時間內解決問題。 布林可滿足性問題 (SAT), (SMT)和回答集程式設計 (ASP) 可以算是某種程度上的約束滿足問題。 以下舉例為幾個簡單的約束滿足問題:
* 八皇后問題
* 圖著色問題
* 填字遊戲、數獨及其他一些邏輯益智遊戲 這些是提供的ASP,Boolean SAT和SMT教學課程的人通常會教的。在一般情况下，約束滿足問題會是更困難，而且可能難以用這些簡單系統的例子來表達。 現實生活中的例子包含和資源配置。 (zh)
- Ein Constraint-Satisfaction-Problem (CSP; deutsch: Bedingungserfüllungsproblem) ist eine Aufgabenstellung aus der künstlichen Intelligenz und aus dem Operations Research. Aufgabe ist es, einen Zustand (d. h. Belegungen von Variablen) zu finden, der alle aufgestellten Bedingungen (Constraints) erfüllt. Constraint-Satisfaction-Probleme werden in verschiedene Beschränkungs- bzw. Bedingungstypen unterteilt: Zur Lösung von Constraint-Satisfaction-Problemen werden verschiedene Ansätze kombiniert: (de)
- Constraint satisfaction problems (CSPs) are mathematical questions defined as the set of objects whose state must satisfy a number of constraints or/ limitations. CSPs represent a entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems (en)
- Problemas de satisfacción de restricciones (CSP, por sus siglas en inglés), son problemas matemáticos definidos como un conjunto de objetos tal que su estado debe satisfacer un número de restricciones o limitaciones. Los CSP representan las entidades de un problema como una colección homogénea finita de restricciones sobre variables, las que son resueltas por métodos de satisfacción de restricciones. Los CSP son el tema de una intensa investigación en Inteligencia Artificial e Investigación de operaciones, dado que la generalidad en su formulación provee un principio básico para analizar y resolver problemas de distintos tipos. Los CSP a menudo muestran gran complejidad, requiriendo una combinación de métodos heurísticos y búsqueda combinatoria para ser resueltos en un tiempo razonable. El (es)
- O problema da satisfação de restrições do inglês constraint satisfaction problems (CSPs) são problemas matemáticos definidos como um conjunto de objetos cujo estado dos mesmos deve satisfazer uma série de restrições. CSPs representam as entidades de um problema como um conjunto homogêneo de restrições finitas sobre as variável do problema, tal problema é resolvido por métodos de satisfação de restrições. Temos que CSPs são alvos de pesquisa tanto em Inteligência Artificial quanto em Pesquisa Operacional , uma vez a regularidade presente em sua formulação proporciona uma base comum para analise e resolução de problemas de famílias não relacionadas. CSPs geralmente apresentam alta complexidade e são custosos exigindo que sejam usadas métodos heurísticos e de busca combinatória para que s (pt)
- Одной из важных задач искусственного интеллекта (ИИ) является задача удовлетворения ограничений (УО) (constraint satisfaction problem). Теория УО предлагает удобный аппарат и простую формальную схему для представления и решения комбинаторных задач ИИ. Целью решения задачи УО является нахождение значений переменных, удовлетворяющих заданным ограничениям. Проблема существования решений задачи УО является NP-полной. Обзор основных направлений программирования в ограничениях до 2000 г. сделан в работе Ушакова и Телермана (2000). (ru)
- Зада́ча викона́ння обме́жень (Constraint satisfaction problem) (ЗВО) — це математичні проблеми, визначені як сукупність об'єктів, стан яких має задовільняти ряду обмежень. ЗВО представляє сутності проблеми як однорідний набір обмежень, що накладаються на змінні, які розв'язуються методами . ЗВО є предметом інтенсивних досліджень і в галузі штучного інтелекту, і дослідженні операцій, оскільки закономірності у формулюванні цих задач складають загальну основу для аналізу та вирішення проблем в багатьох неспоріднених областях. , що вимагає поєднання евристичних та комбінаторних методів пошуку для швидкого вирішення.Приклади простих задач, які можуть розглядатись як задачі виконання обмежень: Задача про вісім ферзів, Проблема чотирьох фарб, Судоку. (uk)
|
