基于混合负载平衡的并行启发式搜索算法  

Parallel A* Searching Algorithm Based on Mixed Load Balancing

作　　者：袁源[1] 李炳法[1] 杨杰[2] 丁莹[1] 彭代毅[1] 

机构地区：[1]四川大学计算机学院,成都610065 [2]代尔夫特理工大学计算机系

出　　处：《计算机工程》2006年第23期193-195,215,共4页Computer Engineering

摘　　要：在分析了迭代加深启发式搜索(Iterative Deepening A*)算法及其可并行性后,提出了一种新的基于混合负载平衡的并行迭代加深启发式搜索算法。该算法综合了静态负载平衡和动态负载平衡的优点,可以在多结点的并行搜索计算中获得很高的加速比和效率。给出了该算法的Java RMI实现。通过在72个结点的并行机上的试验表明,该算法可以极大地提高并行搜索算法的加速度和效率。This paper presents a new parallel iterative deepening A＊ searching algorithm by discussing iterative deepening A＊ algorithm and its parallel properties. This algorithm has the advantages in both static and dynamic load balancing, and achieves very high speedup and efficiency. It shows how to realize Java RMI with this algorithm. The experimentations on 72-node parallel machine indicate that this algorithm can improve the speedup and efficiency of parallel searching algorithm heavily.

关 键 词：负载平衡 迭代加深 并行 搜索算法 

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