杭州电子科技大学学报
杭州電子科技大學學報
항주전자과기대학학보
JOURNAL OF HANGZHOU DIANZI UNIVERSITY
2012年
2期
63-65
,共3页
树核问题%极大子树%动态规划
樹覈問題%極大子樹%動態規劃
수핵문제%겁대자수%동태규화
考虑到在实际应用中,由于计算机和通信网络中一般每个设备的处理能力是有限的,以及控制各设备放置点之间的营运成本,该文在tree core问题的基础上,提出了同时带有度和半径约束的tree core问题,记为(q,1)-DTC问题(Degree constrained Tree Core).该文先构造出极大子树集,然后在极大子树中利用动态规划的方法,求解(q,1) - DTC问题,可在O(n2)时间内求得该问题的最优解.
攷慮到在實際應用中,由于計算機和通信網絡中一般每箇設備的處理能力是有限的,以及控製各設備放置點之間的營運成本,該文在tree core問題的基礎上,提齣瞭同時帶有度和半徑約束的tree core問題,記為(q,1)-DTC問題(Degree constrained Tree Core).該文先構造齣極大子樹集,然後在極大子樹中利用動態規劃的方法,求解(q,1) - DTC問題,可在O(n2)時間內求得該問題的最優解.
고필도재실제응용중,유우계산궤화통신망락중일반매개설비적처리능력시유한적,이급공제각설비방치점지간적영운성본,해문재tree core문제적기출상,제출료동시대유도화반경약속적tree core문제,기위(q,1)-DTC문제(Degree constrained Tree Core).해문선구조출겁대자수집,연후재겁대자수중이용동태규화적방법,구해(q,1) - DTC문제,가재O(n2)시간내구득해문제적최우해.
