一种基于差别矩阵的属性约简完备算法 被引量：29

1

作者 王兵 陈善本 《上海交通大学学报》 EI CAS CSCD 北大核心 2004年第1期43-46,共4页

提出了一种基于差别矩阵的粗糙集属性约简完备算法,算法的求解策略是在每次迭代过程中只选择必要的条件属性,如果在某次迭代过程中找不到这样的条件属性,则任意排除一条件属性,为下一次迭代中找到必要的条件属性做准备.分析了算法在最... 提出了一种基于差别矩阵的粗糙集属性约简完备算法,算法的求解策略是在每次迭代过程中只选择必要的条件属性,如果在某次迭代过程中找不到这样的条件属性,则任意排除一条件属性,为下一次迭代中找到必要的条件属性做准备.分析了算法在最坏情况下的时间复杂性,给出了该算法相对Pawlak约简的完备性的证明.同已有的同类约简算法相比,该算法在最坏情况下具有更小的时间复杂性. 展开更多

关键词 粗糙集 差别矩阵 属性约简 完备算法

下载PDF 职称材料

改进的基于差别矩阵的属性约简算法 被引量：21

2

作者 王加阳 高灿 《计算机工程》 CAS CSCD 北大核心 2009年第3期66-67,73,共3页

指出现有差别矩阵属性约简算法的不足,对原有差别矩阵和属性重要性度量方法进行改进,运用差别矩阵元素项的重要性质,提出一种新的启发式约简完备算法,有效地降低差别矩阵约简算法的空间复杂度。仿真实验结果显示,新算法产生的约简与分... 指出现有差别矩阵属性约简算法的不足,对原有差别矩阵和属性重要性度量方法进行改进,运用差别矩阵元素项的重要性质,提出一种新的启发式约简完备算法,有效地降低差别矩阵约简算法的空间复杂度。仿真实验结果显示,新算法产生的约简与分辨函数思想产生的最优约简一致,表明了新算法的有效性与完备性。 展开更多

关键词 差别矩阵 最优约简 完备算法

下载PDF 职称材料

基于差别矩阵的增量式属性约简完备算法 被引量：13

3

作者 刘洋 冯博琴 周江卫 《西安交通大学学报》 EI CAS CSCD 北大核心 2007年第2期158-161,208,共5页

为了解决基于差别矩阵的属性约简完备算法得不到最小约简的问题,提出了一种改进的属性约简方法.该方法将信息论定义的属性重要性作为启发式信息,并通过构造一个条件信息熵算子对差别集合进行运算,同时利用算子来计算候选属性的剔除次序... 为了解决基于差别矩阵的属性约简完备算法得不到最小约简的问题,提出了一种改进的属性约简方法.该方法将信息论定义的属性重要性作为启发式信息,并通过构造一个条件信息熵算子对差别集合进行运算,同时利用算子来计算候选属性的剔除次序,采用宽度优先搜索策略使约简集合中含有最重要的属性,这样就解决了完备算法约简率低的问题.结合该方法并在分析对象集增量与差别矩阵关系的基础上,证明了增量约简定理,由此提出了一种增量式约简完备算法(CAIR),当新数据加入决策表时,算法可增量构造差别集合.实验结果表明,所提CAIR在大大缩短计算差别集合时间的同时,约简率比非完备算法提高了20.3%,是同条件下完备算法执行效率的13.2倍. 展开更多

关键词 差别矩阵 差别集合 属性约简 完备算法

下载PDF 职称材料

一种改进的基于差别矩阵的属性约简算法 被引量：9

4

作者 刘洋 冯博琴 周江卫 《微电子学与计算机》 CSCD 北大核心 2007年第5期133-135,137,共4页

为解决决策表属性约简完备算法约简质量低的问题,在基于差别矩阵的属性约简完备算法的基础上,引入信息论中信息熵和互信息增益的定义,给出一种启发式属性约简完备方法,通过实例说明启发式信息可以提高完备算法的约简质量,比较不同启发... 为解决决策表属性约简完备算法约简质量低的问题,在基于差别矩阵的属性约简完备算法的基础上,引入信息论中信息熵和互信息增益的定义,给出一种启发式属性约简完备方法,通过实例说明启发式信息可以提高完备算法的约简质量,比较不同启发信息对完备算法的约简质量和约简效率。试验结果表明,采用基于信息论定义的两种启发信息的完备算法约简效率基本一致,该算法较非启发式完备算法有更好的约简质量。 展开更多

关键词 粗糙集 属性约简 差别矩阵 完备算法

下载PDF 职称材料

求解SAT问题的算法的研究进展 被引量：9

