function?[MatchingCost]?=?Hungarian（Perf）
%?[MATCHINGCOST]?=?Hungarian_New（WEIGHTS）
%?匈牙利算法
%?給定一個(gè)n?x?n矩陣的邊權(quán)矩陣，使用匈牙利算法求解最小邊權(quán)值和問題，類似最小樹問題
%?如果矩陣中出現(xiàn)inf，則表示沒有邊與之相連
%?輸出：
%???????Matching?為一個(gè)?n?x?n的矩陣，只有0?和?1
%????????COST?為對應(yīng)Matching處為1所在位置的元素和

?%?初始化變量
?Matching?=?zeros（size（Perf））;

??%?移除Inf，加速算法執(zhí)行效率
??%?針對每一列找inf
????num_y?=?sum（~isinf（Perf）1）;
??%?針對每一行找inf
????num_x?=?sum（~isinf（Perf）2）;
????
??%?Find?the?columns（vertices）?and?rows（vertices）?that?are?isolated
????x_con?=?find（num_x~=0）;
????y_con?=?find（num_y~=0）;
????
??%?縮減矩陣
????P_size?=?max（length（x_con）length（y_con））;
????P_cond?=?zeros（P_size）;
????P_cond（1:length（x_con）1:length（y_con））?=?Perf（x_cony_con）;
????if?isempty（P_cond）
??????Cost?=?0;
??????return
????end

??????%?計(jì)算邊權(quán)矩陣
??????Edge?=?P_cond;
??????Edge（P_cond~=Inf）?=?0;
??????%?修正權(quán)效矩陣
??????cnum?=?min_line_cover（Edge）;
????
??????%?對未標(biāo)記的行和已標(biāo)記的列畫縱、橫線P
??????Pmax?=?max（max（P_cond（P_cond~=Inf）））;
??????P_size?=?length（P_cond）+cnum;
??????P_cond?=?ones（P_size）*Pmax;
??????P_cond（1:length（x_con）1:length（y_con））?=?Perf（x_cony_con）;
???
%*************************************************
%?主要求解步驟
%*************************************************
??exit_flag?=?1;
??stepnum?=?1;
??while?exit_flag
????switch?stepnum
??????case?1
????????[P_condstepnum]?=?step1（P_cond）;
??????case?2
????????[r_covc_covMstepnum]?=?step2（P_cond）;
??????case?3
????????[c_covstepnum]?=?step3（MP_size）;
??????case?4
????????[Mr_covc_covZ_rZ_cstepnum]?=?step4（P_condr_covc_covM）;
??????case?5
????????[Mr_covc_covstepnum]?=?step5（MZ_rZ_cr_covc_cov）;
??????case?6
????????[P_condstepnum]?=?step6（P_condr_covc_cov）;
??????case?7
????????exit_flag?=?0;
????end
??end

%?移除所有的虛擬節(jié)點(diǎn)
Matching（x_cony_con）?=?M（1:length（x_con）1:length（y_con））;
Cost?=?sum（sum（Perf（Matching==1）））;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%???STEP?1:找每行最小元素
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function?[P_condstepnum]?=?step1（P_cond）

??P_size?=?length（P_cond）;
??
??%?Loop?throught?each?row
??for?ii?=?1:P_size
????rmin?=?min（P_cond（ii:））;
????P_cond（ii:）?=?P_cond（ii:）-rmin;
??end

??stepnum?=?2;
??
%**************************************************************************??
%???STEP?2:?尋找P_cond中的0元素
%**************************************************************************
function?[r_covc_covMstepnum]?=?step2（P_cond）

%?定義變量
??P_size?=?length（P_cond）;
??r_cov?=?zeros（P_size1）;??%?記錄?元素為0?所在的行
??c_cov?=?zeros（P_size1）;??%?記錄?元素為0?所在的列
??M?=?zeros（P_size）;????????%?A?mask?that?shows?if?a?position?is?starred?or?primed
??
??for?ii?=?1:P_size
????for?jj?=?1:P_size
??????if?P_cond（iijj）?==?0?&&?r_cov（ii）?==?0?&&?c_cov（jj）?==?0
????????M（iijj）?=?1;
????????r_cov（ii）?=?1;
????????c_cov（jj）?=?1;
??????end
????end
??end
??
%?重新初始化操作
??r_cov?=?zeros（P_size1）;??%?A?vector?that?shows?if?a?row?is?covered
??c_cov?=?

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件???????7369??2018-06-29?12:59??第26章\Hungarian.m

?????文件???????3798??2018-06-29?12:59??第26章\Hungarian_algorithm.m

?????文件????????147??2018-06-29?12:59??第26章\ysw1.m

?????目錄??????????0??2018-08-20?17:45??第26章

-----------?---------??----------?-----??----

????????????????11314????????????????????4