主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
陈恩红,张振亚,王煦法.相接行凸约束网络的快速识别算法.软件学报,2002,13(5):972-979
相接行凸约束网络的快速识别算法
A Fast Recognition Algorithm of CRC Constraint Networks
投稿时间:2000-06-10  修订日期:2001-03-01
DOI:
中文关键词:  二项约束网络  RC约束网络  CRC约束网络  PQ树  CRC约束矩阵的标准型
英文关键词:binary constraint network  RC constraint network  CRC constraint network PQ-Tree  the standardized form for CRC constraint matrix
基金项目:国家自然科学基金资助项目(60005004);国家重点基础研究发展规划973资助项目(G1998030509)
作者单位
陈恩红 中国科学技术大学,计算机科学与技术系,安徽,合肥,230026 
张振亚 中国科学技术大学,计算机科学与技术系,安徽,合肥,230026 
王煦法 中国科学技术大学,计算机科学与技术系,安徽,合肥,230026 
摘要点击次数: 3086
全文下载次数: 2626
中文摘要:
      约束网络为计算机科学中的许多问题提供了一种有效的表示方法.一般而言,约束满足问题是NP完全的.然而,许多实际问题通常对约束的结构或形式施加了特殊的限制,从而能够高效地加以解决.迄今,为了识别易处理约束类,人们对特殊的约束或约束网络方面进行了许多研究.相接行凸(connected row-convex,简称CRC)约束网络是Deville等人提出的一类易处理问题.为了给该类问题寻求有效的快速识别算法,在CRC约束网络相关工作基础上,提出了CRC约束矩阵的标准型.在分析CRC约束矩阵的标准型性质的基础上,利用行凸(row-convex,简称RC)约束网络的判定,结合PQ树(由P节点和Q节点构成的树)的性质和矩阵的索引表示法,给出了CRC约束网络的快速识别算法.该算法的时间复杂度为O(n3d2),其中,n为约束网络涉及的变量数,d为各变量的定义域中最大定义域的大小.该时间复杂度达到该类问题的最佳时间复杂度,从而为实际的CRC约束满足问题的求解提供了可行的方法.
英文摘要:
      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(n3d2),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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利