基于权重约束的最大密度路径改进算法

Improved Algorithm for Finding Weight-constrained Maximum-density Path

给定一棵树,树上的每个节点被赋予一对数值,它们分别表示节点的值和权重。基于权重约束的最大密度路径算法用于搜索树上的最大密度路径,即最大密度路径上所有节点的值之和与节点的权重之和的比值是所有路径中最大的。通过研究发现,现有的基于权重约束的最大密度路径算法有一定的局限性。文中提出了突破该局限性的可行性方案,进而设计并改进了基于权重约束的最大密度路径算法。

A tree was given in which each node is associated with a pair of numbers that represent the value and the weight of the node. The weight constrained maximum-density path algorithm is to find the maximum-density path in the tree, that is the ratio of the summation of the nodes＇ values to the summation of the nodes＇ weights is maximum. After studing the current algorithm,we found that the maximum density path algorithm has limitations. We gave the way of bypassing the limitations. Finallv we doll^hal ~ ：