Computer Engineering and Applications 计算机工程与应用
2011， 47 （18）
135
求解指派问题的一次性分配算法
周 莉 1， 张维华 2， 徐射雕 1 1 ZHOU Li ， ZHANG Weihua2， XU Shediao1
1.鲁东大学 信息科学与工程学院， 山东 烟台 264025 2.鲁东大学 资产处， 山东 烟台， 264025 1.School of Information Science and Engineering， Ludong University， Yantai， Shandong 264025， China 2.Assets Department， Ludong University， Yantai， Shandong 264025， China ZHOU Li， ZHANG Weihua， XU Shediao.One-time assignment algorithm to solve assignment puter Engineering and Applications， 2011， 47 （18） ： 135-138. 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 摘 要： 匈牙利算法是求解指派问题的全局最优求解算法， 但是经典的匈牙利算法存在着实现难、 处理速度慢等不足。提出了一
4 两种算法的比较 4.1 经典匈牙利算法示例
例1 min é 3 9 10 12ù 3 é0 6 7 9ù é0 6 7 8 ù ê 13 1 2 16 17ú 1 0 4 5ú 1 0 4 4 ú ê ú 12 ê ú®ê ê ú® ®ê ê ú 14 ê ê ú ê ê ú 15 16 14 15 ú 1 2 0 1 1 2 0 0ú ê ú 11 12 15 16 û 11 ë0 1 4 5û ë0 1 4 4û ë 1 minFra bibliotek3.2
改进算法原理
改进算法是一种一次性分配算法， 也是一种启发式算法，
其思想是： （1） 一个独立零既是行中的独立零， 又是列中的独 立零， 则根据最优分配的思想， 该元素为最优解分量的可能性 极大； （2） 位于同一列 （行） 中的独立零， 其所在行 （列） 中次小 值越大， 选择该独立零的局部最优效果越好。对于出现多种 同一列或同一行的独立零的情况， 次小值越大， 越有必要对其 行或列中的零元素优先指派； （3） 位于同一列 （行） 中的独立零 在指派确定后， 就会出现未指派行 （列） 中没有零元素的情况， 为确保分配能够一次性完成， 需要对该行 （列） 中的所有元素 减去本行 （列） 的次小元素， 及时构造出该行 （列） 的零元素。
é⊗ ê1 ê ê1 / ë0 é⊗ ê ê5 ê ê5 ê ê / ë0 6 7 ⊗ 4 2 ⊗ 1 4 - - Ú 10 11 ⊗ 8 6 ⊗ 1 0 / 8ù é0 10 11 8ù 4ú - ¾¾ ê5 0 8 4ú ú® ¾ ¾ ¾ ¾ ¾ ¾® ê ú- ¾ ê5 6 0 0ú ú ê 0 /ú ë0 1 0 0û 4û Ú 8 ù é1 ú ê0 4ú ú®ê ê0 0 /ú ê ú ú ⊗û ë0 0 1 0 0 0 0 1 0 0ù 0ú ú ú 0ú 1û
[1]
2
经典匈牙利算法介绍
匈牙利算法作为求解指派问题的经典算法[2]， 其优点是在
避免程序陷入无限循环的情况下， 可以求得指派问题精确的 全局最优解。但随着代价矩阵维数的增加， 该算法的时间花 费变长， 主要原因是在多数情况下， 该算法不能经一次分配便 求得问题的最优解， 这就需要通过多次变换代价矩阵进行迭 代求解， 从而使程序运算时间变长。 匈牙利算法的具体步骤如下：
种改进匈牙利算法， 对匈牙利算法寻找独立零的次序进行了改进， 从而避免了匈牙利算法通常需要进行多次试分配的不足。针 对改进前后两种算法的复杂度、 运算时间、 精确度等进行了对比分析， 结果表明， 改进的算法是一种高精度的近似最优求解算法； 与匈牙利算法相比， 改进的算法易于编程实现， 且时间花费较低， 是一种适用于工程实时应用的有效求解算法。 关键词： 指派问题； 匈牙利算法； 一次性 DOI： 10.3778/j.issn.1002-8331.2011.18.039 文章编号： 1002-8331 （2011） 18-0135-04 文献标识码： A 中图分类号： TP311
1
引言
日常生活中经常会遇到这样的问题： 某单位需完成 N 项
要经过多次试分配的不足。并对改进算法的复杂度、 运算时 间、 精确度等进行了评测， 在确认改进的算法确实比传统的匈 牙利算法有所提高的基础上， 对两种算法进行了编程实现。 算例分析结果表明， 改进的算法是一种高精度的近似最优求 解算法， 与经典匈牙利算法相比， 一次性指派算法易于理解 与实现， 且时间花费较低， 是求解指派问题的一种有效求解 算法。
3.3
改进算法具体步骤
改进匈牙利算法的步骤如下： 步骤 1 使指派问题的代价矩阵经变换， 在各行各列中都
出现零元素。 步骤 2 若在一行 （列） 中的独立零， 又是它所在列 （行） 的 独立零， 则选中该零元素， 划掉它所在的行和列。 步骤 3 若同一列 （行） 存在多个独立零， 则在它们的行 （列） 中找出各自的次小元素， 选中次小值最大的行 （列） 中的 独立零， 划掉它所在的行和列， 然后把刚才与其比较的行 （列） 中的所有元素减去本行 （列） 的最小元素。若上述情况不止一 种， 则优先分配次小元素最大的行或列中的独立零。 步骤 4 独立零所在的列 （行） 的其他零不是其行 （列） 中的 独立零， 则选取该独立零， 划掉所在列 （行） 的其他的零元素。 步骤 5 若所有的行 （列） 中都不存在独立零， 则和匈牙利 算法一样， 任意选出零元素最少的行 （列） 中的一个零， 若行中 零元素个数一样就选择列 （行） 中零元素个数最少的零 （多数 礼让少数） 。 步骤 6 重复步骤 2~5， 直到找出 n 个零为止。
136
2011， 47 （18）
Computer Engineering and Applications 计算机工程与应用
步骤 1 使指派问题的代价矩阵经变换， 在各行各列中都 出现零元素。 （1） 从代价矩阵的每行元素中减去该行的最小元素； （2） 再从所得代价矩阵的每列元素中减去该列的最小元素。 步骤 2 试指派， 寻求最优解， 按以下步骤进行： 经过第一步变换后， 代价矩阵中每行每列都已存在零元 素； 但需找出 n 个独立的零元素。若能找出， 就以这些独立零 元素对应解矩阵 ( xij) 中的元素为 1， 其余为 0， 得到最优解。当 可用观察法、 试探法去找出 n 个独立零元素。若 n n 较小时， 较大， 则需要按一定顺序去找， 常用步骤如下： （1） 从只有一个零元素的行 （列） 开始， 给这个零元素加 圈。这表示对这行所代表的人， 只有一项任务可指派。然后 划去画圈的列 （行） 中的其他零元素。这表示这列代表的任务 已指派完， 不必再考虑别人了。 （2） 给只有一个零元素列 （行） 的零元素加圈， 然后划去加 圈的元素所在行 （列） 的零元素。 （3） 反复进行 （1） 、 （2） 两步， 直到所有零元素都被圈出或 划掉为止。 （4） 若仍有没有画圈的零元素， 且同行 （列） 的零元素至少 有两个， 这可用不同的方案去试探。从剩有零元素最少的行 （列） 开始， 比较这行零元素所在列中零元素的数目， 选择列中 零元素最少的零元素加圈， 然后划掉同行同列的其他零元 素。反复进行， 直到所有零元素都圈出或划掉为止。 （5） 若画圈零元素的数目 m 等于矩阵的维数 n ， 那么已得 到指派问题的最优解； 若 m<n， 则转下一步。 步骤 3 做最少的直线覆盖所有零元素， 以确定该代价矩 阵中能找到最多的独立零元素数。按以下步骤进行： （1） 对没有画圈的行打对号； （2） 对已经打对号的行中有划掉零元素的列打对号； （3） 再对打有对号的列中含画圈元素的行打对号； （4） 重复 （2） 、 （3） ， 直到得不出新的打对号的行、 列为止； （5） 对没有打对号的行画一横线， 对打对号的列画一纵 线， 得到覆盖所有零元素的最少直线数。 步骤 4 经过上述变换得到新的代价矩阵。在没有被直线 覆盖的元素中找出最小元素， 并对没划直线行的各元素都减 去该最小元素， 对划直线列的各元素都加上该最小元素， 得到 新矩阵， 转步骤 2。