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