共查询到20条相似文献,搜索用时 15 毫秒
1.
Zi-MaoLi Da-MingZhu Shao-HanMa 《计算机科学技术学报》2004,19(C00):39-39
近些年来,Steiner树问题在理论和应用上都引起了极大的关注,尤其在日渐成熟的近似算法设计理论方面,该问题占有一定的中心地位。给定赋权连通图G=(V,E,W)及顶点子集S包含V(S中顶点称为terminals),传统的Steiner树问题要求寻找一棵最小的树联接5中的所有顶点,该树可能包含V-S中的顶点(称为Steiner点)。即使图中每条边的权值仅限制为1或2时,传统的Steiner树问题仍然是MAX—SNP Hard。 相似文献
2.
一种点边带权最小生成树的近似算法 总被引:1,自引:0,他引:1
在给定的一个除边有代价外点也有两种代价的图中,要求出一棵点边代价和最小的生成树。这个优化问题具有实际应用背景。证明了该问题是NP难的,并且也给出该问题的近似算法和近似度分析。 相似文献
3.
树上推广的Multicut问题的近似算法 总被引:3,自引:0,他引:3
张鹏 《计算机研究与发展》2008,45(7):1195-1202
给定边上有费用的树T,终端集合族X={S\\-1,S\\-2,…,S\\-l},推广的Multicut问题询问费用最小的边集,使得在树上删除边集中的边能够断开每一个终端集.推广的Multicut问题有其独立的研究意义,因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的Steiner Forest问题的对偶问题.树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题近似求解.对于该问题的Prize-collecting版本,给出了原始对偶的3倍近似算法.对于该问题的k版本,通过非一致的途径给出了近似比为min{2(l-k+1),k}的近似算法.以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似到O(n\\+\\{16-ε\\})以内是困难的(对某个小的常数ε>0). 相似文献
4.
提出一种更新移动目标最短路径树的近似算法来避免重新生成整棵路径树。算法使用了局部图的思想,使每次迭代更新尽量少的节点来减少代价。实验证明算法具有良好的效率、近似度和可伸缩性。分析了如何调整算法,以便在近似度和效率之间实现平衡。 相似文献
5.
计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈ V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过△*+1,其中△*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多. 相似文献
7.
数据流是一种新型数据模型,广泛应用于交通流量监控、通信管理、传感器网络、股票分析、Web点击流等众多领域.近年来越来越多的学者关注于数据流上的分位数计算研究.由于流数据的连续、无界、易失等特性,存储完整的流数据信息并得到精确的查询结果几乎是不可能的.在实施查询计算时追求内存用量与查询精度之间的最佳均衡.设计了规范数直方图的概要数据结构以存储流数据的摘要信息,并在此基础上提出了单遍扫描的、联机的分位数近似算法,其时间和空间复杂度均线性于概要结构中桶的个数,而与数据流的长度无关,因而具有很好的可规模性.该方法在均匀分布的数据上取得了优良性能.分析了算法精度与内存需求的关系.实验结果表明该算法具有较精确的查询结果,具备良好的实用性和有效性. 相似文献
8.
9.
研究任务有多种处理方式的多处理器任务调度问题(MTS)的求解算法,给出求解这种问题的二阶段方法:第1阶段为指派问题,第二阶段调度问题Pm|fixj|Cmax,从而得到一个新的求解Pm|setj|Cmax。近似算法的方法,并针对P4|fixj|Cmax给出了具体算法,证明这种近似算法是一个2-逼近度算法,是文献中在4-处理器问题上的推广。 相似文献
10.
本文提出了一个计算机通信和分布式系统的一类扩展的Steiner树问题,对此问题设计了两个求其最优解的算法。这两个算法的时间复杂性分别是O和O。其中,k是一棵Steiner树需支撑的给定顶点的个数。 相似文献
11.
12.
本文给出两种构造三阶B树的算法,证明算法的时间复杂性,并给出用三阶B权实现热力公司的数据管理实例。 相似文献
13.
14.
有色装箱问题的在线近似算法 总被引:7,自引:0,他引:7
有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景,提出了求解有色装箱问题的KC-A算法,它首先对输入物品进行分类预处理,然后在同一类内部使用经典装箱问题的近似策略A,给出了KC-A算法最坏情况渐近性能比的下界,分析了当选用的算法A是著名装相算法NF,FF,BF,WF时KC-A算法的最坏情况渐近性能比和平均性能比,给出了实验结果,并指出KC-FF表现出相对更好的实验效果。 相似文献
15.
16.
17.
最小生成树的高效异步并行算法 总被引:1,自引:0,他引:1
在MIMD-SM并行计算模型上,本文给出了时间复杂性为O(n(n/p+logp))的最小生成树的异步并行算法,其中n,p(1≤p≤n)分别表示图的顶点数和处理机的个数。 相似文献
18.
提出了一种基于矩阵变换的方法,将n阶TSP问题近似转化为n-1阶TSP问题,然后用递归运算得出最后解。此算法的时间复杂度为O(n3)。而后又对此算法做了进一步的改进,近似度有很大提高但时间复杂度增加为O(n4)。经过实验表明,此类算法求解的近似度很高,尤其是在满足三角不等式的问题中,误差更低。利用TSPLIB数据库中的数据进行测试,得到的结果误差最多不超过10%。 相似文献
19.
本文研究对称二分B树(Symmetric Binary B-trees)的一种拓广形式,即SBB(K)树。这种树结构高度仅为[(1+1/K)log(n+1)],通过改变K值,树重构平均代价为O(olgn),维护算法在最坏情况时仅耗费常数代价。 相似文献