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

One-time assignment algorithm to solve assignment problem

作　　者：周莉[1] 张维华[2] 徐射雕[1] 

机构地区：[1]鲁东大学信息科学与工程学院,山东烟台264025 [2]鲁东大学资产处,山东烟台264025

出　　处：《计算机工程与应用》2011年第18期135-138,152,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60672140);山东省自然科学基金(No.ZR2009GM001);山东省高校科技计划项目(No.J09LG01);鲁东大学学科建设经费资助项目~~

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

关 键 词：指派问题 匈牙利算法 一次性 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]