社交网络中的概率支配集问题

针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念.在图中寻找最少点数的概率支配集称为最小概率支配集问题.证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间复杂度的精确算法.基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概率支配集问题...     

货郎问题求解算法分析

介绍了求解货郎问题的4个算法：贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解，并对各个算法的性能进行了分析比较。贪心算法的运行速度较快，但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题，其近似性能比（即精确度）分别为：RMST（I）＜2，RMM（I）＜3／2。回溯搜索算法可以求出货郎问题的最优解，随着城市数目的增加，其搜索效率会下降。     

一种求解带权集合覆盖问题的近似算法

以优化形式描述的集合覆盖问题是一个NP难问题,设计快速有效的近似算法,具有重要的理论与现实意义.基于贪心算法思想,提出了一种求解带权集合覆盖问题的近似算法,并讨论了该算法的相对近似比.     

TSP问题的一种快速近似算法及应用

给出求解度约束最小生成树(DCMST)问题的一种快速近似算法．在此基础上．又给出求解TSP问题的一种快速近似算法,并在微机上实现且其数值试验的效果良好．最后,将求解TSP问题的近似快速算法作一些改进．应用于遗传算法的初始种群生成并进行数值实验．结果表明,用文中算法生成的初始种群．比起一般方法产生的初始种群性能有很大改进．该算法可以加速遗传算法的寻优速度．     

无线Ad Hoc网络MCDS的贪心分布式近似算法

在无线Ad Hoc网络中基于最小连通支配集(MCDS)构建虚拟主干网可以有效缓解广播风暴,提高网络性能,延长网络生存时间.利用单位圆盘图中极大独立集的性质,使用2阶段贪心分布式近似算法构造了MCDS.从理论上分析了算法的时间复杂度、信息复杂度和近似比.     

基于扰动的社交网络保护方法研究

扰动技术是社交网络隐私保护的重要方法,本文提出了高斯随机扰动和贪心扰动两种扰动算法保护社交网络的权值,分别适用于动态和静态社交网络。高斯随机扰动可以简单有效地保护动态社交网络的权值隐私,贪心扰动算法将社交网络的边分类,可以在保护静态社交网络权值隐私的同时保证社交网络的最小生成树不变,提高社交网络数据的可用性。实验结果表明两种算法均能有效保护社交网络的权值安全,并且保持较高的数据可用性。     

联合有社交意识的D2D配对和功率分配策略

随着移动社交网络应用和无线通信网络的快速发展,移动社交网络(MSNs)正在渗透进人们日常生活中.提出了一种有社交意识的D2D(Device-to-Device)通信模型.基于该模型,研究了在物理条件和社交条件的约束下联合D2D配对和功率分配的问题.为了易于求解,在匹配理论的基础上,将问题建模为一个一对一的双边匹配问题,提出了分三步求解的算法优化D2D配对和功率分配问题.引入了真实的社交网络轨迹来模拟移动用户间的社交关系,从而验证提出的算法的性能.仿真结果表明:相比另外两种启发式算法有较高的增益.     

最优顶点覆盖的贪心边近似算法

提出了一种新的贪心边近似算法,能保证性能比不大于2的同时比传统的选任意边算法有更优的解,在可验证（能得到最优覆盖点数）时,统计数据表明贪心边算法非常有效,是一个集合了传统的任选一边近似算法和选择度数最大点的贪心算法两者优点的新算法.     

改进的生成树算法求解旅行商问题

给出了一种基于最小生成树的TSP求解算法,该算法结合贪心算法和匹配算法,把传统近似算法的局部最优转化为全局最优,避免了最邻近算法中最后几步产生的较大的误差.文章最后分析了算法的复杂性,实验数据表明该算法有较高的有效性.     

基于改进的模拟退火算法求解0／1背包问题

提出了一种改进的具有变异和倒位算子的模拟退火算法,并将其用于求解0／1背包问题,其性能较标准模拟退火算法和贪心算法都有很大的改善．通过大量的数值实验,证明了文中改进的模拟退火算法求解背包问题的有效性和实用性．     

图的正面影响控制集中贪婪算法的设计与分析

