锁具装箱

班级： 姓名： 学号： 信计92

雍宏巍 09092049

摘要

本文主要讨论了锁具装箱问题中n个槽m个高度时锁具的个数和槽高和为奇数和偶数两类锁之间的最大匹配问题。对于前者主要利用matlab编程，结合m进制数的思想和判断条件，得到了任意给定一组n和m均可以根据程序求出锁具的个数的结果。特别的对于4个槽5个高度求出一共有114中锁具。对于第二个问题，同样采用计算机编程的方法来做，采用邻接矩阵存储，利用matlab结合Edmonds算法和大基数基匹配矩阵的算法，求得最大匹配，通过建立每种锁具和平面上点的一一对应关系，将最后结果以附图形式给出。方法科学，结果理想。

一．问题叙述

某厂生产一种弹子锁具，每个锁具有n个槽，每个槽有m个高度，每个槽的高度从｛1，2，…，m｝这m个数(单位略)中任取一个，限制至少有一个相邻的槽高之差等于m-1，且至少有3个不同的槽高。每个槽的高度取遍这m个数且满足上面这两个限制时生产出一批锁。求一批锁的把数。

对于同一批中两个锁具是否能够互开，有以下试验结果：若二者相对应的 n个槽的高度中有 n-1个相同，另一个槽的高度差为1，则能互开，在其它情形下不可能互开。将这一批锁按槽高数之和分为奇数(A)和偶数(B)两类。请给出这两类锁之间的最大匹配。主要考虑 4个槽，5个高度的情况

二．问题分析

该问题主要分为两个部分，第一部分为符合条件的一批所的把数，第二部分为图论内容，求最大匹配。第一部分可以采用枚举法，利用计算机编程来解决，而且很容易实现。第二部分，首先要将图存成邻接矩阵，然后图论中的一些算法，例如Edmonds算法来解决。由于所涉及的锁具数目较多，结果不能以数据显示，太占篇幅，最好以图的形式展示。

三．问题求解

3.1对于n个槽m个高度求一批锁具的数量

求解一批锁具的数量有多种方法，比如排列组合法，递推法，图论方法等。但

这里的n和m未知时这些方法往往比较复杂，需要较多的思考。这里我们采用计算机求解锁具数目的方法。基本思路为穷举法。对于所有可能的槽高组合进行一一验证，符合条件的槽高组合记录下来并计数。

首先要解决的是循环问题，若对每一个槽的槽高进行循环，则要采用n个for循环，由于n的数目未定，便无法实现。但是可以确定的是所有可能的槽高组合一共有mn种组合，我们能否只用一个for循环来实现呢？答案是可以的，采用m进制数的换算思想便可以实现。

我们可以让整数b在1到mn之间取值。将b转换为m进制数，将其每个数位上的数字提取出来。每个数字加1便是槽高的一个组合。

3.1.1m进制数的转换

对0到m-1之间给定的一个整数b，

nbb1mn1b2mn2bimnibn1mbn

b-b1mn1b其第一位数字b1n1；第二位数为b2，第三位数n2mmi1njb-bmjb-b1mn1-b2mn2j1； b3；……对于第i位数binin3mm

这样的话我们就可以将b所对应的m进制数的每一位数提取出来，对每一个数加一，以n维向量a来存储。这样的话便可以用一个for循环来实现穷举。

3.1.2符合条件的槽高组合判断

依据题目有满足要求的槽高需具备两个条件:一是有三个不同的槽高，二是、有相邻高差为m-1的情况。

1.首先来看第一个条件，要有三个高度的槽。也就是说所有槽高除了槽高的最大值和最小值以外还应有其他取值。即除了max(a)和min(a)以外还应有其他值。以

a(i)表示a的第i个分量，若a(i)为max(a)或min(a)，那么

(max(a)a(i))(a(i)min(a))必然为零。若a(i)不为max(a)或min(a)，则(max(a)a(i))(a(i)min(a))大于零。这样只需存在一个i，使得(max(a)a(i))(a(i)min(a))大于零即可，等价于所有i对应的

(max(a)a(i))(a(i)min(a))之和大于零。这边可作为第一个判断条件。

2.第二个条件有相邻高差为m-1的情况，可先求所以相邻槽的高度差的绝对值，让其最大值等于m-1即。

以s来计数，矩阵A来存储符合条件的槽高组合。 程序如下

function [s,A]=suoju(n,m) A=[];s=0;

for b=0:(m^n-1) ss=0;bb=0;a=[];

for i=1:n

bb=fix((b-ss)/m^(n-i)); a=[a,bb];

