狠狠撸

1 题目
某厂生产一种弹子锁具，每个锁具有n个槽，每个槽有m个高度，每个槽的高
度从｛1，2，…，m｝这m个数(单位略)中任取一个，限制至少有一个相邻的槽
高之差等于m-1，且至少有3个不同的槽高。每个槽的高度取遍这m个数且满足上
面这两个限制时生产出一批锁。
对于同一批中两个锁具是否能够互开，有以下试验结果：若二者相对应的 n
个槽的高度中有 n-1 个相同，另一个槽的高度差为 1，则能互开，在其它情形下
不可能互开。将这一批锁按槽高数之和分为奇数(A)和偶数(B)两类。请给出这
两类锁之间的最大匹配。

2 分析
1. 求出所有满足条件的锁，和为奇数的保存在矩阵 LMA 中，和为偶数的保存
在矩阵 LMB 中，这样我们便得到了锁与自然数的映射（矩阵行标）。
2. 建立邻接矩阵，若可以互开则设置相应位置为 1 否则设为 0.
3. 利用 Edmonds 算法求完美匹配。
? 两个数组记录匹配，设 MatA,MatB。例如 MatA(i)=j 表示 A 中第 i 个
元素与 B 中的第 j 个元素相匹配（此时必须有 MatB(j)=i）。
? 三个数组 XYZ 用来求某个未匹配点的增广轨。
? 具体过程有：
a) 初始化 MatA,MatB,X,Y,Z 为 0；
b) 若 MatA 中不存在 0 元素，则表明匹配已经是最大匹配，算法结束。
若 A 中存在未匹配点，任取一未匹配点 i。
c) 将 i 所有相邻结点在 Y 中标记为 i。
d) 若 Y 与 Z 相同，表明 i 没有与之相应的匹配，将 MatA(i)标记为-1，
转至 b。否则设 Y-Z 中第一个元素的下标为 j。若 j 不在匹配中，
则得到一个增广轨 P，从 j 开始逆向得到一条边在匹配和非匹配
中交替出现的路径，取匹配为原匹配与该增广轨的对称差，转至
b。
e) 若 j 在匹配中，则标记 Z(j)=Y(j)。假设 MatB(j)=i（即与 j 相匹
配的元素为 i），记 X(i)=j,并转至 c。
f) 清空 XYZ，转至 b。

3 实现
Edmonds 算法（匈牙利算法）的关键在于寻找增广轨并求原匹配与该增广轨
的对称差，下面结合代码详细说明增广轨的求法：

1. 首先寻找初始匹配，为方便起见可以选取 A 中第一个元素，代码实现：
j = find(AB(1,:), 1);
MatA(1)=j; MatB(j)=1;

2. 接着只要 MatA 中存在 0 元素就表明 A 中存在尚未匹配点（不能匹配的点用-1
表示），为方便起见可以选取第一个 0 元素（设下标为 i）为下次进行匹配的
点，代码如下：
while length(find(MatA==0)) ~= 0 % 存在不匹配的元素
J = find(MatA==0); i = J(1); % 第 i 个元素未被匹配
init = i;

3. 标记 X(i)=0 （标记为 0 方便逆向寻找增广轨，可以做为终结条件），并标记
Y 中所有与 i 相邻的结点为 i，代码如下：
X(i)=0;
J = find(AB(i,:)); % J 为所有与 i 相邻结点
Y(J) = i; j=J(1);

4. 当 Y=Z 时表明不存在 i 的匹配，此时清空 XYZ 并标记 MatA(i)=-1 继续下次尚
未匹配点的匹配，否则当 j 在匹配中时，标记 Z(j)=Y(j)，设与 j 匹配的点为 i，
标记 Y 中所有 I 相邻的结点，并记 Y-Z 中第一个元素的下标为 j。代码如下：
if MatB(j) ~= 0 % j 是匹配点
Z(j) = Y(j);
i = MatB(j);
X(i)=j;
J = find(AB(i,:));
Y(J)=i;
J = find(Y);
JJ = find(Z);
J = setxor(intersect(J, JJ), J);
j=J(1);

