| 分支定界算法的分布并行化研究 |
| |
| 引用本文： | 李一明,李毅,周明天. 分支定界算法的分布并行化研究[J]. 计算机应用, 2006, 26(3): 723-0726 |
| |
| 作者姓名： | 李一明 李毅 周明天 |
| |
| 作者单位： | 电子科技大学,计算机科学与工程学院,四川,成都,610054;电子科技大学,计算机科学与工程学院,四川,成都,610054;电子科技大学,计算机科学与工程学院,四川,成都,610054 |
| |
| 摘 要： | 介绍了一种专用于计算分支定界算法的机群计算平台，其中所使用的分布并行策略减少了分支定界算法计算时间复杂度，减小了问题的规模；可以把计算平台机群中的任何一台计算机上计算出的当前全局最佳本分值，实时地广播给所有其他并行的计算机，并作为它们新的最佳本分值，实现分支节点的快速并行淘汰；应用启发式算法修改了分支定界算法，提高了分支节点的淘汰效率。选用旅行商问题实例作为测试基准。计算表明，在保证求得最优解的前提下，该平台能很好地提高分支定界算法的效率。
|
| 关 键 词： | 分支定界算法 分布并行计算 启发式算法 旅行商问题(TSP) |
| 文章编号： | 1001-9081（2006）03-0723-04 |
| 收稿时间： | 2005-10-08 |
| 修稿时间： | 2005-10-082005-12-15 |
Research on distributed parallel computing for branch and bound algorithm |
| |
| LI Yi-ming,LI Yi,ZHOU Ming-tian. Research on distributed parallel computing for branch and bound algorithm[J]. Journal of Computer Applications, 2006, 26(3): 723-0726 |
| |
| Authors: | LI Yi-ming LI Yi ZHOU Ming-tian |
| |
| Affiliation: | School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 610054, China |
| |
| Abstract: | The realization of a special cluster for calculating branch and bound algorithm was presented. The distributed parallel strategy in the cluster decreased the branch and bound running time from three aspects: (1)the problem's scale was decreased by using distributed parallel computing; (2)the present optimal value which was calculated by any computer could be broadcast to every computer in the platform immediately; (3) the changed branch and bound algorithm with the heuristic algorithm in the cluster increases the efficiency of eliminating node. The solving TSP(Traveling Salesman Problem) examples as benchmark shows that this platform can increase the branch and bound algorithm's efficiency and get the optimal solution sooner. |
| |
| Keywords: | branch and bound algorithm distributed parallel computing heuristic algorithm traveling salesman problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