ss=ss+bb*m^(n-i); end

for i=1:n

a(i)=a(i)+1; end

amax=max(a); amin=min(a); numbers=0; for i=1:n

number(i)=(amax-a(i))*(a(i)-amin); numbers=numbers+number(i); end

for i=1:(n-1)

ab(i)=abs(a(i)-a(i+1)); end

neighbors=max(ab); if numbers>0.5

if neighbors>m-1.5 s=s+1; A=[A,a']; end end end

我们可以根据以上程序求出n从4到7，m从4到7的所有符合条件的锁的数目 采用一下命令：

for i=1:4 for j=1:4

b(i,j)=suoju(i+3,j+3); end end b

运行结果 b =

64 114 176 250 360 786 1440 2370 1776 4836 10640 20460 8216 28164 74816 168620

结果绘制成下表

表1:n个槽，m个高度时符合条件的锁具的把书 n 4 5 6 7 m 4 64 114 176 250 5 360 786 1440 2370 6 1776 4836 10640 20460 7 8216 28164 74816 168620 另外可采用命令 [s,A]=suoju(4,5)输出n=4,m=5时所有符合条件的槽高组合 由于有114种组合在这里就不列出输出结果。

3.2最大匹配的求法

以n=4，m=5来具体研究，以下列命令求出不同槽高组合的槽高和，以向量B来存储。

[s,A]=suoju(4,5); B=[];

for i=1:114

B=[B,sum(A(:,i))]; end

对B中数据进行统计

tabulate(B)

Value Count Percent 9 10 8.77% 10 16 14.04% 11 22 19.30% 12 18 15.79% 13 22 19.30% 14 16 14.04% 15 10 8.77%

从上面程序结果我们可以看出不同槽高和的值的有着同一种槽高和的锁的个数。同样可以看出槽高和为奇数的点为64个，槽高和为偶数的点为50个。

由于两个不同的槽高组合，要满足4个槽的高度一样，另一个相差为一，才能互开,这与对应槽高差的平方和为1等价。而且槽高和为9的锁，只能和槽高和为10的锁互开；而且槽高和为10的锁，只能和槽高和为9和11的锁互开，以此类推。即一个锁只能和其槽高和数值上相邻的锁互开。

由于所以不同槽高的组合有114种，每种都有4个槽高数，很明显不能用数值表示，为了便于观察采用如下程序，将每一种锁的槽高组合与平面上一个点相对应。这样可以清楚的看出，不同锁具的关系。 程序如下：

[s,A]=suoju(4,5);

a1=[];a2=[];a3=[];a4=[];a5=[];a6=[];a7=[]; for i=1:114 a=0;

for j=1:4

a=a+A(j,i); end

switch a case 9

a1=[a1,A(:,i)]; case 10

a2=[a2,A(:,i)]; case 11

a3=[a3,A(:,i)]; case 12

a4=[a4,A(:,i)]; case 13

a5=[a5,A(:,i)]; case 14

a6=[a6,A(:,i)]; case 15

a7=[a7,A(:,i)]; end end

A=[a1,a2,a3,a4,a5,a6,a7]; B=[];

for i=1:114

B=[B,sum(A(:,i))]; end

[a,b]=hist(B,7);

C=[5:14,4:19,1:22,4:21,1:22,4:19,5:14]; for i=1:114

plot(B(i),C(i),'.b') hold on end

xlabel('锁的所有槽高和') ylabel('不同槽高组合') title('点图')

图一 所有锁在平面上对应的点图

上图中每一个点代表一种锁，横坐标代表槽高和，纵坐标代表不同槽高组合。每一个边代表这条边端点所对应的锁可以互开。从左往右，从下到上数起，第i个点多对应的槽高组合，可用命令A(:,i)来查看。

3.2.1图的存储

图的主要是矩阵的方式来存储，可以用关联矩阵来存储，也可以用邻接矩阵来存储。

关联矩阵反映点和边的关系。而邻接矩阵反映点和点的关系显然这个矩阵过大。关联矩阵存储时不方便运算，当边数很多时，也会大大增加计算机的运算量。

根据本题特点，再求最大匹配问题时采用邻接矩阵来存储，一共有114个顶点，其规模刚好为114114。比关联矩阵规模略小，同样也便于计算和存储。

根据二分图的特点，可以作其邻接矩阵进行。以矩阵D的第i行第j列的元素D(i,j)表示，点i个点和第j个点是否有边,若有边则D(i,j)=1，没边为0。两点之间有边的判断条件为对应槽高差的平方和为一。

for i=1:s; for j=1:i

m=A(:,i)-A(:,j); pan=0; for k=1:4

pan=pan+m(k)^2; end

if pan==1

plot([B(i),B(j)],[C(i),C(j)]); D(i,j)=1; D(j,i)=1;

hold on end end end

xlabel('锁的所有槽高和') ylabel('不同槽高组合') title('二分图')

图二 锁具的二分图

D为该图的邻接矩阵，第i个点和第j个点之间是否有边可用 D(i,j)来查看，D(i,j)=1，表示两点之间有边，D(i,j)=0，这两点之间表示没有边。由上图我们也可以发现每一个点至少有2条边以其为端点，即每个点的度数大于等于2.

3.2.2求最大匹配

有了图的邻接矩阵后，求最大匹配就变成了就变成了邻接矩阵的运算。 求最大匹配可采用，Edmonds算法，也称匈牙利算法，具体步骤如下 1. 任意给出G的一个初始匹配M;

2. 如果M已经饱和了V1中的所有节点,则M是G的一个完全匹配,计算结束．否则转下一步

3. 找出V1中的一个非饱和点x,令A=｛x｝,B= 

4. 考察A的邻接点,如果N(A)=B,则图G不存在完全匹配,计算结束,否则 转下一

步

5. 在V2中找出一点y∈N(A)-B;

6. 如果y是M的饱和点,则在V1中找出y的配对点z,令A=A∪｛z｝,B=B∪{ y},转第4步,否则进行下一步;

7. 存在一条从x到y的可扩路P,由定理知,M不是G的最大匹配,将M与P中 的边进行选择,令 M=M+E(P),则新的M的基数比原来的基数多1,转向第2步．

1.初始匹配的选取：

初始匹配应该取一个基数较大的矩阵，这样的话可以大大减少Edmonds算法中的循环次数，初始匹配选择恰当的话，甚至可以不要进入循环，直接得到最大匹配。 寻找图的一个较大基数的匹配的求法： 1.任意取得图中一边，将其存入匹配M中

2.从该图中将与匹配M中的每一条边相邻的所有边删除； 3.直到所剩的图全为孤立的顶点，算法结束；否则转1. 程序如下:

function J=matgraf(w) n=size(w,1); J=zeros(n,n);

while sum(sum(w))~=0 a=find(w~=0); t1=mod(a(1),n); if t1==0 t1=n; end

if a(1)/n>floor(a(1)/n) t2=floor(a(1)/n)+1; else

t2=floor(a(1)/n); end

J(t1,t2)=1; J(t2,t1)=1;

w(t1,:)=0;w(t2,:)=0; w(:,t1)=0;w(:,t2)=0; end

这样利用以上程序便可以求出邻接矩阵D的一个初始的大基数匹配，程序如下： J=matgraf(D); for i=1:s; for j=1:i

if J(i,j)==1

plot([B(i),B(j)],[C(i),C(j)],'r');

end

end end

xlabel('锁的所有槽高和') ylabel('不同槽高组合') title('最大匹配图')

图三 初始匹配图

2.初始匹配有了之后我们来判断初始匹配J有没有饱和所有偶数点。 以如下程序来看匹配J中顶点的个数 sum(sum(J)) ans =

100

有结果可知匹配J中一共有100个顶点，由二分图特点可知该匹配中一共有50个奇数点和50个偶数点，已经饱和了所有的偶数点。所以该匹配J已经为该图的一最大匹配。可以停止循环。

为了便于观看，做出该最大匹配的图来。

、

图四 最大匹配图

可以用命令

P=[];

for i=1:s; for j=1:i

if J(i,j)==1

p=[A(:,i)',A(:,j)']'; P=[P,p]; end end end P

将所有符合匹配端点所对应的槽高组和输出出来，其中列代表槽高组合，前四个数和后四个数分别为匹配的两个端点对应的槽高数。结果见附录。

四．参考文献

[1] 李明哲，金俊，石端银 图论及其算法 北京：机械工业出版社 2010.10 [2]周义仓，赫孝良 数学建模实验.西安：西安交通大学出版社，1990 [3]徐金明 MATLAB实用教程 北京：清华大学出版社 2005.7

[4]卓金武 MATLAB在数学建模中的应用 北京:航空航天大学出版社 2011.4

五．附录

部分数据：

5.1所有的槽高组合（按槽高和从小到大排序后的)