5

作者 郭莹 张长胜 张斌 《计算机科学》 CSCD 北大核心 2016年第3期8-17,共10页

SAT问题是研究最广泛的NPC问题之一。由于SAT问题本身的特性,除非P=NP,否则不存在最坏情况下多项式阶时间复杂度的SAT求解算法。因此设计出高效快速的SAT求解算法至今仍是研究热点。首先简要介绍了SAT问题;其次从完备算法、不完备算法... SAT问题是研究最广泛的NPC问题之一。由于SAT问题本身的特性,除非P=NP,否则不存在最坏情况下多项式阶时间复杂度的SAT求解算法。因此设计出高效快速的SAT求解算法至今仍是研究热点。首先简要介绍了SAT问题;其次从完备算法、不完备算法和组合算法3个角度总结了新近的研究进展,深入分析了已有算法解决SAT问题的基本流程,并从适用问题类别、算法特点、求解效率等方面对各类先进的求解器进行了对比分析;最后讨论了求解SAT问题的算法面临的挑战,并对下一步研究工作进行了展望。 展开更多

关键词 SAT问题 完备算法 不完备算法 组合算法

下载PDF 职称材料

基于简化差别矩阵的完备属性约简算法 被引量：9

6

作者 徐章艳 杨炳儒 宋威 《计算机工程与应用》 CSCD 北大核心 2006年第26期167-169,197,共4页

由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出IND(C),故设计了一个... 由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出IND(C),故设计了一个较好的求IND(C)的算法,其复杂度被降为O(｜C‖U｜)。在此基础上设计了一个完备属性约简算法,其时间复杂度和空间复杂度分别被降为max｛O(｜C｜2(｜U′pos‖U/C｜)),O(｜C‖U｜)｝和max｛O(｜U｜),O(｜C｜(｜U′pos‖U/C｜))｝。 展开更多

关键词 粗糙集 差别矩阵 简化差别矩阵 属性约简 完备算法 复杂度

下载PDF 职称材料

基于差别矩阵的属性约简完备算法 被引量：8

7

作者 蒋瑜 王鹏 +1 位作者 王燮 李永礼 《计算机工程与应用》 CSCD 北大核心 2007年第19期185-187,共3页

分析了传统属性频率函数作为属性重要度的不足,重新定义了属性重要度,提出了一种基于差别矩阵属性重要度的属性约简完备算法,即CRABSA(Complete Reduction Algorithm Basedonthe Significance of Attribute)。该算法采用迭代思想,在每... 分析了传统属性频率函数作为属性重要度的不足,重新定义了属性重要度,提出了一种基于差别矩阵属性重要度的属性约简完备算法,即CRABSA(Complete Reduction Algorithm Basedonthe Significance of Attribute)。该算法采用迭代思想,在每次迭代过程中根据属性重要度SGF(a)选择必要的条件属性加入约简R中。由SGF(a)的定义可知,算法能确保在大多数情况下能得到决策表的最小约简。分析了算法在最坏情况下的时间复杂度,给出了该算法相对Pawlak约简的完备性的证明。 展开更多

关键词 粗糙集 差别矩阵 属性重要度 完备算法

下载PDF 职称材料

简化的二进制差别矩阵属性约简算法的改进 被引量：5

8

作者 桂现才 《计算机工程与设计》 CSCD 北大核心 2007年第16期3971-3973,共3页

目前,基于二进制差别矩阵的属性约简算法有以下不足:所得到的属性约简与基于正区域的属性约简不一致。文献[7]中给出一种基于简化的二进制差别矩阵的快速属性约简算法,但该算法不完备。分析了算法不完备的原因,在此基础上,提出了一种改... 目前,基于二进制差别矩阵的属性约简算法有以下不足:所得到的属性约简与基于正区域的属性约简不一致。文献[7]中给出一种基于简化的二进制差别矩阵的快速属性约简算法,但该算法不完备。分析了算法不完备的原因,在此基础上,提出了一种改进的完备算法,该算法的时间复杂度为max(O(∣C||U∣),O(∣C∣2∣U pos||U/C))。 展开更多

关键词 属性约简 正区域 决策表 简化的二进制差别矩阵 完备算法

下载PDF 职称材料

最大可满足性问题的算法研究综述 被引量：3

9

作者 何琨 郑迥之 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2022年第2期82-95,共14页

最大可满足性问题(maximum satisfiability,MaxSAT)是一个著名的、具有NP难度的组合优化问题.本研究总结了近年来求解最大可满足性问题的各类算法.首先,给出了最大可满足性问题的定义;然后,基于完备算法和非完备算法两个类型,对求解Max... 最大可满足性问题(maximum satisfiability,MaxSAT)是一个著名的、具有NP难度的组合优化问题.本研究总结了近年来求解最大可满足性问题的各类算法.首先,给出了最大可满足性问题的定义;然后,基于完备算法和非完备算法两个类型,对求解MaxSAT的各类算法进行了综述.其中完备算法包括分支定界算法和迭代调用可满足性问题求解器的算法,非完备算法包括近似算法、基于最小校正子集的算法和局部搜索算法;最后,分析和对比了各类求解算法的优劣,并对最大可满足性问题求解所面临的挑战及可能的研究方向进行了讨论和展望. 展开更多

关键词 最大可满足性问题 NP难度 组合优化 完备算法 非完备算法

原文传递

基于差别矩阵的完备属性约简算法 被引量：4

10

作者 杨波 徐章艳 舒文豪 《计算机工程》 CAS CSCD 北大核心 2011年第16期51-53,共3页

基于差别矩阵思想的属性约简算法需要求出决策表的差别矩阵,然而差别矩阵的求取不但费时而且占用大量的存储空间。为此,提出一种基于差别矩阵中非空对象个数的改进属性约简算法。在利用差别矩阵思想的同时不生成差别矩阵,并给出属性重... 基于差别矩阵思想的属性约简算法需要求出决策表的差别矩阵,然而差别矩阵的求取不但费时而且占用大量的存储空间。为此,提出一种基于差别矩阵中非空对象个数的改进属性约简算法。在利用差别矩阵思想的同时不生成差别矩阵,并给出属性重要度的定义及其快速计算公式,只需要U'POS和U'NEG就能计算出属性重要度。实例分析证明,该算法能节省计算时间,求出最小属性约简。 展开更多

关键词 粗糙集 简化决策表 差别矩阵 属性约简 完备算法

下载PDF 职称材料

基于差别矩阵的高效属性约简算法 被引量：2

11

作者 张娟 蒋瑜 +1 位作者 聂华北 李永礼 《武汉理工大学学报》 CAS CSCD 北大核心 2010年第23期145-149,共5页

针对现有粗糙集属性约简算法的不足,提出了一种基于差别矩阵的属性约简新算法。算法的构造借助于差别矩阵,结合集合运算,采用迭代的思想,利用完备优化算子,最后得到决策表的一个完备约简,有效地降低了约简算法的时间复杂度。仿真实验结... 针对现有粗糙集属性约简算法的不足,提出了一种基于差别矩阵的属性约简新算法。算法的构造借助于差别矩阵,结合集合运算,采用迭代的思想,利用完备优化算子,最后得到决策表的一个完备约简,有效地降低了约简算法的时间复杂度。仿真实验结果显示,其产生的约简与现有算法产生的最优约简一致,进一步表明了新算法的高效性与完备性。 展开更多

关键词 粗糙集 差别矩阵 属性约简 完备算法

原文传递

基于核与改进的条件区分能力的反向删除属性约简算法 被引量：2

12

作者 冯卫兵 张梅 《计算机应用与软件》 CSCD 2016年第5期252-255,292,共5页

粗糙集理论的布尔矩阵表示形式具有直观、易于理解的优点,它的引入为研究粗糙集的理论提供了一个新的思路。在对布尔矩阵性质研究的基础上,针对已有的基于布尔矩阵算法没有考虑到核属性在浓缩布尔矩阵时的重要性的不足,将属性重要性与... 粗糙集理论的布尔矩阵表示形式具有直观、易于理解的优点,它的引入为研究粗糙集的理论提供了一个新的思路。在对布尔矩阵性质研究的基础上,针对已有的基于布尔矩阵算法没有考虑到核属性在浓缩布尔矩阵时的重要性的不足,将属性重要性与改进的条件区分能力相结合,提出基于核与改进的条件区分能力的属性约简算法,借助反向删除确保约简集的完备性。实例表明改进后的算法在条件区分能力上更加准确,并且使约简结果更具有较强的完备性。 展开更多

关键词 布尔矩阵 条件区分能力 属性约简 完备算法

下载PDF 职称材料

基于系统熵的属性约简的简化差别矩阵方法 被引量：2

13

作者 王熊彬 郑雪峰 徐章艳 《计算机应用研究》 CSCD 北大核心 2009年第7期2460-2464,共5页

