摘要
研究一个在并行与分布式计算环境下兴起的树分割问题:给定一个节点和边均带权值的树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.
出处
《计算机应用研究》
CSCD
北大核心
2014年第8期2287-2289,2319,共4页
Application Research of Computers
基金
四川省自然科学基金资助项目(2012GZ0088
2012FZ0063)
关键词
树分割
动态规划
优化算法
分布式计算
tree partitioning
dynamic programming
optimal algorithm
distributed computing
