-
题名一种基于STR算法的新表压缩方法
- 1
-
-
作者
董爱迪
李占山
于海鸿
-
机构
吉林大学计算机科学与技术学院
符号计算与知识工程教育部重点实验室(吉林大学)
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2018年第12期2734-2740,共7页
-
基金
吉林省自然科学基金项目(20180101043JC)~~
-
文摘
约束传播是约束编程的关键方法,近些年来,一些约束传播算法中频繁用到简单表缩减(simple tabular reduction,STR)算法来降低约束表的空间消耗,同时提高广义弧相容(generalised arc consistent,GAC)算法的运行速度.短支持方法是在约束传播算法中使用最广泛的一种表压缩方式,但当约束表压缩率较低时,短支持方法提高运行速度效果不明显.因此提出一种压缩约束表的新算法STRO(simple tabular reduction optimization),结合短支持压缩和位操作,在提高STR算法的运行速度的同时压缩表空间效果更好.实验结果表明:在约束表的平均大小不是特别小的情况下,STRO与ShortSTR2,STR2算法相比,速度更快、效率更高;与STRbit算法相比,在时间上可以替代STRbit算法,但STRO算法的表压缩率更大、更加节省空间.
-
关键词
约束传播
约束编程
表约束
表压缩方法
位操作
广义弧相容
简单表缩减
-
Keywords
constraint propagation
constraint programming
table constraint
table compression method
bit-wise operation
generalised arc consistent (GAC)
simple tabular reduction (str)
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名一种高效的FDE并行传播算法
被引量：1
- 2
-
-
作者
李哲
于哲舟
李占山
-
机构
吉林大学计算机科学与技术学院
符号计算与知识工程教育部重点实验室(吉林大学)
-
出处
《软件学报》
EI
CSCD
北大核心
2023年第9期4153-4166,共14页
-
基金
国家自然科学基金(61802056)
吉林省自然科学基金(20180101043JC)
+1 种基金
吉林省发展和改革委员会产业技术研究与开发项目(2019C053-9)
中国科学院太空应用重点实验室开放基金(LSU-KFJJ-2019-08)。
-
文摘
约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相容性算法用于缩减搜索空间.目前,最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇,如Compact-Table (CT)和STRbit算法.它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC).此外,完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性.最为高效的维持fPWC算法是PW-CT算法.多年来,人们提出了多种表约束相容性算法来提高剪枝能力和执行效率.因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码.它一定程度地扩大了问题模型,使在新的问题上维持相对较弱的GAC等价于在原问题上维持fPWC.目前, FDE的合适STR算法是STRFDE和STR2,而不是CT.这是由于CT算法可能产生内存溢出问题.在维持相容性算法的过程中,需要将迭代地调用各个约束执行其相容性算法过滤搜索空间,这个过程称为约束传播.动态提交方案是一个并行约束传播框架,可以并行地调度约束执行传播算法.它在大规模问题中,改进效果尤为明显.改进STRFDE和动态提交传播算法.针对FDE提出了PSTRFDE算法. PSTRFDE可以嵌入到动态提交方案中,进一步提高了约束规划问题的求解效率.大量的实验表明, PSTRFDE与CT和STRbit相比,可以减少内存占用;与STRFDE和STR2相比,可以提高算法的效率.所作工作充分说明了PSTRFDE是FDE上最为高效的过滤算法.
-
关键词
约束规划
并行约束传播
相容性算法
简单表缩减算法
-
Keywords
constraint programming(CP)
parallel constraint propagation
consistency algorithms
simple table reduction(str)algorithm
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名简化的二进制差别矩阵属性约简算法的改进
被引量：5
- 3
-
-
作者
桂现才
-
机构
湛江师范学院数学与计算科学学院
-
出处
《计算机工程与设计》
CSCD
北大核心
2007年第16期3971-3973,共3页
-
基金
湛江师范学院科研基金项目(L0602)
-
文摘
目前,基于二进制差别矩阵的属性约简算法有以下不足:所得到的属性约简与基于正区域的属性约简不一致。文献[7]中给出一种基于简化的二进制差别矩阵的快速属性约简算法,但该算法不完备。分析了算法不完备的原因,在此基础上,提出了一种改进的完备算法,该算法的时间复杂度为max(O(∣C||U∣),O(∣C∣2∣U pos||U/C))。
-
关键词
属性约简
正区域
决策表
简化的二进制差别矩阵
完备算法
-
Keywords
attribute reduction
positive region
decision table
simple binary discernibility matrix
complete algorithm
-
分类号
TP182
[自动化与计算机技术—控制理论与控制工程]
-
