基于A*算法的2种任务-处理器分配改进算法

Two Improved Algorithms for Task to Processor Assignment Based on A* Algorithm

针对分布式计算中的任务-处理器分配问题,提出了2种基于A*算法的改进算法.通过对A*算法原理的分析,得到将A*算法应用于任务分配问题的搜索树模型,和通过将搜索树在处理单元之间尽可能均匀地进行划分和通过避免不必要的节点扩展来得到最优解;实验结果表明,提出的2种改进算法,相比于传统的A*算法,不仅能够通过减少搜索空间节省内存和减少任务执行时间,而且能够通过并行分配来提高算法执行时的加速性.

Aiming at the problem for task-processor assignment in distributed computing,two improved algorithms based on A* algorithm are proposed.By analyzing the principle of A* algorithm,the search tree model of applying A* algorithm to task assignment problem is obtained,and by dividing the search tree as evenly as possible among the processing units and by avoiding unnecessary nodes extension,the optimal solution is obtained. The experimental results show that,compared with the traditional A* algorithm,the proposed two improved algorithms can not only save memory and task execution time by reducing search space,but also improve the speedup performance of algorithm execution by parallel assignment.