基于权重约束的最大密度路径改进算法-论文.pdf

《基于权重约束的最大密度路径改进算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第8期计算机科学Vo1．41No．82014年8月ComDuterScienceAug2014基于权重约束的最大密度路径改进算法刘坤良张大坤武继刚(天津工业大学计算机科学与软件学院天津300387)摘要给定一棵树，树上的每个节点被赋予一对数值，它们分别表示节点的值和权重。基于权重约束的最大密度路径算法用于搜索树上的最大密度路径，即最大密度路径上所有节点的值之和与节点的权重之和的比值是所有路径中最大的。通过研究发现，现有的基于权重约束的最大密度路径算法有一定的局限性。文中提出了突破该局限性的可行性方案，进而设

2、计并改进了基于权重约束的最大密度路径算法。关键词最大密度路径，最大密度子树，动态规划中图法分类号TP393文献标识码ADOI10．11896／j．issn．1002—137X．2014．08．027ImprovedAlgorithmforFindingWeight-constrainedMaximum-densityPathLIUKun-liangZHANGDa—kunWUJi—gang(SchoolofComputerScienceandSoftwareEngineering，TianjinPolytechnic

3、University，Tianjin300387。China)AbstractAtreewasgiveninwhicheachnodeiSassociatedwithapairOfnumbersthatrepresentthevalueandtheweightofthenode．Theweightconstrainedmaximum-densitypathalgorithmistofindthemaximum-densitypathinthetree．thatiStheratioofthesummationofth

4、enodes’valuestothesummationofthenodes’weightsiSmaximurrkAfterstudingthecurrentalgorithm，wefoundthatthemaximumdensitypathalgorithmhaslimitations．Wegavethewayofbypassingthelimitations．Finallywedesignedandimprovedthealgorithm．KeywordsMaximum-densitypath，Maximum-d

5、ensitysubtree，DynamicprogrammingHsin-HaoSu_3]提出了改进的基于长度约束的最大子树算法，1引言该算法在树上所有边的长度都是正整数的情况下，时间复杂给定一棵具有个节点的树T一(V，E)，树上的每个节度为O(nulogn)，边的长度一致的情况下，该算法的时间复杂点被赋予一对数值(val，)，分别表示节点的值和权重，其度可以降为0(n／log孚)，其中，“为子树的最大约束长度。中val为一实数，表示节点的数值大小；为一正整数，Sun-YuanHsieh[1_在树上的每个节点给定权

6、重和节点值的情表示节点的权重。假设用D(T)表示树T的密度，则D(T)况下，设计了基于权重约束的最大密度路径(MDP)和基于权∑val一_。假设用硼(丁)表示树丁的权重之和，则叫(丁)一重约束的最大密度子树(MDT)算法，算法的时间复杂度分别为O(Wm~，z)和o(议缸n)。其中一为最大约束权重值，为∑叫。树T的子树T一(，E)为树T的一个连通子图，其树上节点的个数。在把节点对应的值和权重改为赋值给边的中V，E∈E。给定一权重范围(win。，让h)，基于权重约情况下，同样可以解决边约束的问题。我们通过研究发现该束的

7、最大密度子树算法(MDT)用于搜索满足条件≤叫算法有实现上的局限性，如果按照算法本身的设计去实现并()≤的最大密度子树一(，E)。如果子树被限定不能找到有效的最大密度路径或最大密度子树。本文对此问为节点之间的路径，MDT问题就变成了基于权重约束的最大题进行研究，并作了改进。改进后的算法能有效地找到最大路径(MDP)问题。MDP算法在计算生物学领域有着广泛的密度路径或最大密度子树，平均情况下的时间复杂度优于原应用，比如基因序列比对。MDT算法在计算机网络、交通网算法，最坏情况的时间复杂度与原算法相同。络及物流网络设计

8、中应用广泛。比如在交通网络设计中，怎2问题描述样在有限的预算之下改造交通流量最高的路段。HoongChuinLaiuE2_在树上的每条边赋予确定的权重和长度的情况在一棵具有根节点r的树T上，任一节点的父节点用下，给出了基于长度约束的最大密度路径算法。该算法的时par(v)表示，其子节点用child()表示，节点的度用deg()间复杂度为O(nlog)，当所有