《最佳匹配的matlab程序》由会员分享，可在线阅读，更多相关《最佳匹配的matlab程序（8页珍藏版）》请在金锄头文库上搜索。
1、最佳匹配的最佳匹配的 MATLABMATLAB 程序程序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 的
2、两个端点是关于 M 的非饱和点，则它就称%为可增广道路。% 5、M 是 G 的最大匹配当且仅当 G 中不存在关于 M 的可增广道路。% 6、设 r 是二分图 G 的最大匹配数，s 是其邻接矩阵的最小覆盖数，则有 r=s。%=%实际意义：% 指派问题：需要完成 n1 项任务，有 n2 个人可以承担这些任务。由于每个人的专长不同，%完成不同任务的成本与效率也不同。应如何分配任务才能使得总成本最小或者总效益最大。%=%算法及步骤：% 使用匈牙利算法求解最佳匹配问题，基于最小成本的问题求解。% 时间复杂度 O(mn)。% step1：使成本/效益矩阵经过变换，在各行各列中都出现 0 元素。% （1）成
3、本/效益矩阵每行的元素减去该行的最小元素；% （2）再将所得的成本/效益矩阵每列的元素减去该列的最小元素。% step2：进行指派，寻求最优解。% （1）从只有一个 0 元素的行（列）开始，给这个 0 元素加圈，这表示对这行所代表% 的人而言，只有一种任务可以指派。然后划去该加圈 0 元素所在列（行）的其他 0 元% 素，表示该列所代表的任务已经指派完，无需考虑其他人。% （2）给只有一个 0 元素的列（行）的 0 元素加圈，同时划去该 0 元素所在行（列）的% 其他 0 元素。% （3）重复进行（1） 、 （2）两步，直至所有 0 元素都被加圈或划去为止。% （4）若仍存在未加圈未划去的 0
4、 元素，且同行（列）的 0元素至少有两个（表示对% 这个可以从两项任务中指派其一） ，则对同行同列中其他 0元素总数最少的 0 元素加% 圈（表示选择性多的要礼让选择性少的） ，并划去同行同列中的其他 0 元素。可反% 复进行，直至所有 0 元素都被加圈或划去为止。% （5）若加圈的 0 元素数量 m 等于矩阵的阶数 n（这里矩阵的阶数指成本/效益矩阵行% 数、列数中的较小值） ，则指派问题已经得到最优解；若mn，则转 step3。% step3：作最少的直线覆盖所有的 0 元素，以确定成本/效益矩阵中的独立 0 元素。% （1）对没有加圈 0 元素的行打勾；% （2）对已打勾的行中被划去 0
5、 元素所在列打勾；% （3）对打勾的列中的加圈 0 元素所在行打勾；% （4）重复（2） 、 （3）直至找不出新的可打勾的行、列为止；% （5）选取未打勾的行和已打勾的列，即可覆盖全部 0 元素。% （6）选取的行、列数之和（即所作直线数）为 l。若ln，说明必须再变换当前的% 成本/效益矩阵才能找到 n 个独立的 0 元素，为此转step4；若 l=n 而 mn，则返回% step2(4)，另行试探。% step4：在未被直线覆盖的部分中找出最小元素。在打勾的行的各元素减去该最小元素，% 在打勾的列的各元素加上该最小元素，以保证原来的 0 元素不变。删除所有打勾、% 加圈、划去记号，返回 s
6、tep2。%=%函数的使用：% 输入：% （1）成本/效益矩阵 C；% （2）匹配类型 type：min表示求最小成本，max表示求最大效益。% 输出：% （1）总最佳成本/效益的值 val；% （2）最佳匹配矩阵 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(i,:)-min_ro
7、w(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=1do=0;for i=1:rowp=0;t=0;for j=1:columnif a(i,j)=0 t=j;end;end;if p=1
8、 %该行只有一个未标记且未划去的零元素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 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 end;if do=0 %不存在只有一个未标记且未
9、划去的零元素的行或列，则选影响最小的 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 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：作最少的直线覆盖所有
10、 0 元素row_select=zeros(1,row);column_select=zeros(1,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 %对已打勾的列中加圈元素所
11、在的行打勾if column_select(j)=1for i=1:rowif flag(i,j)=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 lnx=max(max(abs(a);for i=1:row %寻找最小非 0 元素for j=1:columnif a(i,j)=0 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);
