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

摘要

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