|
1.
|
Multi-Radio无线传感器网络中基于缓存和信道切换的数据查询算法的研究
|
|
|
|
|
|
|
张艳卿 李金宝 郭龙江 朱敬华《计算机学报》,2012年第35卷第11期
|
|
|
针对Multi-Radio Multi-Channel传感器网络中链路服务质量和信道冲突等问题,提出并证明了基于缓存和信道切换的数据查询问题是一个NP完全问题.根据数据流守恒和链路-信道等约束条件,建立线性规划方程,得到该问题的最优解模型,并提出了一个多项式时间的近似算法——贪心新覆盖数据算法.该算法采用动态规划策略最小化缓存节点将单位数据包传输到查询节点所需要的路径时延,再贪心选择其具有最小路径时延的缓存节点,收集其新覆盖数据.理论分析和实验结果表明,提出的方案能有效地减少数据收集时延,提高数据查询效率.
|
|
2.
|
K-median问题贪心近似算法的分析与实验 被引次数：1
|
|
|
|
|
|
|
肖进杰 谢青松 刘晓华《计算机工程》,2008年第34卷第22期
|
|
|
讨论K-median问题的贪心近似算法及其在实际计算中的表现。提出一个解K-median问题的贪心算法，证明该算法的近似度为O(ln(n/k))，通过实验证明该贪心算法在实际应用当中可以取得较好的效果，大约有90%的客户能被距离其最近、次近和第三近的设备服务。
|
|
3.
|
基于共享存储器多处理器片上系统的互斥模型*
|
|
|
|
|
|
|
徐成 龙榜 刘彦 陶海洋 王立东《计算机应用研究》,2009年第26卷第12期
|
|
|
在原有模型和算法分析的基础上，提出了一种共享存储器MPSOC互斥模型。该模型能适应各种互斥算法的描述、论证需求，能更好地描述任务优先级、实时性；能够适应区分处理器源任务的互斥算法（即区分对待来自不同处理器的任务）；严格区分并发性、并行性，描述更加精确；扩展了服务周期、事件之间关系；能够精确地量化互斥性能指标，以便更好地比较互斥算法优劣。最后，给出了该模型的一个简单实例，对模型应用提供指导。
|
|
4.
|
用贪心算法求解最优服务次序问题
|
|
|
|
|
|
|
李洪霞 于仁师 史新梁 邓立苗《适用技术之窗》,2008年第3期
|
|
|
贪心算法是解决问题的一类重要方法,因其简单、直观和高效而受到人们的重视。特别是对于具有最优子结构和贪心选择性质的一类实际问题,它可以通过一系列局部最优选择来获得整体最优解。本文首先对最优服务次序问题进行了分析,然后给出了该问题的贪心解法,最后对所提出算法的时间复杂度进行了分析。
|
|
5.
|
基于Token追踪的分布式互斥算法
|
|
|
|
|
|
|
鄢勇《计算机学报》,1993年第16卷第9期
|
|
|
本文首先提出一切合实际的互斥信件量度量方法,该方法不仅考虑请求结点所发的信息数,同时还考虑信件的存储转发次数,然后针对任一拓扑结构,在充分利用局部信息与已知信息的基础上,给出了互斥信件量为0～2(n—1)(n为结点数)的有效互斥算法,该算法不仅在互斥信件量上是目前最优的,而且充分体现了分布式算法设计的一个重要原则,充分利用一切已知信息作为未来决策的依据。
|
|
6.
|
一维下料问题的AB分类法 被引次数：1
|
|
|
|
|
|
|
林健良《计算机应用》,2009年第29卷第5期
|
|
|
为了解决大规模的一维下料问题的计算困难, 根据一维下料问题的特点，把贪心算法和随机搜索技术有机地结合起来，利用随机搜索技术对贪心算法进行了有效的改进,提出了一种简单实用的AB分类法。 实验表明，该算法对规模较大的问题也能较快地获得问题最优解或精度较高的近似最优解。
|
|
7.
|
集合多覆盖问题的乘性权重更新分析
|
|
|
|
|
|
|
崔鹏 钱丽艳《计算机科学》,2007年第34卷第10期
|
|
|
集合多覆盖问题的简单贪心算法的近似比是lnn＋1。本文提出简单贪心算法的一个变形，宽度优先贪心算法，并且证明其有近似比（lnn）／r＋lnlnn＋O（1），其中r是覆盖要求。这个结果比由随机取整方法得到的近似比O（（lnn）/r＋√（lnn）＋1为优。宽度优先贪心算法的设计可以归入Arora等最近提出的乘性权重更新方法的框架。关键词集合多覆盖，宽度优先贪心算法，乘性权重更新方法
|
|
8.
|
NFV 中的 vDPI 功能放置问题研究
|
|
|
|
|
|
|
吴迪 李俊 韩淑君《南方农业学报》,2016年第7卷第6期
|
|
|
网络功能虚拟化 (NFV) 是视频流应用的重要技术。在视频流使用场景下,已有的工作研究 NFV 网络中的虚拟深度包检测 (vDPI) 放置问题时,仅考虑减少 vDPI 放置的数量,但没有考虑放置 vDPI 功能带来的 NFV 网络性能稳定性问题。针对上述不足,本文在减小 vDPI 放置数量的基础上,考虑提高网络稳定性,提出了一个多目标线性整数规划模型,并设计了一种贪心近似放置算法。该算法在 NFV 中放置 vDPI 功能时,可以降低 vDPI 放置数量、减少流量经过的平均网络跳数、降低传输时延、保证网络性能的稳定性。本文采用 Lingo 求出数学模型的最优解,并用贪心近似放置算法进行实验,对比算法实验结果与模型所求最优解可知：所提算法正确性较高,有较好的时间复杂度,适用于不同规模的 NFV 网络。
|
|
9.
|
一种可扩展的XPath查询最小化算法框架
|
|
|
|
|
|
|
林峰 冯建华 塔娜 李国良 洪亲《计算机科学》,2008年第35卷第3期
|
|
|
XPath是XML的基本查询语言,XPath查询最小化对于提高XML数据库的查询性能具有重要意义.但是,由于XPath查询最小化是一个coNP完备问题,大部分已有的算法局限于处理简单的XPath片段.本文从一个新的角度入手,综合考虑完备性和高效性,提出了一个新的查询最小化框架,与已有算法"面向结点",即逐个删除冗余结点的解决思路不同,本文提出"面向树模式"的方式,即通过计算树模式的自同态映射,寻找目标结点集最小的自同态映射,进而求解最小等价查询树的方法.该方法具有较高的效率,而且在--Z..情况下是完备的,尤其是可以进一步扩展到更复杂的XPath片段.本文以此框架为基础,给出一个可以计算复杂查询模式的算法.
|
|
10.
|
基于树拓扑网络的分布式互斥算法
|
|
|
|
|
|
|
王莉《计算机仿真》,2009年第26卷第2期
|
|
|
分布式互斥是分布式系统的重要问题.根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME.算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大残存树"探测方法进行系统的容错处理.描述了算法的模型、主要思想、数据结构、消息结构以及伪代码,并证明了算法的正确性.理论性能分析与仿真对比证明,算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.
|
|
11.
|
一种非DHT查找方式的结构化P2P文件共享模型
|
|
|
|
|
|
|
熊伟 谢冬青 焦炳旺 刘洁《计算机研究与发展》,2009年第46卷第3期
|
|
|
普遍认为在结构化P2P协议中实现能力感知会增加网络开销.提出一种能力感知结构化P2P协议--HeteroChord,HeteroChord在新加入结点的路由表建立算法与更新算法中实现能力感知,能力感知速度快,在动态环境下,HeteroChord具有比Chord更小的维护开销.针对HeteroPastry文件索引双向复制开销大以及不能遍历强结点的缺点,以HeteroChord协议为基础建立一种非DHT查找方式的文件共享模型--NHFS,NHFS将超级结点简单首尾相连形成super leaf set,并采用选择性单向复制把文件索引复制到超级结点,使查询仅在超级结点中进行.super leaf set使查询可以方便遍历超级结点,且选择性单向复制文件索引产生的网络开销远小于双向复制文件索引产生的网络开销,相对HeteroPastry而言,NHFS文件共享模型更合理.
|
|
12.
|
贪心遗传算法及其在武器目标分配问题中的应用
|
|
|
|
|
|
|
张海兵 徐诚 李世永《弹道学报》,2007年第19卷第2期
|
|
|
针对遗传算法在解决武器目标分配问题时存在的缺点,提出了将贪心机制应用于遗传算法解决该问题的思路,即贪心遗传算法.在建立武器目标分配问题数学模型的基础上,探讨将贪心算法思想作为确定性选择原则指导遗传操作实施解空间搜索,分析了贪心遗传算法的编码、生成初始种群,贪心交叉、贪心变异等过程的原理和算法实现流程,应用贪心遗传算法进行了战斗实例计算.结果表明该方法是可行的,避免了遗传算法早熟收敛和封闭竞争的问题,计算量小、算法稳定.
|
|
13.
|
关于最小测试集的线性规划松弛近似
|
|
|
|
|
|
|
崔鹏 刘红静《计算机科学》,2005年第32卷第10期
|
|
|
目前最小测试集的最佳近似比是贪心算法的2 ln n＋o（1）.这个近似比能否改进是一个公开的问题.本文讨论了最小测试集的基于线性规划松弛的近似比证明方法的能力问题.我们证明最小测试集的整性间隙至少为0.72 ln n,而且最小测试集整性间隙的系数可以与最小集合覆盖的整性间隙的系数一样大.另外,我们说明加权最小测试集的贪心算法的近似比不能通过对偶拟合方法改进超过一个常数.
|
|
14.
|
一种分布式系统中最优复制的策略分析
|
|
|
|
|
|
|
刘兴 万方 王大震《计算机工程与应用》,2006年第Z1期
|
|
|
在网络中定位最优复制以最小化通讯代价。假定网络采用read-one-write-all策略来保证网络数据一致性,那么存在一个决定复制定位的最优化问题。提出了研究复制问题中读、写比率以确定最优化通讯代价。问题可转换成一个0- 1线性规划问题,并将此问题扩展为一个P中值问题,可以证明这个问题是NP-complete的问题,并提出了一种多项式时间内的此问题求解算法。
|
|
15.
|
一种自适应动态负载均衡算法 被引次数：5
|
|
|
|
|
|
|
王玥 蔡皖东 段琪《计算机工程与应用》,2006年第42卷第21期
|
|
|
负载均衡问题是一个经典的组合优化难题,该文建立了一个集群中的负载均衡问题模型,并提出了一种旨在最小化负载均衡开销的动态自适应算法。由于集群中存在网络延时,所以负载重分配的开销很大一部分取决于CPU间发送、接受的消息的最大数量。该负载均衡算法以最小化负载重分配时CPU间消息发送、接受的数量为目标,根据过载、轻载CPU数量的变化动态调用D算法和R算法,以降低负载均衡开销。
|
|
16.
|
MANET中基于缓存的移动数据查询处理算法的研究
|
|
|
|
|
|
|
张艳卿 李金宝 郭龙江《计算机研究与发展》,2011年第48卷第10期
|
|
|
针对MANET环境中带宽有限、能量有限、存储有限和链路频繁的断接性等特点,提出了基于缓存的移动数据查询问题,证明该问题是NP完全问题,并给出一个多项式时间的近似算法,即最大节点新覆盖数据算法MD.该算法采用贪心策略,查询新覆盖数据量最大的节点,减少了查询次数,并最大限度地减少了网络中的传输时延.然后在MD算法的基础上,同时考虑了节点新覆盖数据量和链路服务质量问题,提出了一种改进的高效的启发式算法,即基于最大节点DD值的算法MDD,有效地减少了能量消耗,最小化数据传输时延,提高了网络的吞吐量.理论分析及实验结果表明提出的数据查询算法能够充分利用缓存节点的数据信息,较好地完成数据查询工作,有效地减少数据收集时延,提高查询效率.
|
|
17.
|
k-median问题反向贪心随机算法
|
|
|
|
|
|
|
王守强《计算机科学》,2012年第39卷第7期
|
|
|
k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O([kαln(k)]2(n+m)),其中n和m分别代表设施集合以及客户点集的大小。最后,通过计算机实验验证了k-median问题的反向贪心算法的实际计算效果。
|
|
18.
|
一种基于模式替代的遗传算法解0/1背包问题* 被引次数：3
|
|
|
|
|
|
|
李康顺 贾玉珍 张文生《计算机应用研究》,2009年第26卷第2期
|
|
|
背包问题是一个典型的 NP完全问题。提出一种基于模式替代的遗传算法解0/1背包问题思想，通过收集每代种群中最好的几个个体生成模式来引导种群的搜索方向，以提高遗传算法的搜索速度和寻找最优解的能力。通过仿真数值实验，将该方法与简单遗传算法、贪心算法计算结果比较分析，充分证明了使用基于模式替代遗传算法来求解背包问题的有效性和实用性。
|
|
19.
|
改进的最优顶点覆盖贪心边近似算法 被引次数：3
|
|
|
|
|
|
|
杨杰《计算机应用》,2006年第26卷第1期
|
|
|
最优顶点覆盖问题是6个基本的NP完全问题之一，无法在多项式时间内得到最优解，除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时，证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。
|
|
20.
|
一种基于松弛循环差集的对称分布式互斥算法
|
|
|
|
|
|
|
李美安 刘心松 王征《四川大学学报(工程科学版)》,2005年第37卷第4期
|
|
|
为在全分布系统中实现对称的分布式互斥，需要设计出对称的分布式互斥算法。通过证明循环请求集与松弛循环差集的等价性，将求取包含任意数量节点的分布式系统对称请求集的问题转化为求取任意数量节点集合的松弛差集问题，并在此基础上提出了一种基于循环松弛差集的对称分布式互斥请求集生成算法。在请求集生成算法的基础上，引入了转移应答消息和请求集重构消息，重新定义应答消息的结构以使其能够携带更多的信息，重新设计了分布式互斥算法的相关过程，从而改进了Makawa类分布式互斥算法的性能。该算法具有较高的时间效率和空间效率，其求取的请求集尺寸较小，使分布式互斥算法的消息复杂度降为0（2（N的平方根）），同步时间降为T，节点容错能力达到N-1。基于松弛循环差集的分布式互斥算法克服了以往分布式算法必须牺牲一种性能指标以提高另一种性能指标的缺点，具有很高的应用价值。
|
|
