计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2011年
18期
135-138,152
,共5页
指派问题%匈牙利算法%一次性
指派問題%匈牙利算法%一次性
지파문제%흉아리산법%일차성
匈牙利算法是求解指派问题的全局最优求解算法,但是经典的匈牙利算法存在着实现难、处理速度慢等不足.提出了一种改进匈牙利算法,对匈牙利算法寻找独立零的次序进行了改进,从而避免了匈牙利算法通常需要进行多次试分配的不足.针对改进前后两种算法的复杂度、运算时间、精确度等进行了对比分析,结果表明,改进的算法是一种高精度的近似最优求解算法;与匈牙利算法相比,改进的算法易于编程实现,且时间花费较低,是一种适用于工程实时应用的有效求解算法.
匈牙利算法是求解指派問題的全跼最優求解算法,但是經典的匈牙利算法存在著實現難、處理速度慢等不足.提齣瞭一種改進匈牙利算法,對匈牙利算法尋找獨立零的次序進行瞭改進,從而避免瞭匈牙利算法通常需要進行多次試分配的不足.針對改進前後兩種算法的複雜度、運算時間、精確度等進行瞭對比分析,結果錶明,改進的算法是一種高精度的近似最優求解算法;與匈牙利算法相比,改進的算法易于編程實現,且時間花費較低,是一種適用于工程實時應用的有效求解算法.
흉아리산법시구해지파문제적전국최우구해산법,단시경전적흉아리산법존재착실현난、처리속도만등불족.제출료일충개진흉아리산법,대흉아리산법심조독립령적차서진행료개진,종이피면료흉아리산법통상수요진행다차시분배적불족.침대개진전후량충산법적복잡도、운산시간、정학도등진행료대비분석,결과표명,개진적산법시일충고정도적근사최우구해산법;여흉아리산법상비,개진적산법역우편정실현,차시간화비교저,시일충괄용우공정실시응용적유효구해산법.