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

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (18): 135-138.

• 数据库、信号与信息处理 • 上一篇下一篇

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

周莉1，张维华2，徐射雕1

1.鲁东大学信息科学与工程学院，山东烟台 264025
2.鲁东大学资产处，山东烟台，264025

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-06-21 发布日期:2011-06-21

One-time assignment algorithm to solve assignment problem

ZHOU Li1，ZHANG Weihua2，XU Shediao1

1.School of Information Science and Engineering，Ludong University，Yantai，Shandong 264025，China
2.Assets Department，Ludong University，Yantai，Shandong 264025，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-06-21 Published:2011-06-21

摘要/Abstract

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

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

Abstract: Hungarian algorithm is an optimal global algorithm to solve assignment problem.However，there are some deficiencies 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.

Key words: assignment problem, Hungarian algorithm, one-time

周莉1，张维华2，徐射雕1. 求解指派问题的一次性分配算法[J]. 计算机工程与应用, 2011, 47(18): 135-138.

ZHOU Li1，ZHANG Weihua2，XU Shediao1. One-time assignment algorithm to solve assignment problem[J]. Computer Engineering and Applications, 2011, 47(18): 135-138.

[1]	景庆阳，李波. 结合改进角点检测的优化核相关滤波方法[J]. 计算机工程与应用, 2021, 57(18): 194-203.
[2]	高瑾1，白亮2. 基于网页浏览器和在线服务的安全密钥设计[J]. 计算机工程与应用, 2018, 54(17): 71-76.
[3]	刘兵兵1，周伟平1，沈玲2. 灰色线性双层指派问题的智能全局优化方法[J]. 计算机工程与应用, 2016, 52(8): 38-42.
[4]	杨皎平1，高雷阜2，王俊2. 装卸联盟车辆路径问题及两阶段优化方法[J]. 计算机工程与应用, 2011, 47(14): 217-221.
[5]	李岩,郭强. 非确定型指派问题的求解算法[J]. 计算机工程与应用, 2009, 45(15): 61-63.
[6]	朱郑州,吴中福,吴开贵,钟将. 基于本体和二部图的网格服务发现算法研究[J]. 计算机工程与应用, 2008, 44(1): 8-10.
[7]	崔岩,刘永杰,周玉洁. （50元）（1160元）一种适用于移动电子商务的微支付方案[J]. 计算机工程与应用, 2005, 41(35期): 0-.

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

One-time assignment algorithm to solve assignment problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics