Problemas de satisfacción de restricciones (CSP) por sus siglas en inglés, son problemas matemáticos definido como un conjunto de objetos tal que su estado debe satisfacer un número de restricciones o limitaciones. Los CSP representa 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), el Satisfiability Modulo Theories (SMT) y answer set programming (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. \n* Problema de las ocho reinas \n* Teorema de los cuatro colores Problema de coloración de mapas \n* Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato y muchos otros puzzles De forma general, problemas de restricciones pueden ser más difíciles, y pueden no ser expresables en alguno de estos sistemas simples. Ejemplos de la vida real son Planeamiento y Asignación de recursos.

Leer el artículo completo en Wikipedia · CC-BY-SA

Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the 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 intense 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. The Boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT) and answer set programming (ASP) can be roughly thought of as certain forms of the constraint satisfaction problem. Examples of simple problems that can be modeled as a constraint satisfaction problem include: \n* Eight queens puzzle \n* Map coloring problem \n* Crosswords, Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato and many other logic puzzles These are often provided with tutorials of 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 and resource allocation.

Leer el artículo completo en Wikipedia · CC-BY-SA