Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming

摘要：

　　The classical algorithm uses Dynamic Programming to construct an Optimal Binary Search Tree.In this paper,we research into the dynamical process of building an Optimal Binary Search Tree and present an optimized solution.Time complexity is reduced from O (n3) to O (n2).Meanwhile,three feasible parallel solutions are put forward to achieve greater optimization.Some experiments on cluster have been done to compare efficiency of parallel and serial algorithm and the result shows that the parallel algorithm is much better.In the case of a larger amount of testing data,the parallel solution can save half of the time consumption.However,because of the particularity of this issue,the parallel algorithm has its own limitation.

关键词： Dynamic Programming Optimal Binary Search Tree optimization parallelization

作者: Bo Han Yongquan Lu

作者单位: High Performance Computing Center of Communication University of China,Beijing,China

会议类型: 国际会议

会议名称: the 2nd International Conference on Electronic & Mechanical Engineering and Information Technology (EMEIT-2012)(2012年电机工程与信息技术国际会议)

会议地点: 沈阳

会议语种:英文

页码: 229-233

在线出版日期: 2012-09-26（万方平台首次上网日期，不代表论文的发表时间）