广义信息系统的属性约简

把完备信息系统、不完备信息系统、序信息系统、覆盖信息系统等常见信息系统统称为广义信息系统,采用新的知识表达形式将其知识结构进行统一表示,特别是将覆盖信息系统纳入了广义信息系统的框架之中。在广义信息系统中引入粒度熵的概念,对属性的重要性给出度量;在此基础上,提出一种广义信息系统属性约简的启发式算法,进而得到广义信息系统的知识约简,并给出了若干算例。

基于二跳独立邻居覆盖的极小连通支配集构造算法

提出两个基于二跳独立邻居覆盖的无线传感器网络极小连通支配集构造算法.在两个构造算法中,已选择的支配节点推举新的支配节点,并要求新推举的支配节点完全覆盖该支配节点的二跳独立邻居节点.第一个算法不考虑能量因子,以被推举节点的一跳和部分二跳独立邻居节点集合大小之和最大作为新支配节点推举依据;第二个算法以被推举节点剩余能量与其覆盖的二跳独立邻居节点个数之商最大化作为推举依据.所提出的算法具有较好的时间复杂度和消息复杂度,且均为O(n),第一个算法的性能比为O(n^(1/2)).仿真结果表明,本文提出的算法可构造较小规模的连通支配集以及延长网络生命时间.

关于边控制集的一些结论

令 G=(V,E)是一个图 ,M是边集 E(G)的子集 .如果有 e∈E(G) /M,e至少与 M中一条边相连 ,则称 M为图 G的边控制集 .进一步 ,若 M是匹配 ,则称 M为图 G独立边控制集 .本文给出关于边控制集的一些结论 .(1 )设图 H,S是两个连通图 .且 H,S∈ Ж,γe(S) =1 ,M和 M′={uv}分别是图 H和 S的唯一最小边控制集 ,其中 S是图 1中的 (G1 ,G2 ,G3,G4 )四个图之一 .对任何点 x∈V(S) -{u,v},y∈V(H) -V(M) .令 G=H(y=x) S,则 G∈Ж.(2 )如果连通图 G≠K2 ,G∈ Ж,γe(G) =k,则存在 G的两个连通子图 H,S和某两个正整数 l,m使 H∈ Ж,S∈Ж,且 γe(H) =k-l,γe(S) =l,G≌H(yi=xi) S,其中 l i m.

基于分离优势覆盖集的Pythagorean模糊决策信息系统的属性约简

讨论了基于分离优势覆盖集的Pythagorean模糊决策信息系统的属性约简问题.首先基于优势关系,在Pythagorean模糊决策信息系统中给出了优势覆盖集、分离优势覆盖集、D分离优势覆盖集等概念.进而利用分离优势覆盖集、D分离优势覆盖集对Pythagorean模糊决策信息系统进行约简.最后,将提出的约简算法与其他约简算法进行比较,验证了所提出算法的有效性和优越性.

粘贴模型在两类特殊问题中的改进算法研究

为了避免对初始解空间的复杂过滤,同时充分利用粘贴模型在生物操作过程中的优越性,设计了基于粘贴模型的改进DNA算法。对于最小支配集问题和最小顶点覆盖问题,算法设计可以直接生成可满足解的解空间,使解空间的规模小于O(2n),从而简化最优解的筛选。通过具体实例说明了该算法的可行性。

信息系统上的优势关系与保序关系

经典的Pawlak粗集理论建立在由等价关系对对象集划分的基础上,本文研究由优势关系代替等价关系引起的一系列结果.优势关系生成对象集上的覆盖;保序关系生成对象集幂集上的划分.并得到了优势约简与保序约简之间的关系.

一种求解最小支配集问题的置信传播算法

最小支配集问题(MDS)是图论中的一个重要问题,在网络资源配置中有广泛的应用。上述问题是一个NP难问题,传统的启发式算法求解最小支配集问题时速度慢,且易于陷入局部最优解。将上述问题原有的无向图转化为对应的因子图,基于因子图构建最小支配集问题的线性规划方程,将方程代入图模型(GM)中,设计了一种求解最小支配集问题的置信传播算法。当算法收敛时,获得每个节点取值的边缘概率,利用边缘概率高概率地决定最小支配集节点。在随机生成的无向图上进行数值实验,结果表明,算法有效。