匈牙利算法MATLAB程序

%%ÓÃÐÙÑÀÀû·¨½âÖ¸ÅÉÎÊÌâ%%CÊÇЧÒæ¾ØÕófunction[y,fval,flag]=Hungary(C)[m,n]=size(C);tempC=C;%%%ÒÔÏÂÁ½¸öÑ­»·Ê¹Ã¿ÐÐÿÁж¼³öÏÖÁãÔªËØfori=1:mtempC(i,:)=tempC(i,:)-min(tempC(i,:));endfori=1:ntempC(:,i)=tempC(:,i)-min(tempC(:,i));endAssignMatrix=zeros(m,n);tempC=TryAssign(tempC);OneNumber=0;fori=1:mforj=1:niftempC(i,j)==infOneNumber=OneNumber+1;break;endendendwhileOneNumbermRow=zeros(m,1);Col=ones(1,n);Line=[];fori=1:mifIsInMatrix(inf,tempC(i,:))==0Line=[Line,i];Row(i)=1;endendfori=LineCur=i;whileCur~=0[Cur,Row,Col]=ZeroCover(tempC,Row,Col,Cur);endendtemp=inf;fori=1:mforj=1:nifRow(i)==1&Col(j)==1&tempC(i,j)temptemp=tempC(i,j);endendendfori=1:mforj=1:niftempC(i,j)==inf|tempC(i,j)==-inftempC(i,j)=0;endendendfori=1:mifRow(i)==1tempC(i,:)=tempC(i,:)-temp;endendforj=1:nifCol(j)==0tempC(:,j)=tempC(:,j)+temp;endendtempC=TryAssign(tempC);OneNumber=0;fori=1:mforj=1:niftempC(i,j)==infOneNumber=OneNumber+1;break;endendendendfori=1:mforj=1:niftempC(i,j)==infAssignMatrix(i,j)=1;endendend%y=AssignMatrix;fori=1:mforj=1:mifAssignMatrix(i,j)==1y(i,1)=i;y(i,2)=j;break;endendendcol=zeros(1,m);row=zeros(1,m);fori=1:mcol=sum(AssignMatrix(i,:));row=sum(AssignMatrix(:,i));endifcol==ones(1,m)&row==ones(1,m)flag=1;elseflag=0;endtemp=C.*AssignMatrix;fval=sum(temp(:));%%¶Ô´¦Àí¹ýµÄÿÐÐÿÁж¼ÓÐÁãÔªËصľØÕóC½øÐÐÊÔÖ¸ÅÉfunctiony=TryAssign(C)[m,n]=size(C);whileIsInMatrix(0,C)==1flag=0;fori=1:mifZeroNumber(C(i,:))==1temp=C(i,:);ZeroRowPos=find(temp==0);C(i,ZeroRowPos)=inf;temp=C(:,ZeroRowPos);ZeroColPos=find(temp==0);forj=ZeroColPosC(j,ZeroRowPos)=-inf;endflag=flag+1;endendfori=1:nifZeroNumber(C(:,i))==1temp=C(:,i);ZeroColPos=find(temp==0);C(ZeroColPos,i)=inf;temp=C(ZeroColPos,:);ZeroRowPos=find(temp==0);forj=ZeroRowPosC(ZeroColPos,j)=-inf;endflag=flag+1;endendifflag==0temp=inf;fori=1:mif(ZeroNumber(C(i,:))temp)&(ZeroNumber(C(i,:))0)temp=ZeroNumber(C(i,:));ZeroRow=i;endendtemp1=find(C(ZeroRow,:)==0);temp2=inf;fori=temp1if(ZeroNumber(C(:,i))temp2)&(ZeroNumber(C(:,i))0)temp2=ZeroNumber(C(:,i));ZeroCol=i;endendC(ZeroRow,ZeroCol)=inf;temp=find(C(ZeroRow,:)==0);fori=tempC(ZeroRow,i)=-inf;endtemp=find(C(:,ZeroCol)==0);fori=tempC(i,ZeroCol)=-inf;endendendy=C;%%ÅжϾØÕóAÖÐÊÇ·ñº¬ÓÐÔªËØa%%ÈôÓУ¬·µ»Ø1£¬·ñÔò·µ»Ø0functiony=IsInMatrix(a,A);[m,n]=size(A);y=0;fori=1:mforj=1:nifA(i,j)==ay=1;break;endendifjnbreak;endend%%ÓÃ×îÉÙµÄÖ±Ï߸²¸ÇËùÓÐÁãÔªËØfunction[y,Row,Col]=ZeroCover(C,Row,Col,Cur)[m,n]=size(C);temp=C(Cur,:);flag=0;Cur=[];fori=1:miftemp(i)==-inf&Col(i)~=0Col(i)=0;Cur=[Cur,i];flag=1;endendifflag==0y=0;elsefori=Curtemp=C(:,i);fori=1:miftemp(i)==inf&Row(i)==0Row(i)=1;y=i;flag=0;[y,Row,Col]=ZeroCover(C,Row,Col,y);break;endendifflag==1y=0;endendend%%¼ÆËãÏòÁ¿AÖеÄÁãÔªËصĸöÊýfunctiony=ZeroNumber(A)y=0;fori=1:length(A)ifA(i)==0y=y+1;endend