A =

Columns 1 through 12

1 1 1 1 2 2 5 1 5 2 5 1

Columns 13 through 24

1 1 1 3 5 5 5 1 2 1 3 2

Columns 25 through 36

5 5 1 1 1 1 2 3 5 2 1 4

Columns 37 through 48

2 3 3 5 1 2 1 5 1 3 2 5

Columns 49 through 60

1 1 1 5 5 5 2 3 4 4 3 2

1 1 5 5 1 2 2 1 1 2 5 1 3 5 1 2 1 1 4 4 1 5 5 1 3 3 2 5 5 1 1 2 2 2 1 4 5 1 4 5 2 2 1 1 1 5 5 1 2 2 2 2 1 5 5 1 1 1 5 5 1 2 4 3 4 4 1 1 1 5 5 1 2 2 4 5 5 1 1 4 2 5 5 1 1 1 1 2 2 3 5 1 1 1 2 5 1 1 5 5 3 4 2 1 4 5 5 1 1 1 1 4 3 3 1 3 5 1 3 5 5 1 1 1 2 5 1 3 3 3 1 5 5 1 1 1 2 2 1 3 5 1 3 5 5 5 1 1 2 3 3 2 3 3 3 5 5 1 1 3 1 3 1 5 5 1 1 3 2 3 5 1 5 1 4 1 4 1 5 2 Columns 61 through 72

