最小k-击中集问题的一个随机近似算法

Franco等给出一个基于平均度数的最小3-击中集问题的贪心算法,并给出算法返回击中集规模的上界.首先将其算法推广成为求解最小k-击中集问题的贪心算法HGREEDY1(A,C),并类似地给出算法返回击中集规模的上界;然后给出基于最大度数的贪心算法HGREEDY2(A,C),并证明算法HGREEDY2(A,C)在给定条件下返回的击中集规模上界优于算法HGREEDY1(A,C);另外设计了用于求解最小k-击中集的随机算法RH(A,C),并对其性能进行平均分析;在此基础上设计一个求解最小k-击中集的随机近似算法并讨论其性质.     

SINR模型下链路调度问题的启发式算法

在SINR模型下研究了无线网络中与链路调度密切相关的两个重要的NP-完全问题：最大链路独立集( Maximum Independent Set of Links,MISL)和最大带权链路独立集( Maximum Weighted Independent Set of Links,MWISL),给出了对这两个问题有好的实际性能保障的有效启发式算法,从理论上证明了算法的正确性,并通过仿真验证了算法的有效性。对于MISL问题,在MTIR算法( Yang等人于2010年提出)的基础上,得到了性能更优的启发式算法MTBR;对于MWISL问题给出的有效启发式算法,比近似算法PMWISL( Wan等人于2011年提出)的性能有了较大的提高。     

约束最大频繁项目集的增量式更新算法

发现约束频繁(约束最大频繁)项目集是多种数据挖掘应用中的关键问题，目前已有许多算法可用于发现约束频繁(约束最大频繁)项目集，而对约束频繁(约束最大频繁)项目集维护问题的研究工作却很少。因此，需要设计高效的算法来更新、维护和管理已挖掘出来的约束频繁(约束最大频繁)项目集。为此。该文提出了一种快速的增量式更新约束最大频繁项目集算法IUACMFI，并举例说明了算法的执行过程。     

伪随机遥控指令码集的选择

本文论述了所有达到Baumert-王-welch(BWW)下界的伪随机序列可用于构成遥控指 令码;推导出这类码集最大容错数的一般公式.得出了达到BWW界的伪随机序列的平移等 价序列构成的指令码集在抗干扰性能上是最佳循环码集的结论.给出了序列及其反序列的平 移等价序列共同做为遥控指令码集的条件.     

描述逻辑εL混合循环术语集的LCS和MSC推理

分析了描述逻辑循环术语集的研究现状和存在的问题,在F.Baader工作的基础上进一步研究了描述逻辑εL混合循环术语集的LCS(least common subsumer)和MSC(most specific concept)推理问题.给出了εL混合循环术语集的语法和语义.针对εL混合循环术语集LCS和MSC推理的需要,提出了TBox-完全的概念,并重新定义了描述图.使用描述图和TBox-完全给出了最大不动点语义下εL混合循环术语集LCS和MSC的推理算法,证明了推理算法的正确性,并证明了推理算法是多项式时间复杂的.该推理算法为εL混合循环术语集的LCS和MSC推理提供了理论基础.     

收缩邻居节点集方法求解有向网络的最大流问题

最大流问题在许多领域有广泛的应用,然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题.对一个给定的有向网络,文中提出一种收缩邻居节点集的方法(CNA)求解其最大流.该方法通过收缩邻居节点集有效降低网络规模,使经典算法及改进算法可直接使用.首先给出收缩邻居节点集的条件,接着给出依据收缩条件构建目标网络的算法,最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似.实验结果表明CNA不仅平均能将目标网络的规模降至初始网络的一半,且能以较小的误差求得初始网络的最大流.     

基于绩效管理的最大频繁模式挖掘研究

提出了对绩效管理关键绩效指标(KPI)的确定中挖掘最大频繁集的一种方法。该方法采用了位图数据格式;根据绩效管理中数据的特点,由用户的需求导出FP-tree。通过分析Apriori方法和FP-growth方法的优缺点,结合各种有效剪枝技术,对传统挖掘算法进行了改进,加速了FP-tree上的最大频繁集的生成,以适应绩效管理的应用环境。最后给出了实例以显示处理过程及效率。     

描述逻辑εL混合循环术语集的LCS和MSC推理

