求解指派问题的一次性分配算法

One-time assignment algorithm to solve assignment problem

匈牙利算法是求解指派问题的全局最优求解算法,但是经典的匈牙利算法存在着实现难、处理速度慢等不足。提出了一种改进匈牙利算法,对匈牙利算法寻找独立零的次序进行了改进,从而避免了匈牙利算法通常需要进行多次试分配的不足。针对改进前后两种算法的复杂度、运算时间、精确度等进行了对比分析,结果表明,改进的算法是一种高精度的近似最优求解算法;与匈牙利算法相比,改进的算法易于编程实现,且时间花费较低,是一种适用于工程实时应用的有效求解算法。

Hungarian algorithm is an optimal global algorithm to solve assignment problem.However,there are some deficien- cies in the classic Hungarian algorithm,such as the hardly achieving and slowly processing.This paper presents an improved algorithm on the base of the Hungarian algorithm,and improves the order of finding separate zero in Hungarian algorithm, as a result,it avoids the disadvantage of repeating assignment in Hungarian algorithm.By comparing the performance of the two algorithms for improved and classic Hungarian algorithm in complexity,running time and association accuracy,the results show that the improved Hungary arithmetic is a high-precision approximative algorithm,can be easily achieved and fastly processed,and can be applyed to the application of real-time engineering.