4 4 4 5 5 5 1 1 1 1 2 2 2 2 5 1 1 1 5 5 5 5 1 5 1 5 1 2 3 4 2 3 4 5 5 1 5 1 2 4 3 2 5 4 3 2 5 5

Columns 73 through 84

2 3 3 3 3 4 4 4 4 5 5 5 5 1 4 4 5 1 3 3 5 1 1 1 5 5 1 5 1 5 1 5 1 2 3 4 1 4 5 1 4 3 5 1 3 5 4 3

Columns 85 through 96

5 5 5 5 1 1 1 3 3 3 4 4 1 2 2 5 5 5 5 1 5 5 1 4 5 1 5 1 3 4 5 5 1 5 5 1 2 5 1 2 5 4 3 5 5 1 4 5

Columns 97 through 108

4 4 5 5 5 5 5 5 1 1 4 4 4 5 1 1 1 3 3 5 5 5 1 5 5 1 3 4 5 1 5 1 4 5 5 1 1 4 5 4 3 5 1 3 5 4 5 5

Columns 109 through 114

4 5 5 5 5 5 5 1 1 4 4 5 5 4 5 1 5 1 1 5 4 5 1 4

5.2.匹配结果：

其中列代表槽高组合，前四个数和后四个数分别为匹配的两个端点对应的槽高数，一共50对槽高组合。

P =

Columns 1 through 12

1 1 1 1 1 2 2 2 5 5 1 2 1 3 3 5 5 1 2 5 1 1 5 3 5 1 5 1 2 5 1 1 1 2 3 5 3 5 1 3 2 2 5 2 3 2 2 1 1 1 1 1 1 2 2 2 5 5 1 2 1 2 2 5 5 1 1 5 1 1 5 2 5 1 5 1 2 5 1 1 1 2 3 5 2 5 1

Columns 13 through 24

3 3 3 1 2 5 5 1 1 2 5 2 3 3 3 1 1 5 5 1 1 1 5 1

Columns 25 through 36

3 3 4 3 3 1 1 5 5 5 1 2 2 3 4 3 2 1 1 5 5 5 1 1

Columns 37 through 48

1 3 3 5 1 5 5 5 1 3 5 5 1 2 2 5 1 5 4 5 1 3 5 5

2 1 5 1 1 5 3 2 2 4 5 1 1 5 3 1 1 4 4 4 2 5 1 1 5 2 4 4 1 5 1 1 5 1 3 4 5 1 5 5 1 4 2 3 5 1 5 5 1 4 1 5 1 1 5 5 3 4 3 2 1 1 5 5 2 4 3 1 5 5 1 1 2 3 4 3 5 5 1 1 1 2 4 3 4 4 4 4 1 5 5 1 3 3 4 4 1 5 5 1 1 2 2 2 1 4 5 1 4 5 1 1 1 4 5 1 4 5 5 3 1 5 4 1 2 4 5 3 1 5 4 1 1 3 4 5 5 1 1 3 4 5 4 5 5 1 1 2 3 5 1 1 2 2 4 5 5 1 1 4 1 2 4 5 5 1 1 3 4 1 3 5 5 3 1 5 4 1 2 5 5 2 1 5 5 5 1 1 4 5 4 3 5 4 1 1 3 5 4 3 1 3 1 5 3 2 1 5 3 1 5 4 4 1 5 3 4 5 3 1 5 4 3 1 5 Columns 49 through 50

5 5 3 5 5 1 1 3 5 5 2 5 5 1 1 2