5. 如果 j 不在匹配中，则表明已经找到了一个增广轨，接下来就是要用原匹配
与增广轨的对称差来替代原来的匹配，例如最后一次 i=8，时发现 MatB(8)=0
j=8
（即 8 不在匹配中），之后便可以利用 X 和 Z 中的数据来得到一条增广轨：

下标 1 2 3 4 5 6 7 8
X 0 3B 1B 6B
Y NM
Z 1A 6A 5A

得到增广轨后便更新原来匹配，其具体代码实现：
i = Y(j);
MatA(i) = j;
MatB(j) = i;
while X(i)
j = X(i);
i = Z(j);
MatA(i) = j;
MatB(j) = i;
end
break;

6. 最后为方便人机交互，可以用 Matlab GUI 设计简单的界面。
function pushbutton1_Callback(hObject, eventdata, handles)
a = get(handles.edit1, 'String');
b = get(handles.edit2, 'String');
str = Edmonds(str2num(a), str2num(b));
set(handles.edit4, 'String', str);
guidata(hObject, handles);

4 结果
槽数
4 5
高度
4 32 180
5 50 378

5 改进
从结果中可以看到当有 5 个槽 5 个高度时匹配有 378 个，此时建立邻接矩阵
为大于 378*378 的矩阵，随着槽数和高度的增加，该程序对内存空间的要求会很
高，而矩阵中真正有用的标记并不多，故空间利用率是很低的，但此方法的优点
在于可以充分利用 Matlab 的内建函数，思路清晰代码简洁。一种改进方法是不
用邻接矩阵，令每个结点对应一个由其邻接结点构成的向量，这样便可减少空间
需求，同时代码量也会增加，对编程能力要求较高。

6 源码
LockMap.m

function [LMA, LMB] = LockMap(n, m)
% LOCKMAP - 求解满足条件锁并设置相应的映射
% 输入参数：n 表槽数，m 表高度数。
% 输出参数：LMA，LMB 分别为二维矩阵表示自然数到满足条件锁之间的映射。

global jiA ouB ary A B mm N % 调用递归函数时要用到的变量所以
% 设为全局
N = n; mm = m;
jiA=0; ouB=0;
A=[]; B=[];
ary = zeros(1, n);
RecuCal(n);
LMA=A; LMB=B;
[lena, n] = size(LMA);
[lenb, n] =size(LMB);
if lena>lenb
temp = LMA; LMA=LMB;LMB=temp;
temp = lena;lena=lenb;lenb=temp;
end

RecuCal.m

function RecuCal(n)
% RECUCAL - 递归函数
global jiA ouB ary A B mm N
if n ==1
for k=1:mm

ary(1) = k;
Max = max(ary); Min = min(ary);
num = 0; neighbor = 0;
for i=1:N
num = num + (Max-ary(i))*(ary(i)-Min);
if (i~=N)
neighbor = max(neighbor, abs(ary(i)-ary(i+1)));
end
end
if (neighbor > mm-1.5)&&(num > 0.5)
if mod(sum(ary), 2) % 奇数，属于 A 类
jiA = jiA+1;
A(jiA,:) = ary;
else % 偶数，属于 B 类
ouB = ouB+1;
B(ouB,:) = ary;
end
end
end
else
for k=1:mm
ary(n) = k;
RecuCal(n-1);
end
end

BuildMatrix.m

function AB = BuildMatrix(LMA, LMB)
% BUILDMATRIX - 建立邻接矩阵，若 i 与 j 之间可以互开则 AB(i,j)=1，否则为 0。
AB = [];
[lena, n] = size(LMA);
[lenb, n] =size(LMB);

for i = 1:lena
for j=1:lenb
tmp = 0;
for k=1:n
tmp = tmp + abs(LMA(i,k)-LMB(j,k));
end
if tmp == 1
AB(i, j)=1;
end

end
end

Edmonds.m
function str = Edmonds(n, m)
% EDMONDS - Edmonds 算法寻找完美匹配

