Algorithms and complexity of the constraint satisfaction problem

约束满足问题的算法和复杂度

• 批准号: 313357-2010
• 负责人: Bulatov, Andrei
• 金额: $ 3.13万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=514939
• 关键词: Algorithms; complexity; constraint; satisfaction; problem

The aim in a constraint satisfaction problem (CSP) is to find an assignment of values to a given set of variables, subject to constraints on the values which can be assigned simultaneously to certain specified subsets of variables. In its counting version (#CSP) the goal is to find or approximate the number of such assignments. CSP and #CSP can be used to model a wide variety of computational problems in computer science, discrete mathematics, artificial intelligence, and elsewhere, they have found numerous applications in those areas.

约束满足问题（CSP）的目标是找到给定变量集的值的分配，该变量集受到可以同时分配给某些指定变量子集的值的约束。在其计数版本（#CSP）中，目标是找到或近似计算此类分配的数量。CSP和#CSP可用于对计算机科学、离散数学、人工智能和其他领域的各种计算问题进行建模，它们在这些领域中有许多应用。