分析了描述逻辑循环术语集的研究现状和存在的问题,在F.Baader工作的基础上进一步研究了描述逻辑εL混合循环术语集的LCS(least common subsumer)和MSC(most specific concept)推理问题.给出了εL混合循环术语集的语法和语义.针对εL混合循环术语集LCS和MSC推理的需要,提出了TBox-完全的概念,并重新定义了描述图.使用描述图和TBox-完全给出了最大不动点语义下εL混合循环术语集LCS和MSC的推理算法,证明了推理算法的正确性,并证明了推理算法是多项式时间复杂的.该推理算法为(L混合循环术语集的LCS和MSC推理提供了理论基础.     

相继干扰抵消的无线网络基于遗传算法的容量估计

相继干扰抵消(SIC)是一种有效对抗干扰的多包接收技术.在支持SIC的无线网络中,研究了最大容量即最大化并发传输数目的问题.给出了刻画SIC顺序检测特性的干扰模型,并据此提出判断链路集是否可并发的有效算法.由于最大容量问题为NP-hard的,而寻找最大并发链路集是全局优化的问题.研究了基于遗传算法的近似机制.详细讨论了遗传算法的设计并探讨了关键参数的设置,算法性能通过大量仿真实验得到了验证.     

多面体上彷射系统可达性问题研究

研究n维多面体上自治仿射系统的可达性问题. 目的在于得到多面体上最大正不变集和每个极大面的反向可达集(吸引域). 研究最大稳定不变仿射子空间, 并给出不变集和吸引域的性质, 最后通过分割算法确定两者的边界.     

改进的基于频繁模式树的最大频繁项集挖掘算法——FP-MFIA

针对最大频繁项目集挖掘算法(DMFIA)当候选项目集维数高而最大频繁项目集维数较低的情况下要产生大量的候选项目集的缺点,提出了一种改进的基于频繁模式树(FP-tree)结构的最大频繁项目集挖掘算法--FP-MFIA。该算法根据FP-tree的项目头表,采用自底向上的搜索策略逐层挖掘最大频繁项目集,从而加速每次对候选集计数的操作。在挖掘时根据每层的条件模式基产生维数较低的非频繁项目集,尽早对候选项目集进行剪枝和降维,可大量减少候选项目集的数量。同时在挖掘时充分利用最大频繁项集的性质,减少搜索空间。通过算法在不同支持度下挖掘时间的对比可知,算法FP-MFIA在最小支持度较低的情况下时间效率是DMFIA以及基于降维的最大频繁模式挖掘算法(BDRFI)的2倍以上,说明FP-MFIA在候选集维数较高的时候优势明显。     

基于集对分析OWA算子信息决策排序方法

研究了以集对数给出的信息排序问题,给出了一种集对数有序加权平均(SPAOWA)算子的信息决策排序方法并进行了算例分析。     

求解图的最大独立集的一种算法

如何寻找图的最大独立集这个问题是一个古老的难题。文章从图论的基本概念入手 ,得到了一种基于图的邻接矩阵的寻找图的极大独立集和最大独立集的算法 ,并得到其算法复杂度为 O(nn!/(m!(n - m) !) )     

边带权最大独立集问题及其近似算法

区别于传统对带权最大独立集问题的研究，本文从新的角度首先提出了边带权最大独立集问题，给出了完整的定义，证明了它的NP-Complete难解性。并且通过对问题结构的研究，给出了一个近似度为1/[Δ′ 1/3]的近似算法，Δ′为图中点的最大度数。     

基于闭环DNA计算的最大独立集问题的算法

提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验,实现简捷、可靠。     

具有属性析取萎缩-扩张特征的动态数据智能挖掘

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-粗集对偶结构,给出属性析取萎缩-扩张特征的动态数据生成与它的属性析取萎缩-扩张关系;给出数据推理与推理模型;利用数据推理给出动态数据智能挖掘定理;利用这些理论结果,给出动态数据智能挖掘-智能认知的应用.     

S-粗集与数据挖掘单位圆特征

给出单向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-粗集是粗集理论与应用研究的新分支。     

函数s一粗集，函数粗集与信息系统规律拆分一合成

给出函数单向导粗集(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粗集与函数粗集的关系。利用这些结果,给出函数的区间离散与有限元素集的生成、函数离散一元素集合生成原理;给出函数导粗集生成的信息规律、函数等价类动态特性一属性补充与删除原理;给出数据拆分一合成原理、信息规律动态拆分一合成的属性特征;给出信息规律动态拆分一合成不变性原理;利用这些概念与结果,给出信息规律拆分一合成与信息图像嵌入一分离的应用,给出嵌入信息图像的分离一辫识。函数导粗集、函数粗集是粗集理论与应用研究中的一个新的研究方向。     

粗糙集的近似集

粗糙集是1982年由Pawlak教授提出的解决集合边界不确定的重要方法,它通过两个精确的上、下近似集作为边界线来刻画目标集合(概念)X的不确定性,但它没有给出如何用已知的知识基(知识粒)来精确或近似地描述边界不确定的目标集合(概念)X的方法.首先给出了集合之间的相似度概念,然后分析了分别用上近似集R(X)和下近似集R(X)作为目标集合(概念)X近似描述的不足,提出了在已有知识基(粒)空间下寻找目标集合(概念)X的近似集的方法,并分析了用R0.5(X)作为X(概念)的近似集的优越性.最后讨论了不同知识粒度空间下R0.5(X)与X的相似度随知识粒度的变化关系.从新的角度提出了目标集合(概念)X近似集的构造方法,促进了粗糙集模型的发展.     

点集的多IFS编码

文中首先论述了分形编码方法的发展概况,简单介绍了迭代函数系统(IFS)的理论,然后提出了点集的多IFS的思想,定义了多IFS中仿射变换伴随集的概念并给出了求伴随集的两种方法,在此基础上提出了构造点集的多IFS的算法,最后给出了算法的一维实验结果。