相接行凸约束网络的快速识别算法

• 作者: 张振亚 王煦法 陈恩红
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 二项约束网络 RC约束网络 CRC约束网络 PQ树 CRC约束矩阵的标准型
• 年，卷（期）: 2002,（5）
• 页码范围: 972-979
• 页数: 8页
• 分类号: TP301
• 字数: 7114字
• 语种: 中文

摘要

约束网络为计算机科学中的许多问题提供了一种有效的表示方法.一般而言,约束满足问题是NP完全的.然而,许多实际问题通常对约束的结构或形式施加了特殊的限制,从而能够高效地加以解决.迄今,为了识别易处理约束类,人们对特殊的约束或约束网络方面进行了许多研究.相接行凸(connected row-convex,简称CRC)约束网络是Deville等人提出的一类易处理问题.为了给该类问题寻求有效的快速识别算法,在CRC约束网络相关工作基础上,提出了CRC约束矩阵的标准型.在分析CRC约束矩阵的标准型性质的基础上,利用行凸(row-convex,简称RC)约束网络的判定,结合PQ树(由P节点和Q节点构成的树)的性质和矩阵的索引表示法,给出了CRC约束网络的快速识别算法.该算法的时间复杂度为O(n3d2),其中,n为约束网络涉及的变量数,d为各变量的定义域中最大定义域的大小.该时间复杂度达到该类问题的最佳时间复杂度,从而为实际的CRC约束满足问题的求解提供了可行的方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈恩红	中国科学技术大学计算机科学与技术系	87	1942	22.0	42.0
2	王煦法	中国科学技术大学计算机科学与技术系	191	4142	33.0	58.0
3	张振亚	中国科学技术大学计算机科学与技术系	17	264	7.0	16.0