str = [];
[LMA, LMB] = LockMap(n, m);
AB = BuildMatrix(LMA, LMB);
lena = length(LMA);
lenb = length(LMB);
if lena==0
disp('其中一个分组为空，无法匹配'); %当 n=m=3 时只有偶数组无奇数组，不能完成
匹配
return;
end
MatA = zeros(1, lena);
MatB = zeros(1, lenb);
X = MatA; Y=MatB; Z=Y;
NumNoMat = 0; % 无法匹配的点的个数
% 最初匹配，只有一个匹配
j = find(AB(1,:), 1);
MatA(1)=j; MatB(j)=1;

while length(find(MatA==0)) ~= 0 % 存在不匹配的元素
J = find(MatA==0); i = J(1); % 第 i 个元素未被匹配
init = i; X(i)=0;
J = find(AB(i,:)); % J 为所有与 i 相邻结点
Y(J) = i; j=J(1);
while ~isempty(find(Y~=Z))
if MatB(j) ~= 0 % j 是匹配点
Z(j) = Y(j);
i = MatB(j);
X(i)=j;
J = find(AB(i,:));
Y(J)=i;
J = find(Y);
JJ = find(Z);
J = setxor(intersect(J, JJ), J);
j=J(1);
else % j 不是匹配点
i = Y(j);

MatA(i) = j;
MatB(j) = i;
while X(i)
j = X(i);
i = Z(j);
MatA(i) = j;
MatB(j) = i;
end
break;
end
end
% 如果 Y==Z 则表明该点没有与之相应的匹配，即不存在完美匹配，在 MatA 中标
% 记为－1。
if isempty(find(Y~=Z, 1))
NumNoMat = NumNoMat + 1;
MatA(init) = -1;
end
X(1:lena)=0; Y(1:lenb)=0; Z=Y;
end
total = 0;
for i=1:lena
k = MatA(i);
if k<=0 continue; end % k<=0 时表明匹配不存在
stra = ''; strb = '';
for j=1:n
stra = [stra, num2str(LMA(i, j)), ' '];
strb = [strb, num2str(LMB(k, j)), ' '];
end
str = [str, stra, '------ ', strb, 10];
total = total + 1;
end
str = [str, '匹配个数有：', num2str(total)];

GUI1.m
function varargout = GUI1(varargin)
gui_Singleton = 1;
gui_State = struct('gui_Name', mfilename, ...
'gui_Singleton', gui_Singleton, ...
'gui_OpeningFcn', @GUI1_OpeningFcn, ...
'gui_OutputFcn', @GUI1_OutputFcn, ...
'gui_LayoutFcn', [] , ...
'gui_Callback', []);
if nargin && ischar(varargin{1})
gui_State.gui_Callback = str2func(varargin{1});

end

if nargout
[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT

% --- Executes just before GUI1 is made visible.
function GUI1_OpeningFcn(hObject, eventdata, handles, varargin)
handles.output = hObject;


function varargout = GUI1_OutputFcn(hObject, eventdata, handles)

varargout{1} = handles.output;

a = get(handles.edit1, 'String');
b = get(handles.edit2, 'String');
str = Edmonds(str2num(a), str2num(b));
set(handles.edit4, 'String', str);

function edit1_Callback(hObject, eventdata, handles)

input = str2num(get(hObject, 'String'));

function edit1_CreateFcn(hObject, eventdata, handles)

if ispc && isequal(get(hObject,'BackgroundColor'),
get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end


input = str2num(get(hObject, 'String'));


end

function slider1_Callback(hObject, eventdata, handles)

function slider1_CreateFcn(hObject, eventdata, handles)

if isequal(get(hObject,'BackgroundColor'),
set(hObject,'BackgroundColor',[.9 .9 .9]);
end

function text_result_Callback(hObject, eventdata, handles)

function text_result_CreateFcn(hObject, eventdata, handles)

end



end


set(handles.edit4, 'String', '');

狠狠撸

锁具装箱

Recommended

More Related Content

What's hot (19)

Viewers also liked (7)

Similar to 锁具装箱 (20)

锁具装箱