约束分解技术回顾与展望

计算机科学 ›› 2011, Vol. 38 ›› Issue (10): 29-33.

约束分解技术回顾与展望

李占山,韩文成,郭霆

(吉林大学符号计算与知识工程教育部重点实验室长春130012);(吉林大学计算机科学与技术学院长春130012)

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家白然科学基金(60973089,60873148,60773097,61003101)，吉林省科技发展计划项目基金(20101501,20100185,20090108,20080107)，浙江省白然科学基金(Yll00191)，欧盟合作项目(155776-EM-1-2009-1-IT-ERAMUN-DUS-ECW-L12)，吉林大学符号计算与知识工程教育部重点实验室开放项目(93K-17-2009-K05)资助。

Retrospect and Prospect of Decomposition Technology

LI Zhan-shan,HAN Wen-cheng,GUO Ting

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

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

关键词: 约束满足问题，约束分解技术，知识表示框架

Abstract: 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.

Key words: Constraint satisfaction problems,Decomposition technology,Knowledge representation frame

李占山,韩文成,郭霆. 约束分解技术回顾与展望[J]. 计算机科学, 2011, 38(10): 29-33. https://doi.org/

LI Zhan-shan,HAN Wen-cheng,GUO Ting. Retrospect and Prospect of Decomposition Technology[J]. Computer Science, 2011, 38(10): 29-33. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed