共查询到20条相似文献,搜索用时 31 毫秒
1.
杨智应 《计算机应用与软件》2009,26(3)
Franco等给出一个基于平均度数的最小3-击中集问题的贪心算法,并给出算法返回击中集规模的上界.首先将其算法推广成为求解最小k-击中集问题的贪心算法HGREEDY1(A,C),并类似地给出算法返回击中集规模的上界;然后给出基于最大度数的贪心算法HGREEDY2(A,C),并证明算法HGREEDY2(A,C)在给定条件下返回的击中集规模上界优于算法HGREEDY1(A,C);另外设计了用于求解最小k-击中集的随机算法RH(A,C),并对其性能进行平均分析;在此基础上设计一个求解最小k-击中集的随机近似算法并讨论其性质. 相似文献
2.
在SINR模型下研究了无线网络中与链路调度密切相关的两个重要的NP-完全问题:最大链路独立集( Maximum Independent Set of Links,MISL)和最大带权链路独立集( Maximum Weighted Independent Set of Links,MWISL),给出了对这两个问题有好的实际性能保障的有效启发式算法,从理论上证明了算法的正确性,并通过仿真验证了算法的有效性。对于MISL问题,在MTIR算法( Yang等人于2010年提出)的基础上,得到了性能更优的启发式算法MTBR;对于MWISL问题给出的有效启发式算法,比近似算法PMWISL( Wan等人于2011年提出)的性能有了较大的提高。 相似文献
3.
4.
5.
描述逻辑εL混合循环术语集的LCS和MSC推理 总被引:2,自引:0,他引:2
分析了描述逻辑循环术语集的研究现状和存在的问题,在F.Baader工作的基础上进一步研究了描述逻辑εL混合循环术语集的LCS(least common subsumer)和MSC(most specific concept)推理问题.给出了εL混合循环术语集的语法和语义.针对εL混合循环术语集LCS和MSC推理的需要,提出了TBox-完全的概念,并重新定义了描述图.使用描述图和TBox-完全给出了最大不动点语义下εL混合循环术语集LCS和MSC的推理算法,证明了推理算法的正确性,并证明了推理算法是多项式时间复杂的.该推理算法为εL混合循环术语集的LCS和MSC推理提供了理论基础. 相似文献
6.
最大流问题在许多领域有广泛的应用,然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题.对一个给定的有向网络,文中提出一种收缩邻居节点集的方法(CNA)求解其最大流.该方法通过收缩邻居节点集有效降低网络规模,使经典算法及改进算法可直接使用.首先给出收缩邻居节点集的条件,接着给出依据收缩条件构建目标网络的算法,最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似.实验结果表明CNA不仅平均能将目标网络的规模降至初始网络的一半,且能以较小的误差求得初始网络的最大流. 相似文献
7.
提出了对绩效管理关键绩效指标(KPI)的确定中挖掘最大频繁集的一种方法。该方法采用了位图数据格式;根据绩效管理中数据的特点,由用户的需求导出FP-tree。通过分析Apriori方法和FP-growth方法的优缺点,结合各种有效剪枝技术,对传统挖掘算法进行了改进,加速了FP-tree上的最大频繁集的生成,以适应绩效管理的应用环境。最后给出了实例以显示处理过程及效率。 相似文献
8.
描述逻辑εL混合循环术语集的LCS和MSC推理 总被引:1,自引:0,他引:1
分析了描述逻辑循环术语集的研究现状和存在的问题,在F.Baader工作的基础上进一步研究了描述逻辑εL混合循环术语集的LCS(least common subsumer)和MSC(most specific concept)推理问题.给出了εL混合循环术语集的语法和语义.针对εL混合循环术语集LCS和MSC推理的需要,提出了TBox-完全的概念,并重新定义了描述图.使用描述图和TBox-完全给出了最大不动点语义下εL混合循环术语集LCS和MSC的推理算法,证明了推理算法的正确性,并证明了推理算法是多项式时间复杂的.该推理算法为(L混合循环术语集的LCS和MSC推理提供了理论基础. 相似文献
9.
10.
11.
针对最大频繁项目集挖掘算法(DMFIA)当候选项目集维数高而最大频繁项目集维数较低的情况下要产生大量的候选项目集的缺点,提出了一种改进的基于频繁模式树(FP-tree)结构的最大频繁项目集挖掘算法--FP-MFIA。该算法根据FP-tree的项目头表,采用自底向上的搜索策略逐层挖掘最大频繁项目集,从而加速每次对候选集计数的操作。在挖掘时根据每层的条件模式基产生维数较低的非频繁项目集,尽早对候选项目集进行剪枝和降维,可大量减少候选项目集的数量。同时在挖掘时充分利用最大频繁项集的性质,减少搜索空间。通过算法在不同支持度下挖掘时间的对比可知,算法FP-MFIA在最小支持度较低的情况下时间效率是DMFIA以及基于降维的最大频繁模式挖掘算法(BDRFI)的2倍以上,说明FP-MFIA在候选集维数较高的时候优势明显。 相似文献
12.
13.
求解图的最大独立集的一种算法 总被引:5,自引:0,他引:5
如何寻找图的最大独立集这个问题是一个古老的难题。文章从图论的基本概念入手 ,得到了一种基于图的邻接矩阵的寻找图的极大独立集和最大独立集的算法 ,并得到其算法复杂度为 O(nn!/(m!(n - m) !) ) 相似文献
14.
区别于传统对带权最大独立集问题的研究,本文从新的角度首先提出了边带权最大独立集问题,给出了完整的定义,证明了它的NP-Complete难解性。并且通过对问题结构的研究,给出了一个近似度为1/[Δ′ 1/3]的近似算法,Δ′为图中点的最大度数。 相似文献
15.
16.
S-粗集(singular rough sets)是把动态特征引入到Z.Pawlak粗集中对其加以改进而提出的,S-粗集具有动态特征.S-粗集具有3种形式:单向S-粗集(one direction singular rough sets)、单向S-粗集对偶(dual of one direction singular rough sets)与双向S-粗集(two direction singular rough sets);在一定条件下,单向S-粗集、单向S-粗集对偶与双向S-粗集被还原成Z.Pawlak粗集.利用单向S-粗集和单向S-粗集对偶给出具有属性析取特征的动态数据智能挖掘与应用;属性析取是数据具有的逻辑特征之一.主要结果是:利用单向S-粗集、单向S-粗集对偶结构,给出属性析取萎缩-扩张特征的动态数据生成与它的属性析取萎缩-扩张关系;给出数据推理与推理模型;利用数据推理给出动态数据智能挖掘定理;利用这些理论结果,给出动态数据智能挖掘-智能认知的应用. 相似文献
17.
S-粗集与数据挖掘单位圆特征 总被引:4,自引:2,他引:2
给出单向S-粗集(one direction singular rough sets)、单向S-粗集对偶(dual of one direction singular rough sets)的结构。单向S-粗集与单向S-粗集对偶是改进Z.Pawlak粗集得到的,单向S-粗集与单向S-粗集对偶具有动态特性。给出单向S-粗集、单向S-粗集对偶与Z.Pawlak粗集的关系。S-粗集具有三类形式:单向S-粗集、单向S-粗集对偶、双向S-粗集,利用单向S-粗集、单向S-粗集对偶,给出数据内挖掘、数据外挖掘概念,给出数据内挖掘的外同心圆定理、数据外挖掘的内同心圆定理,并给出其应用。S-粗集是粗集理论与应用研究的新分支。 相似文献
18.
函数s一粗集,函数粗集与信息系统规律拆分一合成 总被引:2,自引:1,他引:1
给出函数单向导粗集(function one direction singular rough sets)、函数单向导粗集对偶Cdual of function one direction singular rough sets)、函数双向S粗集(function two direction singular rough sets)与函数粗集(function rough sets)。它们都是把函数概念引入到S粗集中,改进S粗集得到的。函数粗集是把函数概念引入到Z. Pawlak粗集中,改进Z. Pawlak粗集得到的。函数单向导粗集、函数单向S粗集对偶、函数双向S粗集是函数导粗集的三类形式。给出函数导粗集与导粗集的关系;给出函数粗集与Z. Pawlak粗集的关系;给出函数S粗集与函数粗集的关系。利用这些结果,给出函数的区间离散与有限元素集的生成、函数离散一元素集合生成原理;给出函数导粗集生成的信息规律、函数等价类动态特性一属性补充与删除原理;给出数据拆分一合成原理、信息规律动态拆分一合成的属性特征;给出信息规律动态拆分一合成不变性原理;利用这些概念与结果,给出信息规律拆分一合成与信息图像嵌入一分离的应用,给出嵌入信息图像的分离一辫识。函数导粗集、函数粗集是粗集理论与应用研究中的一个新的研究方向。 相似文献
19.
粗糙集是1982年由Pawlak教授提出的解决集合边界不确定的重要方法,它通过两个精确的上、下近似集作为边界线来刻画目标集合(概念)X的不确定性,但它没有给出如何用已知的知识基(知识粒)来精确或近似地描述边界不确定的目标集合(概念)X的方法.首先给出了集合之间的相似度概念,然后分析了分别用上近似集R(X)和下近似集R(X)作为目标集合(概念)X近似描述的不足,提出了在已有知识基(粒)空间下寻找目标集合(概念)X的近似集的方法,并分析了用R0.5(X)作为X(概念)的近似集的优越性.最后讨论了不同知识粒度空间下R0.5(X)与X的相似度随知识粒度的变化关系.从新的角度提出了目标集合(概念)X近似集的构造方法,促进了粗糙集模型的发展. 相似文献