基于系统熵的属性约简是一种新型的属性约简。该模型由于同时考虑了条件属性集和决策属性集对决策表的分类能力,它是一种考虑较周全的属性约简模型。为设计高效的属性约简算法,首先引入简化差别矩阵,同时给出了基于该简化差别矩阵的属... 基于系统熵的属性约简是一种新型的属性约简。该模型由于同时考虑了条件属性集和决策属性集对决策表的分类能力,它是一种考虑较周全的属性约简模型。为设计高效的属性约简算法,首先引入简化差别矩阵,同时给出了基于该简化差别矩阵的属性约简定义,并证明该定义与基于系统熵的属性约简定义等价;然后用简化差别矩阵设计了一个基于系统熵的完备属性约简算法;最后用实例说明了新算法。 展开更多

关键词 粗糙集 系统熵 简化差别矩阵 属性约简 完备算法 复杂度

下载PDF 职称材料

基于动态奖惩的分支策略的SAT完备算法 被引量：2

14

作者 刘燕丽 徐振兴 熊丹 《计算机应用》 CSCD 北大核心 2017年第12期3487-3492,共6页

针对学习子句数量有限或相似度高导致历史信息有限、搜索树不平衡的问题,提出了基于动态奖惩的分支策略。首先,对每次单子句传播的变元进行惩罚,依据变元是否产生冲突和产生冲突的间隔,确立不同的惩罚函数;其次,在学习阶段,利用学习子... 针对学习子句数量有限或相似度高导致历史信息有限、搜索树不平衡的问题,提出了基于动态奖惩的分支策略。首先,对每次单子句传播的变元进行惩罚,依据变元是否产生冲突和产生冲突的间隔,确立不同的惩罚函数;其次,在学习阶段,利用学习子句确定对构造冲突有益的变元,非线性增加它们的活跃度;最后,选择活跃度最大的变元作为新分支变元。在glucose3.0算法基础上,完成了改进的动态奖惩算法——AP7。实验结果表明,相比glucose3.0算法,AP7算法的剪枝率提高了14.2%~29.3%,少数算例剪枝率的提高可达51%,且改进后的AP7算法相比glucose3.0算法,运行时间缩短了7%以上。所提分支策略可以有效降低搜索树规模,使搜索树更加平衡,减少计算时间。 展开更多

关键词 NP完全问题 可满足性问题 冲突驱动子句学习 完备算法 分支策略

下载PDF 职称材料

粗糙集最小约简完备算法 被引量：2

15

作者 刘琼 《微计算机信息》 2009年第22期249-250,共2页

属性约简是粗糙集理论重要研究内容之一,然而求取所有约简与最小约简的时间复杂度为指数级,在大量或海量数据分析时,算法的可行性将面临巨大挑战。文中分析了现在差别矩阵最小约简算法的缺陷,以改进属性频度为启发式信息给出了最小约简... 属性约简是粗糙集理论重要研究内容之一,然而求取所有约简与最小约简的时间复杂度为指数级,在大量或海量数据分析时,算法的可行性将面临巨大挑战。文中分析了现在差别矩阵最小约简算法的缺陷,以改进属性频度为启发式信息给出了最小约简快速完备方法。理论分析结果表明,算法的效率得到了极大的改进。 展开更多

关键词 粗糙集 差别矩阵 最小约简 完备算法

下载PDF 职称材料

一个求解SAT问题的新算法

16

作者 张银丹 张浩军 《电脑知识与技术（过刊）》 2010年第15期4294-4296,共3页

基于对完备算法和非完备算法的研究,结合完备算法能够进行完备求解和不完备算法能够以较快速度进行求解的优点。提出一种新的求解SAT问题的算法——对子句分组、对分组求解的算法。该算法完备地对SAT子句分组,同时在分组求解时使用局部... 基于对完备算法和非完备算法的研究,结合完备算法能够进行完备求解和不完备算法能够以较快速度进行求解的优点。提出一种新的求解SAT问题的算法——对子句分组、对分组求解的算法。该算法完备地对SAT子句分组,同时在分组求解时使用局部搜索方法以较快的速度求解。经过实验验证,结果表明该方法能明显提高求解效率。 展开更多

关键词 完备算法 非完备算法 局部搜索 SAT问题 效率

下载PDF 职称材料

基于学习子句删除策略的SAT求解器分支策略 被引量：1

17

作者 王钇杰 徐扬 吴贯锋 《计算机科学》 CSCD 北大核心 2021年第11期294-299,共6页

