%指派問(wèn)題的匈牙利算法，輸入矩陣，a（ij）為i指派給j第i人干第j個(gè)工作
function?[MatchingCost]?=?Hungarian（Perf）
%?
%?[MATCHINGCOST]?=?Hungarian_New（WEIGHTS）
%
%?A?function?for?finding?a?minimum?edge?weight?matching?given?a?MxN?Edge
%?weight?matrix?WEIGHTS?using?the?Hungarian?Algorithm.
%
%?An?edge?weight?of?Inf?indicates?that?the?pair?of?vertices?given?by?its
%?position?have?no?adjacent?edge.
%
%?MATCHING?return?a?MxN?matrix?with?ones?in?the?place?of?the?matchings?and
%?zeros?elsewhere.
%?
%?COST?returns?the?cost?of?the?minimum?matching

%?Written?by:?Alex?Melin?30?June?2006


?%?Initialize?Variables
?Matching?=?zeros（size（Perf））;

%?Condense?the?Performance?Matrix?by?removing?any?unconnected?vertices?to
%?increase?the?speed?of?the?algorithm

??%?Find?the?number?in?each?column?that?are?connected
????num_y?=?sum（~isinf（Perf）1）;
??%?Find?the?number?in?each?row?that?are?connected
????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）;
????
??%?Assemble?Condensed?Performance?Matrix
????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

????%?Ensure?that?a?perfect?matching?exists
??????%?Calculate?a?form?of?the?Edge?Matrix
??????Edge?=?P_cond;
??????Edge（P_cond~=Inf）?=?0;
??????%?Find?the?deficiency（CNUM）?in?the?Edge?Matrix
??????cnum?=?min_line_cover（Edge）;
????
??????%?Project?additional?vertices?and?edges?so?that?a?perfect?matching
??????%?exists
??????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）;
???
%*************************************************
%?MAIN?PROGRAM:?CONTROLS?WHICH?STEP?IS?EXECUTED
%*************************************************
??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

%?Remove?all?the?virtual?satellites?and?targets?and?uncondense?the
%?Matching?to?the?size?of?the?original?performance?matrix.
Matching（x_cony_con）?=?M（1:length（x_con）1:length（y_con））;
Cost?=?sum（sum（Perf（Matching==1）））;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%???STEP?1:?Find?the?smallest?number?of?zeros?in?each?row
%???????????and?subtract?that?minimum?from?its?row
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function?[P_c