计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
8期
122-124
,共3页
最大密度路径%最大密度子树%动态规划
最大密度路徑%最大密度子樹%動態規劃
최대밀도로경%최대밀도자수%동태규화
Maximum-density path%Maximum-density subtree%Dynamic programming
给定一棵树,树上的每个节点被赋予一对数值,它们分别表示节点的值和权重.基于权重约束的最大密度路径算法用于搜索树上的最大密度路径,即最大密度路径上所有节点的值之和与节点的权重之和的比值是所有路径中最大的.通过研究发现,现有的基于权重约束的最大密度路径算法有一定的局限性.文中提出了突破该局限性的可行性方案,进而设计并改进了基于权重约束的最大密度路径算法.
給定一棵樹,樹上的每箇節點被賦予一對數值,它們分彆錶示節點的值和權重.基于權重約束的最大密度路徑算法用于搜索樹上的最大密度路徑,即最大密度路徑上所有節點的值之和與節點的權重之和的比值是所有路徑中最大的.通過研究髮現,現有的基于權重約束的最大密度路徑算法有一定的跼限性.文中提齣瞭突破該跼限性的可行性方案,進而設計併改進瞭基于權重約束的最大密度路徑算法.
급정일과수,수상적매개절점피부여일대수치,타문분별표시절점적치화권중.기우권중약속적최대밀도로경산법용우수색수상적최대밀도로경,즉최대밀도로경상소유절점적치지화여절점적권중지화적비치시소유로경중최대적.통과연구발현,현유적기우권중약속적최대밀도로경산법유일정적국한성.문중제출료돌파해국한성적가행성방안,진이설계병개진료기우권중약속적최대밀도로경산법.
