基于域的分布式最小连通支配集的启发式算法

在规模较大且移动较频繁的ad hoc网络中,针对构建树形连通支配集缓慢且网络开销大的问题,提出了基于域的分布式最小连通支配集的启发式算法(ZBCDS).ZBCDS在求得极大独立集的基础上,定义了节点阶势和候选节点的概念,通过判断节点的阶势,优化了域的生成和域边界上连接节点的调整,达到CDS重构快速高效地实现的目的.实验...     

分布式最小连通支配集启发式算法

针对AdHoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7．60pt＋1．4,时间复杂度为O（△^2）,消息复杂度为O（n）,比同类算法优秀。     

基于粗糙集的启发式属性约简算法

对现有启发式属性约简算法进行分析,通过实例说明一般启发式算法求得的相对约简有冗余属性存在的问题.针对这一不足,利用粗糙集理论中的条件熵作为启发信息,来缩小搜索空间,并在算法中加入消除冗余属性的二次约简过程,得到一种改进的启发式属性约简算法.提供了实例分析,验证了该改进算法具有较好的约简效果.     

一种基于Rough集理论的属性约简启发式算法

属性约简是知识发现中的关键问题之一．为了能够有效地获取决策表中属性的最小相对约简，在Rough集理论的基础上构造了一个新的算子，将信息论角度定义的属性的重要性作为启发式信息，来描述在决策表中条件属性所提供的知识对决策属性的影响；并采用宽度优先搜索策略，提出了一种新的属性约简启发式算法．以原始条件属性集为起点并结合算子，通过向属性核的递减式逼近，得到属性的最小相对约简．实例分析表明，该算法能有效地对决策表属性进行约简．     

基于启发式的粗糙集属性约简算法研究

对目前常见的粗糙集属性约简算法进行了研究和总结,在此基础上,针对差别矩阵以及启发式约简算法提出了改进算法,减少算法在计算时所需的时间和空间复杂度,求取最小约简。将改进后的约简算法系统地应用到学生考试成绩分析中,对得到的规则进行科学地评价,找出影响学生成绩的潜在因素,并提出学习建议。通过实际应用表明了改进算法的有效性和可行性。     

禁忌遗传算法求解最小支配集

如何寻找一个网络图的最小支配集是NP难题。分别设计了逆序启发式算法和禁忌搜索算法,并在此基础上提出了禁忌遗传算法（TSGA）用于求解最小支配集;将禁忌搜索和遗传算法结合起来,弥补了彼此的不足,既有效地避免了算法易陷入局部最优解的缺陷,又加快了算法的收敛速度。经对大量随机网络图的测试和对物流网络选址问题的求解,验证了TSGA算法的优越性。     

图支配集问题的粗糙集属性约简方法

探讨粗糙集的属性约简和图的支配集问题之间的联系。通过构造信息系统,将粗糙集的属性约简问题与图的支配集问题相联系,从而把图的支配集问题转化为粗糙集的属性约简问题。首先证明图的极小支配集恰是其构造的信息系统的属性约简,然后提出一种基于信息熵的最小支配集算法,最后通过实例验证该算法的可行性和有效性。     

基于粗糙集的启发式约简算法

本文主要研究基于粗糙集理论的属性约简算法.提出了一种基于属性重要度和相关度的启发式约简算法.并通过算例验证了该算法的可行性和有效性.     

邻域粗糙集的加权依赖度及其启发式约简算法

邻域粗糙集是数值型属性数据处理的有效工具.基于邻域粗糙集,传统依赖度及其约简未考虑邻域覆盖的绝对结构,由此文中建立加权依赖度及其启发式约简算法.首先,提出加权依赖度并得到其度量改进性与粒化单调性,定义相关的属性约简.然后,分析邻域半径的自适应取值,构造基于加权依赖度的启发式约简算法(NWDR).最后,在UCI数据集上进行对比实验,验证加权依赖度的单调性与NWDR的有效性.实验证明,加权依赖度改进传统依赖度的不确定性表示能力,NWDR具有较高的分类准确率与较强的应用适应性.     

基于布尔矩阵表示的粗集属性约简启发式算法

属性约简是粗糙集理论研究中的核心内容之一，现已证明寻找最小约简是NP-hard问题。该文对信息系统中属性的条件区分能力给出定义。在此基础上，提出了一种基于条件区分能力的属性约简的启发式算法。通过实例分析表明，在多数情况下该算法能够得到信息系统的最小约简。     

