约束分解技术回顾与展望

Retrospect and Prospect of Decomposition Technology

约束满足问题是一个强有力的知识表示框架,可以有效地解决许多问题。由于约束满足问题一般情况下是NP难度的问题,因此通过约束分解来降低计算的开销具有十分重要的意义。主要描述约束分解在约束满足问题中的地位、经典的分解技术和约束分解技术的发展历史,然后简要地分析这些分解技术。介绍了关于约束分解研究的最新状况,并描述、分析和总结其主要求解思想。最后根据存在的问题与不足提出了下一步的工作方向和研究思路。

Constraint satisfaction problems formalism offers a powerful frame of knowledge representation that can solve many problems.But constraint satisfaction problems are often NP-hard problems,so it＇s very important to using decomposition to reduce the costs of computation.This paper mainly described the importance of the decomposition in constraint satisfaction problems,several classic decomposition technologies and history of decomposition,and then analyzed these technologies.We introduced several new technologies of decomposition and analyzed them,then made a summary.We proposed our next research ideas and direction according to the problems in these technologies.