对于SAT求解器,目前流行的分支变量决策策略大多是基于冲突的变量活跃度评估算法,选择具有最大活性的未赋值变量作为决策变量,优先解决最近的冲突。但是,它们都忽略了包含决策变量的子句数目对布尔约束传播(BCP)的影响。针对此问题,提... 对于SAT求解器,目前流行的分支变量决策策略大多是基于冲突的变量活跃度评估算法,选择具有最大活性的未赋值变量作为决策变量,优先解决最近的冲突。但是,它们都忽略了包含决策变量的子句数目对布尔约束传播(BCP)的影响。针对此问题,提出了一种基于学习子句删除策略的分支变量决策策略(VDALCD),在删除学习子句的同时减小被删除子句中变量的活跃度。基于VDALCD策略分别对Glucose4.1,MapleLCMDistChronoBT-DL-v2.1进行改进,形成了求解器Glucose4.1_VDALCD和Maple-DL_VDALCD。以2018年、2019年SAT国际竞赛题为基准测试例,将改进版本与原版本求解器进行比较。实验结果表明,在2018年的例子测试中,Gluose4.1_VDALCD比Gluose4.1多求出26个例子,增加了15.5%。在2019年的例子测试中,Maple-DL_VDALCD比MapleLCMDistChronoBT-DL-v2.1多求出17个例子,增加了7.6%。 展开更多

关键词 活跃度 学习子句 可满足性问题 学习子句删除策略 完备算法

下载PDF 职称材料

基于奖励机制的SAT求解器分支策略 被引量：1

18

作者 沈雪 陈树伟 艾森阳 《计算机科学》 CSCD 北大核心 2020年第7期42-46,共5页

分支决策是CD CL(Conflict Driven Clause Learning)求解器一个十分关键的环节,一个好的分支策略可以减少分支决策次数进而提高SAT求解器的效率。目前,先进的分支策略大都结合了冲突分析过程,但分支策略对参与冲突分析的变量奖励方法有... 分支决策是CD CL(Conflict Driven Clause Learning)求解器一个十分关键的环节,一个好的分支策略可以减少分支决策次数进而提高SAT求解器的效率。目前,先进的分支策略大都结合了冲突分析过程,但分支策略对参与冲突分析的变量奖励方法有所不同,因此所挑选出的决策变量会有所差异。文中考虑到决策变量总是在未赋值变量中选取的这一重要事实,在EVSIDS(Exponential Variable State Independent Decaying Sum)分支策略的基础上提出了一种新的分支策略,称为基于奖励机制的分支策略(简称RACT分支策略)。RACT分支策略对冲突分析中被撤销赋值的变量再次给予奖励,以增大未赋值变量中频繁参与冲突分析的变量被选择为分支变量的可能性。最后,将所提出的分支策略嵌入到Glucose4.1求解器中以形成新的求解器Glucose4.1+RACT,以2017年SAT竞赛中的350个实例为实验数据集来测试RACT分支策略的有效性。实验结果表明,求解器Glucose4.1+RACT比原版求解器能求解出更多的实例个数,尤其在求解可满足实例的个数上增加了13.5%,此外在求解350个竞赛实例上所花费的总时间较Glucose4.1减少了3.9%,以上实验数据均说明所提分支策略可以有效减少搜索树的分支决策次数并给出正确的搜索空间,进而提高了SAT求解器的求解能力。 展开更多

关键词 可满足性问题 完备算法 冲突驱动子句学习 回溯搜索 分支策略

下载PDF 职称材料

一种基于差别矩阵属性约简的完备算法 被引量：1

19

作者 李小伟 王娜 李永礼 《微机发展》 2005年第11期144-146,150,共4页

为获取一个较优的属性约简集,在对粗糙集中基于差别矩阵的属性约简算法研究的基础上,文中提出了一种新的属性约简算法。该算法对由差别矩阵得到的属性差别集进行运算,得到一种集合内元素之间没有包含关系的新集合,在分析该集合性质的基... 为获取一个较优的属性约简集,在对粗糙集中基于差别矩阵的属性约简算法研究的基础上,文中提出了一种新的属性约简算法。该算法对由差别矩阵得到的属性差别集进行运算,得到一种集合内元素之间没有包含关系的新集合,在分析该集合性质的基础上,给出针对该集合的一个较优属性约简集。最后对时间复杂度进行了分析,并给出了完备性证明。 展开更多

关键词 粗糙集 差别矩阵 完备算法 属性约简

下载PDF 职称材料

回路双三角逆M矩阵完备的判定定理 被引量：1

20

作者 汤淑英 《西北师范大学学报（自然科学版）》 CAS 北大核心 2010年第3期28-30,共3页

循环双三角是一个有向图,它包含两个3结构周期.研究了逆M矩阵的图在该有向图中的完备问题.对每个周期所包含的所有指定的顶点以及所包含的未指定的顶点都进行了探讨;同时给出了完备定律和运算方法.

关键词 部分逆M矩阵 完备算法 双三角循环

下载PDF 职称材料