最小切割代价的限权树分割优化算法  

Optimal algorithm of weight-bounded tree partitioning with minimal cutting cost

作　　者：陈浩[1] 罗光春[1] 秦科[1] 彭凝多 

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《计算机应用研究》2014年第8期2287-2289,2319,共4页Application Research of Computers

基　　金：四川省自然科学基金资助项目(2012GZ0088;2012FZ0063)

摘　　要：研究一个在并行与分布式计算环境下兴起的树分割问题:给定一个节点和边均带权值的树T,通过切割树的边,将该树T分割成节点不相邻的子树,使得所有子树的节点权值之和不超过一个给定的上限K,并且使得被割边的权值之和最小。提出了一个能在多项式时间内完成的快速优化算法,包括一个基本的自底向上的结构及其动态规划方案和两个能大量节省计算空间的剪枝方案。实验表明,该算法在性能上相比其他同类算法要快十倍甚至数百倍,因而该算法能更好地应用于大规模并行任务调度的优化。This paper investigated a tree partition problem that arises in parallel and distributed computing environments. It gave a tree with vertex and edge weights,partitioning into vertex-disjoint subtrees by cutting some edges such that the sum of vertex（ node） weights in each subtree did not exceed a fixed limit and the total weights of cut edges was minimum. It provided a fast polynomial-time optimal algorithm including a basic bottom-up structure with dynamic programming and another two pruning schemes which enabled us to prune much of the computing space. Experimental studies show that the algorithm run much faster than prior algorithms,by a factor ranging form less than 10 to more than hundreds. Therefore,it is more suitable for optimizing the scheduling of large-scale and parallel tasks.

关 键 词：树分割 动态规划 优化算法 分布式计算 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]