无向图中连通支配集问题的精确算法

图◢G=（V,E）的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G［S］是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△（1.93n△）的精确◣算法。     

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。     

基于最小生成树的连通支配集求解算法

针对无线网络中的连通支配集(CDS)问题,通过分析得到了CDS的一个重要性质,即简单连通无向图的最小CDS是该图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论,设计了一个新的连通支配集求解算法,实验表明,新算法较前人的算法有更好的性能。     

一种基于粗糙集理论的启发式特征选择算法

在数据分析中,特征选择是能够保留信息的数据约简的一个有效方法。粗糙集理论提供了一种发现所有可能的特征子集的数学工具。提出了一种新的基于粗糙集的启发函数叫做加权平均支持启发函数。该方法的优点是它考虑了可能性规则集的整体质量。也就是说,对所有的决策类,它考虑了规则的加权平均支持度。最后,实例表明该方法是有效的。     

一种高效的最小连通支配集贪心算法

连通支配集（CDS）在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法（GCDS）,依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点;最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法。     

基于模糊邻域粗糙集的启发式属性约简算法

属性约简是机器学习等领域中常用的数据预处理方法。在基于粗糙集理论的属性约简算法中,大多是根据单一的方法来度量属性重要度。为了从多角度对属性达到更为优越的评估效果,首先在已有的模糊邻域粗糙集模型中定义属性依赖度度量,然后根据粒计算理论中知识粒度的概念,在模糊邻域粗糙集模型下提出了模糊邻域粒度度量。由于属性依赖度和知识粒度代表了不同视角的属性评估方法,因此将这两种方法结合起来用于信息系统的属性重要度评估,最后给出一种启发式属性约简算法。实验结果表明,所提出的算法具有较好的属性约简性能。     

A memetic algorithm for minimum independent dominating set problem

Neural Computing and Applications - The minimum independent dominating set (MIDS) problem is a popular NP-hard combinatorial optimization problem which has been widely used in various fields. In...     

基于分明矩阵的属性约简启发式算法

提出了基于分明矩阵的启发式知识约简算法.该算法以分明矩阵中属性出现的频率作为启发信息,通过构造新的决策表,每次选取出现个数最多的属性,直到选取的属性能够保持原决策表的分类能力,此时得到的集合即是一个约简.试验结果表明,该算法在大多数情况下都能够找到最小约简或令人满意的次优解.     

A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

In recent years growing interest in local distributed algorithms has widely been observed. This results from their high resistance to errors and damage, as well as from their good performance, which is independent of the size of the network. A local deterministic distributed algorithm finding an approximation of a Minimum Dominating Set in planar graphs has been presented by Lenzen et al., and they proved that the algorithm returns a 130-approximation of the Minimum Dominating Set. In this article we will show that the algorithm is two times more effective than was previously assumed, and we prove that the algorithm by Lenzen et al. outputs a 52-approximation to a Minimum Dominating Set. Therefore the gap between the lower bound and the approximation ratio of the best yet local deterministic distributed algorithm is reduced by half.     

Distributed minimum dominating set approximations in restricted families of graphs

A dominating set is a subset of the nodes of a graph such that all nodes are in the set or adjacent to a node in the set. A minimum dominating set approximation is a dominating set that is not much larger than a dominating set with the fewest possible number of nodes. This article summarizes the state-of-the-art with respect to finding minimum dominating set approximations in distributed systems, where each node locally executes a protocol on its own, communicating with its neighbors in order to achieve a solution with good global properties. Moreover, we present a number of recent results for specific families of graphs in detail. A unit disk graph is given by an embedding of the nodes in the Euclidean plane, where two nodes are joined by an edge exactly if they are in distance at most one. For this family of graphs, we prove an asymptotically tight lower bound on the trade-off between time complexity and approximation ratio of deterministic algorithms. Next, we consider graphs of small arboricity, whose edge sets can be decomposed into a small number of forests. We give two algorithms, a randomized one excelling in its approximation ratio and a uniform deterministic one which is faster and simpler. Finally, we show that in planar graphs, which can be drawn in the Euclidean plane without intersecting edges, a constant approximation factor can be ensured within a constant number of communication rounds.