对于没有固定基础设施的无线传感器网络,设计一个优良合理的拓扑控制协议是关键.根据图的控制集在无线传感器网络组建虚拟骨干网的应用,研究了图上控制集问题的一个变形—正面影响控制集问题.针对图中是否存在孤立顶点,分两种情形讨论,设计了相应的贪婪算法,并分析了算法的性能比.     

改进的贪婪算法在无人机组网中的研究与应用

针对小型军用无人机平台小、速度快、能量有限导致的集群组网中节点生存时间受限、投递率低等问题,借鉴贪婪算法,提出一种复合权值的无线自组网路由算法。为减小边缘节点和低能节点对路径的影响,在算法中添加了边界评价因子和能量均衡2个优化参数对节点进行筛选,再利用Dijkstra算法的思想寻找网络中能量-拥塞复合权值最小的转发路径进行数据传输。仿真结果表明,与AODV算法和AOMDV算法相比,该算法在投递成功率、端到端时延、网络生存周期、路由开销方面均有良好性能。     

监测奶牛无线传感器网络的连通支配集构造

基于一个对奶牛行为特征监测的自组织无线传感器网络,构造骨干网以解决节点多跳通信问题,并采用图的连通支配集来实现。提出了一个基于极大独立集的最小连通支配集的分布式构造算法,并证明了该算法的正确性。采用计算机程序仿真的实验结果表明,此算法简单有效、适应于节点移动和网络拓扑变化的环境、且构造的连通支配集占节点的比例为30%左右,有效减少冗余的转发节点,可节省宝贵的网络资源。     

多维0-1背包问题的新型近似解法

运用属性论的转换程度函数,结合贪婪算法和核问题的研究思路提出了多维0-1背包问题的一种新型近似解法。该算法对生产实践中的四大类背包实例都有很快的收敛速度。特别是常规方法难以解决的最大子集和实例及强相关实例,算法能在一个很好的时间范围内给出近似度为99.7%的近似满意解甚至是最优解。     

基于禁忌搜索的模拟退火算法在最小控制集中的应用

图的控制集问题是在给定的简单无向图中求出阶数最小的控制点的集合,目前它已被证明是一个NP-完全问题．针对现阶段已有的模拟退火算法提出了一种改进的基于禁忌搜索的模拟退火算法,并通过与贪心算法、传统模拟退火算法进行比较,证明了该算法可以获得较小的控制集阶数．     

资源受限最小赋权树形图的一种贪婪分解启发式算法

资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.     

一种基于最小路径的多播路由优化算法

信息物理融合系统(Cyber-Physical Systems,CPS)底层是传感器、控制器和执行器等异构节点构成的无线自组网络,不同节点之间需要通过通信网络传送给感兴趣目标节点,传统的无线自组织网络一般采用单播或广播技术,但是这些往往实时性不高,通信开销大,不利于在CPS中受限节点间通信.该文针对信息物理融合系统中无线多播路由问题构建网络模型,演化为最小路径问题,数学模型为约束Steiner最小树问题,并针对该NP难问题通过启发式算法求解,再通过贪婪思想构建一种最小路径多播路由算法.最后通过与uCast以及SenCast等经典的多播路由算法仿真比较,得出其算法在实时性以及能耗等方面性能优异.     

无线传感器网络中能量有效的最小连通支配集算法

提出了一种分布式最小连通支配集求解算法,对Rule K算法中的标记算法进行了优化,从而形成了连通支配集,并通过新的剪枝算法对连通支配集进行了有效缩减.模拟仿真结果表明:在增加算法复杂度的前提下,该算法求得的连通支配集比前算法更小.     

基于社区节点重要性的社会网络压缩方法

针对目前图压缩方法中存在的时间复杂度较高、依赖先验知识设定参数、需要调节的参数过多、压缩有损、忽视网络社区结构等问题, 提出基于社区节点重要性的社会网络压缩方法。该方法由基于贪婪策略的社区发现算法(GS)和社会网络压缩算法(SNC)两部分组成。GS算法采用拓扑势理论, 不但可以实现社区发现, 而且可挖掘出社区中的重要节点。SNC算法以网络社区为压缩对象, 在保持社区间的关联关系的前提下实现了无损压缩, 并可在必要时保留社区中的重要节点或基本结构。通过实验, 对方法的可行性和有效性进行了验证。