最佳匹配的MATLAB程序.doc

最佳匹配的MATLAB程序function val,flag=PerfectMatch(C,type)%=%相关概念：% 1、令M是图G的边子集，若M中任意两条边都没有共同的结点，则称M是G的一个匹配；其%中与M的边关联的结点称为饱和点，否则成为非饱和点。% 2、设M是G=（V，E）的一个匹配，若对G的任意匹配M都有|M|=|M|，则称M是G的一%个最大匹配。% 3、给定了G的一个匹配M，G中属于M与不属于M的边交替出现的道路称为交互道路。% 4、设P是G中关于匹配M的一条交互道路，若P的两个端点是关于M的非饱和点，则它就称%为可增广道路。% 5、M是G的最大匹配当且仅当G中不存在关于M的可增广道路。% 6、设r是二分图G的最大匹配数，s是其邻接矩阵的最小覆盖数，则有r=s。%=%实际意义：% 指派问题：需要完成n1项任务，有n2个人可以承担这些任务。由于每个人的专长不同，%完成不同任务的成本与效率也不同。应如何分配任务才能使得总成本最小或者总效益最大。%=%算法及步骤：% 使用匈牙利算法求解最佳匹配问题，基于最小成本的问题求解。% 时间复杂度O(mn)。% step1：使成本/效益矩阵经过变换，在各行各列中都出现0元素。% （1）成本/效益矩阵每行的元素减去该行的最小元素；% （2）再将所得的成本/效益矩阵每列的元素减去该列的最小元素。% step2：进行指派，寻求最优解。% （1）从只有一个0元素的行（列）开始，给这个0元素加圈，这表示对这行所代表% 的人而言，只有一种任务可以指派。然后划去该加圈0元素所在列（行）的其他0元% 素，表示该列所代表的任务已经指派完，无需考虑其他人。% （2）给只有一个0元素的列（行）的0元素加圈，同时划去该0元素所在行（列）的% 其他0元素。% （3）重复进行（1）、（2）两步，直至所有0元素都被加圈或划去为止。% （4）若仍存在未加圈未划去的0元素，且同行（列）的0元素至少有两个（表示对% 这个可以从两项任务中指派其一），则对同行同列中其他0元素总数最少的0元素加% 圈（表示选择性多的要礼让选择性少的），并划去同行同列中的其他0元素。可反% 复进行，直至所有0元素都被加圈或划去为止。% （5）若加圈的0元素数量m等于矩阵的阶数n（这里矩阵的阶数指成本/效益矩阵行% 数、列数中的较小值），则指派问题已经得到最优解；若mn，则转step3。% step3：作最少的直线覆盖所有的0元素，以确定成本/效益矩阵中的独立0元素。% （1）对没有加圈0元素的行打勾；% （2）对已打勾的行中被划去0元素所在列打勾；% （3）对打勾的列中的加圈0元素所在行打勾；% （4）重复（2）、（3）直至找不出新的可打勾的行、列为止；% （5）选取未打勾的行和已打勾的列，即可覆盖全部0元素。% （6）选取的行、列数之和（即所作直线数）为l。若ln，说明必须再变换当前的% 成本/效益矩阵才能找到n个独立的0元素，为此转step4；若l=n而mn，则返回% step2(4)，另行试探。% step4：在未被直线覆盖的部分中找出最小元素。在打勾的行的各元素减去该最小元素，% 在打勾的列的各元素加上该最小元素，以保证原来的0元素不变。删除所有打勾、% 加圈、划去记号，返回step2。%=%函数的使用：% 输入：% （1）成本/效益矩阵C；% （2）匹配类型type：min表示求最小成本，max表示求最大效益。% 输出：% （1）总最佳成本/效益的值val；% （2）最佳匹配矩阵flag。%=x=max(max(abs(C);if min(type=min)=1 a=C;else a=x-C;end;row,column=size(C); %求出行数和列数n=min(row,column); %求出最大匹配数量%step1：使各行各列都出现零元素min_row=min(a);for i=1:row %每行减去该行的最小值 a(i,:)=a(i,:)-min_row(i);end;min_column=min(a);for j=1:column %每列减去该列的最小值 a(:,j)=a(:,j)-min_column(j);end;l=0; m=0; %m=sum(sum(flag)用以记录独立的0元素while mn %step2：指派 flag=zeros(row,column); %记录被圈的元素，即独立零元素的位置 cancel=zeros(row,column); %记录被划去的元素 do=1; while do=1 do=0; for i=1:row p=0; t=0; for j=1:column if a(i,j)=0 & flag(i,j)=0 & cancel(i,j)=0 %是未标记且未划去的零元素 p=p+1; t=j; end; end; if p=1 %该行只有一个未标记且未划去的零元素 do=1; %表示有操作 flag(i,t)=1; %加圈 cancel(find(a(:,t)=0),t)=1; %划去 cancel(i,t)=0; end; end; for j=1:column p=0; t=0; for i=1:row if a(i,j)=0 & flag(i,j)=0 & cancel(i,j)=0 %是未标记且未划去的零元素 p=p+1; t=i; end; end; if p=1 %该列只有一个未标记且未划去的零元素 do=1; %表示有操作 flag(t,j)=1; %加圈 cancel(t,find(a(t,:)=0)=1; %划去 cancel(t,j)=0; end; end; if sum(sum(a & (flag | cancel)|(a & flag & cancel)=0 %所有0元素都被加圈或划去 break; end; if do=0 %不存在只有一个未标记且未划去的零元素的行或列，则选影响最小的0元素加圈 do=1; while do=1 do=0; I=0; J=0; for i=1:row q=2*n; for j=1:column if a(i,j)=0 & flag(i,j)=0 & cancel(i,j)=0 if length(find(a(i,:)=0)+length(find(a(:,j)=0)-2q I=i; J=j; q=length(find(a(i,:)=0)+length(find(a(:,j)=0)-2; end; end; end; end; if I=0 flag(I,J)=1; cancel(I,find(a(I,:)=0)=1; cancel(find(a(:,J)=0),J)=1; cancel(I,J)=0; do=1; end; end; end; end; %while do=1 %stpe3：作最少的直线覆盖所有0元素 row_select=zeros(1,row); column_select=zeros(1,column); for i=1:row %对没有标记的行打勾 if sum(flag(i,:)=0 row_select(i)=1; end; end; l=0; l_save=1; while l_save=l l_save=l; for i=1:row %对已打勾的行中划去元素所在的列打勾 if row_select(i)=1 for j=1:column if cancel(i,j)=1 column_select(j)=1; end; end; end; end; for j=1:column %对已打勾的列中加圈元素所在的行打勾 if column_select(j)=1 for i=1:row if flag(i,j)=1 row_select(i)=1; end; end; end; end; end; %while l_save=l l=(row-sum(row_select)+sum(column_select); %选取未打勾的行和已打勾的列，即可覆盖所有0元素 %step4：若未达到最大匹配，则需要增加0元素的数量 if ln x=max(max(abs(a); for i=1:row %寻找最小非0元素 for j=1:column if a(i,j)=0 & a(i,j)x & row_select(i)=1 & column_select(j)=0 x=a(i,j); end; end; end; for i=1:ro