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

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