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

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

A Fast Recognition Algorithm of CRC Constraint Networks

Constraint networks provide a useful framework for the formulation of many problems in computer science. In general, constraint satisfaction problems are NP-Complete. Many problems specially restrict the structure of constraints or the form of the constraints, then allow them to be solved efficiently. For the identification of such tractable constraints, much work has been devoted to the study of special classes of constraints or constraint networks. As pointed out by Deville et al., a class of connected row-convex(CRC)constraints is shown to be tractable.This paper intrnds to finds to fint an efficient recognition algorithm for the class of constraint networks.In this paper,a standardized form for the CRC constraint matrix is proposed based on the related finding on CRC constranint network.The basic characteristics of the standardized form are analyzed,and a fast algorithm is provided for the recognition of CRC constraint networks based on a recognition algorithm of the RC constraint network,properties of PQ tree(a tree composed by P nodes and Qnodes)and an indexed matrix representation of constraints.The time complexity of the algorithm is O(n³d²),where n is the number of variables in aconstraint network and d is the maximum size of the domain for wach variable.It reaches the optimum time complexity for a CRC constraint network recognition algorithm,and hence provides afeasible solution to practical CRC constraint satisfaction problems.