实训总结范文-端午节的来历

作业解答
练习题2 利用matlab编程FFD算法完成下题：
设有6 种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子
的容积为100个单 位体积。

解答一：
function [num,s] = BinPackingFFD(w,capacity)
%一维装箱问题的FFD（降序首次适应）算法求解:先将物体按长度从大到小排序,
%然后按FF算法对物体装箱
%输入参数w为物品体积，capacity为箱子容量
%输出参数num为所用箱子个数，s为元胞数组，表示装箱方案，s{i}为第i个箱子所装
%物品体积数组
%例w = [60,45,35,20,20,20]; capacity = 100;
% num=3,s={[1,3],[2,4,5],6};

w = sort(w,'descend');
n = length(w);
s = cell(1,n);
bin = capacity * ones(1,n);
num = 1;
for i = 1:n
for j = 1:num + 1
if w(i) < bin(j)
bin(j) = bin(j) - w(i);
s{j} = [s{j},i];
if j == num + 1
num = num + 1;
end
break;
end
end
end
s = s(1:num);

解答二：
clear;

clc;

V=100;

v=[60 45 35 20 20 20];

n=length(v);

v=fliplr(sort(v));

box_count=1;

x=zeros(n,n);

V_Left=100;

for i=1:n

if v(i)>=max(V_Left)

box_count=box_count+1;

x(i,box_count)=1;

V_Left=[V_Left V-v(i)];

else

j=1;

while(v(i)>V_Left(j))

j=j+1;

end

x(i,j)=1;

V_Left(j)=V_Left(j)-v(i);

end

temp=find(x(i,:)==1);

fprintf('第%d个物品放在第%d个容器n',i,temp)

end


output:
第1个物品放在第1个容器
第2个物品放在第2个容器
第3个物品放在第1个容器
第4个物品放在第2个容器
第5个物品放在第2个容器
第6个物品放在第3个容器

解答三：
function box_count=FFD(x)
%降序首次适应算法
v=100;
x=fliplr(sort(x));
%v=input('请输入箱子的容积:');
n=length(x);
I=ones(n);
E=zeros(1,n);
box=v*I;
box_count=0;
for i=1:n
j=1;
while(j<=box_count)
if x(i)>box(j)
j=j+1;
continue;
else

box(j)=box(j)-x(i);
E(i)=j;
break;
end
end
if j>box_count
box_count=box_count+1;
box(box_count)=box(box_count)-x(i);
E(i)=j;
end
end
disp(E);

在命令窗口输入：
>> x=[60,45,35,20,20,20];
>> FFD(x)


1 2 1 2 2 3
ans =
3
练习题5 “超市大赢家”提供了5 0种商品作为奖品供中奖顾客选择,车的容量为
1000dm
3
, 奖品i占用的空间为w
i
dm
3
,价值为v
i
元, 具体的数据如下:
v
i
= { 220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118,
115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65,
63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1}
w
i
= {80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38,
35, 32, 25, 28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10,
10, 4, 4, 2,1}。
问如何装车才能总价值最大。
解答：
clear;
clc;
v=[220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118, 115, 110, 105,
101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15,
10, 8, 5, 3, 1];
w=[80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25,
28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1];
totalw=1000;limitw=1000;
n=length(w);

for i=1:n
f(1,i)=v(i)w(i);
f(2,i)=w(i);

f(3,i)=i;
end

for i=1:(n-1)
for j=(i+1):n
if f(1,i) t=f(1,i);
f(1,i)=f(1,j);
f(1,j)=t;
t=f(2,i);
f(2,i)=f(2,j);
f(2,j)=t;
t=f(3,i);
f(3,i)=f(3,j);
f(3,j)=t;
end
end
end

totalv=0;a=[];
for i=1:n
if f(2,i)<=limitw
a=[a,f(3,i)]; %disp(f(3,i));
limitw=limitw-f(2,i);
totalv=totalv+f(1,i)*f(2,i);
end
end
a
totalv
totalw=totalw- limitw
结果
a =
Columns 1 through 21
10 40 17 25 28 16 19 35 37
13 11 24 27 9 23 41 1 4
Columns 22 through 27
22 6 30 14 2 47
totalv =
3103
totalw =
1000


练习题8 对最后一个求有向圈的示例用matlab程序实现。
8 26 20

解答：
H= [0 1 0 0 0;
0 0 0 1 1;
1 1 1 0 0;
0 0 1 0 1;
0 1 0 0 0];
n=size(H,1);%顶点个数
p=zeros(1,n);%存储搜索过的顶点
X=zeros(n,n);%用来设置禁止矩阵，往回返的时候设置此路已被搜索
k=1;
p(1)=1;%第一个点作为初始点开始搜索
while p(1)<=n %每个顶点都作为初始点搜索包含p(1)的有向圈，
i=p(1)+1;%当前点k往后搜索时都是从p(1)+1开始，从而也可以搜索下标小于k的点
while i<=n %还有后续点没有搜索（这些点有可能比当前点k小）
if (H(p(k),i)==1)&(X(p(k),i)==0)&isempty(find(p==i))% 满足三个条件
k=k+1;%搜索路径上增加一个点
p(k)=i;%搜索路径向前延伸一个点
else
i=i+1;%当前被搜索点不满足条件，换下一个点
end
end
if i>n %k点往后的所有点都被搜索
if H(p(k),p(1))==1%有圈，每次搜索的都是包含初始点的圈
disp(p(1:k));%输出圈
end
%不管有没有圈，此时k点要往回返
if k>1%路径上不止出发点
for j=1:n
X(p(k),j)=0;%取消以前的限制通行
end
X(p(k-1),p(k))=1;%增加此路已搜索
p(k)=0;%撤销路径上的k点
k=k-1;%返回上一个点作为当前点
else %返回到出发点了

p(1)=p(1)+1; %换下一个出发点（初始点）
end
end
end
运行结果：
1 2 4 3

2 4 5

2 4 3

2 5

3
练习题9 选址问题 现准备在7个居民点中设置一银行，路线与距离如下 图，问设在哪个
点，可使最大服务距离最小若设两个点呢
v
1
3
v
2
1.5
2
2.5
v
3
4
6
3< br>v
4
v
5
1.5
v
6
1.8
v7


解答：
第一步：
function [D,R]=floyd(A)
%用floyd算法实现求任意两点之间的最短路程。可以有负权
%参数D为连通图的权矩阵
A=[0 3 inf inf inf inf inf
3 0 2 inf inf inf
inf 2 0 6 inf 4
inf inf 6 0 inf inf 3
inf inf inf inf 0 inf
inf inf 0
inf inf 4 3 inf 0
];
D=A;n=length(D);
for i=1:n
for j=1:n
R(i,j)=i;%赋路径初值
end
end
for k=1:n
for i=1:n

for j=1:n
if D(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j);%更新 D(i,j)，说明通过k的路程更短
R(i,j)=R(k,j);%更新R(i,j)，需要通过k
end
end
end
hl=0;
for i=1:n
if D(i,i)<0
hl=1;
break;%跳出内层的for循环
end
end
if(hl==1)
fprintf('有负回路')
break;%跳出最外层循环
end
end
D

运行结果：

D=

0
0
0
0
0
0
0
第二步：对于第一问
在矩阵D中每一个取大得到一列数，再在这列数中取小，
[m,n]=size(D);

p=[];

for i=1:m

p(i)=max(D(i,:));

end

for i=1:m

if p(i)==min(p)

disp(i);

end

end

min(p)

在顶点6建立银行，最大服务距离最小，最小是.
第三步：对于第二问
任取两个点 做集合，计算每个点到这个集合的最小值，再在这个最小值中取大，即在矩阵D
中任取两行，对应比较取 小得一向量，将所有这样的向量写成行向量构成一矩阵，然后用
问题一的算法程序即可。
a=0;

b=[];

n=size(D,1);

for i=1:(n-1)

for j=(i+1):n

a=a+1;

for k=1:n

s{a}=[i j];

b(a,k)=min(D(i,k),D(j,k));

end

end

end

m=size(b,1);

p=[];

for i=1:m

p(i)=max(b(i,:));

end

for i=1:m

if p(i)==min(p)

disp(s{i});

end

end

min(p)

结果，在顶点2,4或2,7点建立银行都使得最大服务距离最小，最小值是3

练习题10 货物调运 已知该地区有生产该物资的企业三家，大小物资仓库八
个 ，国家级储备库两个，其分布情况见下面的附件1。经核算该物资的运输成本
为高等级公路2元公里百件 ，普通公路元公里百件，假设各企业、物资仓库及
国家级储备库之间的物资可以通过公路运输互相调运， 请给出各个仓库应该从哪
个企业调运。

解答：
首先建立各个交汇点的距离矩阵m。然后建立函数文件。
%各仓库到各企业的最小运费
function min_spend(m)
c=[28,23,35,31,22,36,29,38]; %仓库
cc=[27,30]; %国家储存库
C=[c,cc];
g=[8,15,1 1,27,7,10,17,14,28,16,18,25,6,5,39,35,13,40,4,29]; %高级公路上的点
n=length(g);
A=zeros(42);
for i=1:42
for j=1:42
if m(i,j)~=0
A(i,j)=*m(i,j); %普通公路上每百件的运费
else
A(i,j)=inf;
end
end
end
for i=1:n
for j=1:n
A(g(i),g(j))=2*A(g(i),g(j)); %高级公路上每百件的运费
end

end
for i=1:42
A(i,i)=0;
end
[D,R]=floyd(A);
for i=1:10
for j=1:3
X(i,j)=D(C(i),q(j));
end
end
[XX,INDEX]=min(X')
在命令窗口输入：
>> min_spend(m)
XX =


INDEX =
2 1 3 3 1 3 2 3 1 3
XX为从各个仓库到三个企业中的最小费用，INDEX为最小费用的企业。

练习题14 最小代价流 将上题容量网络的边上增加另一个权数----代价，变为
具有 代价的容量网络，单位代价为容量数的十位上的数字，求比最大流少30单
位的最小代价流。
v
2
25
71
v
3
38
34
v
1
61
56
49
2436
v
5
72
v
6
53
v
8
74
45
57
74
38v
4
v
7
67
v
9

由上题结果可知 ，最大流为142，则最小代价流的流量应该为112。用迭代算法，预定
流量值wf0=112。
方法一：
C=[0 25 0 56 61 0 0 0 0;
0 0 71 0 0 36 0 0 0;
0 0 0 0 0 0 0 34 0;
0 0 0 0 49 0 74 0 0;
0 24 0 0 0 72 57 0 0;
0 0 38 0 0 0 0 53 45;
0 0 0 0 0 38 0 0 67;
0 0 0 0 0 0 0 0 74;

0 0 0 0 0 0 0 0 0];%弧容量
b=[0 2 0 5 6 0 0 0 0;
0 0 7 0 0 3 0 0 0;
0 0 0 0 0 0 0 3 0;
0 0 0 0 4 0 7 0 0;
0 2 0 0 0 7 5 0 0;
0 0 3 0 0 0 0 5 4;
0 0 0 0 0 3 0 0 6;
0 0 0 0 0 0 0 0 7;
0 0 0 0 0 0 0 0 0]; %弧上单位流量的费用
n=9;
wf=0;wf0=112; %wf表示最大流量, wf0表示预定的流量值
for(i=1:n) for(j=1:n) f(i,j)=0;end;end %取初始可行流f为零流
while(1)









for(i= 1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋 权图
for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a (i,j)=b(i,j);
elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);
elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j); end;end;end
for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford算法求最短路, 赋初值
for(k=1:n)pd=1; %求有向赋权图中vs到vt的最短路
for(i=2:n)for(j=1:n)if(p(i) >p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end; end
if(pd)break;end;end %求最短路的Ford算法结束
if(p(n)==Inf)break;end %不存在vs到vt的最短路, 算法终止. 注意在求最小费用最大流
时构造有向赋权图中不会含负权回路, 所以不会出现k=n
dvt=Inf;t=n; %进入调整过程, dvt表示调整量
while(1) %计算调整量
if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量
elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量
if(dvt>dvtt)dvt=dvtt;end
if(s(t)==1)break;end %当t的标号为vs时, 终止计算调整量
t=s(t);end %继续调整前一段弧上的流f
pd=0;if(wf+dvt>wf0) dvt=wf0-wf;pd=1;end %如果最大流量大于或等于预定的流量值
t=n;while(1) %调整过程
if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整
elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整
if(s(t)==1)break;end %当t的标号为vs时, 终止调整过程
t=s(t);end
if(pd)break;end %如果最大流量达到预定的流量值
wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量
zwf=0;f or(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end %计算最小费用
f %显示最小费用最大流
wf %显示最小费用最大流量
zwf %显示最小费用

运行结果：
>>
f =

0 25 0 26 61 0 0 0 0
0 0 0 0 0 36 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 26 0 0
0 11 0 0 0 9 41 0 0
0 0 0 0 0 0 0 0 45
0 0 0 0 0 0 0 0 67
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

wf =
112

zwf =

1708
由程序运行结果可得：比最大流少30单位的最小代价流为f，最小代价为1708。
方法二
在已知流量上限情况下的Lingo最小费用求解
sets:
nodes1..9:;
arcs(nodes, nodes): c,b,f; !f为流，c为网络容量，b为费用;
endsets
data:
fmax = 112; !流量上界;
c=0 25 0 56 61 0 0 0 0
0 0 71 0 0 36 0 0 0
0 0 0 0 0 0 0 34 0
0 0 0 0 49 0 74 0 0
0 24 0 0 0 72 57 0 0
0 0 38 0 0 0 0 53 45
0 0 0 0 0 38 0 0 67
0 0 0 0 0 0 0 0 74
0 0 0 0 0 0 0 0 0;
b= 0 2 0 5 6 0 0 0 0
0 0 7 0 0 3 0 0 0
0 0 0 0 0 0 0 3 0
0 0 0 0 4 0 7 0 0
0 2 0 0 0 7 5 0 0
0 0 3 0 0 0 0 5 4

0 0 0 0 0 3 0 0 6
0 0 0 0 0 0 0 0 7
0 0 0 0 0 0 0 0 0;
enddata
min=@sum(arcs:b*f);
@for(nodes(i) | i #ne# 1 #and# i #ne# @size(nodes):
@sum(arcs(i,j):f(i,j)) - @sum(arcs(j,i):f(j,i))=0);
@sum(arcs(i,j)|i #eq# 1 : f(i,j))=fmax;
@for(arcs:@bnd(0,f,c));

练习题20 现在有8个城市，已知两个城市之间的路费如下表，现在有一个人
从 A城市出发旅行，应该选择怎样的路线才能刚好每个城市都到达一次又回到A
城市，其总路费最少
A B C D E F G H

A 56 35 21 51 60 43
B 39
C 21 57 78 70 64
D 49
E 36 68 --- 70
F 60
G 51 61 65
26
13 45
62
53
26
5
0
解答：
方法一
建立规划模型：
先将一般加权连通图转化成一个等价的加权完全图，设当从
v
i
到
v
j
时，
x
ij
1，否则，
x
ij
0
，则得如下模型：
min

wx
i1j1
nn
ijij


n


x
ij
1,(i1,, n)

j1
n


x1,(j1,,n)
s.t.


ij

i1

x
i
1
i
2
x
i
2
i
3
x
i
k
i
1
k1,(i
1
,,i
k
1 ,,n;k2,,n1)



x
ij
0或1, i,j1,,n;ij

利用lingo求解：
model:!TSP问题;
sets:
citiesA,B,C,D,E,F,G,H:level;
link(cities, cities)|&1#ne#&2: w, x;!W距离矩阵;
endsets
data:
w= 56 35 21 51 60 43 39
56 21 57 78 70 64 49
35 21 36 68 1000 70 60
21 57 36 51 61 65 26
51 78 68 51 13 45 61
60 70 1000 61 13 53 26
43 64 70 65 45 53 50
39 49 60 26 61 26 50;
enddata
n=@size(cities);
min=@sum(link(i,j)|i #ne# j: w(i,j)*x(i,j));
@for(cities(i) :
@sum(cities(j)| j #ne# i: x(j,i))=1;
@sum(cities(j)| j #ne# i: x(i,j))=1;
@for(cities(j)| j #gt# 1 #and# j #ne# i :
level(j) >= level(i) + x(i,j)
- (n-2)*(1-x(i,j)) + (n-3)*x(j,i);
);
);
@for(link : @bin(x));
@for(cities(i) | i #gt# 1 :
level(i)<=n-1-(n-2)*x(1,i);
level(i)>=1+(n-2)*x(i,1);
);
end

由程序运行结果可得，从A城市出发旅行，刚好每个城市都到达一次又回到A城市，且总

路费最少的路线为：
ADHFEGBCA
。最少费用为251。
方法二（参考）
求一个Hamilton圈
cv
1
v
i
v
i1
v
j
v
j1
v
n
v
1
，
构造新圈：由
c
中删掉边
v
i
v
i1
和
v
j
v
j1
，添加边
vi
v
j
和
v
i1
v
j1
而得到，
判断：若

v
i
v
j
+

vi1
v
j1
<


v
i
v
i1

+

v
j
v
j1
，则以新圈 代替旧圈，称为改良圈。

clear
a(1,2)=56;a(1, 3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(1,7)=43;a(1, 8)=39;
a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70 ;a(2,7)=64;a(2,8)=49;
a(3,4)=36;a(3,5)=68;a(3, 6)=Inf;a(3,7)=70;a(3,8)=60;
a(4,5)=51;a(4,6)=61;a(4,7)=65;a(4,8)=26;
a(5,6)=13;a(5,7)=45;a(5,8)=62;
a(6,7)=53;a(6,8)=26;
a(7,8)=50;
a(8,:)=0;
a=a+a'
c1= [1 3 2 5:8 4];
L=length(c1);
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if a(c1(m),c1(n))+a(c1(m+1), c1(n+1)) flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
sum1=0;
for i=1:L-1
sum1=sum1+a(c1(i),c1(i+1));
end
sum1=sum1+a(c1(8),c1(1))
circle=c1;
sum=sum1;
c1=[1 4 3 2 5:8 ];%改变初始圈，该算法的最后一个顶点不动
flag=1;
while flag>0
flag=0;
for m=1:L-3

for n=m+2:L-1
if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...
a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
sum1=0;
for i=1:L-1
sum1=sum1+a(c1(i),c1(i+1));
end
sum1=sum1+a(c1(8),c1(1))
if sum1 sum=sum1;
circle=c1;
end
circle,sum


练习题21 某街道布局如下，在0点处停放有 一辆洒水车，每天洒水车都要给
每条街道洒水，请给洒水车优化一条路线。
6
3

解答（参考）：以下版本方法正确，应可以简化。

该题为中国邮递员问题，故先使用floyd算法求出奇点间的最短距离，并建立以奇点为顶点
的完全图 ，调用文件
clear;
c=[inf 5 inf 6 inf inf inf inf inf inf
5 inf 5 inf 6 inf inf inf inf inf
inf 5 inf inf inf 2 inf inf inf inf
6 inf inf inf 3 inf 4 inf inf inf
inf 6 inf 3 inf 6 inf 4 inf inf
inf inf 2 inf 6 inf inf inf 4 inf
inf inf inf 4 inf inf inf 4 inf 2
inf inf inf inf 4 inf 4 inf 3 inf
inf inf inf inf inf 4 inf 3 inf inf
inf inf inf inf inf inf 2 inf inf inf];

m=length(c);
Path=zeros(m);
for k=1:m
for i=1:m
for j=1:m
if c(i,j)>c(i,k)+c(k,j)
c(i,j)=c(i,k)+c(k,j);
Path(i,j)=k;
end
end
end
end
h1=c(2,4);
h2=c(2,6);
h3=c(2,7);
h4=c(2,8);
h5=c(2,10);
h6=c(4,6);
h7=c(4,7);
h8=c(4,8);
h9=c(4,10);
h10=c(6,7);
h11=c(6,8);
h12=c(6,10);
h13=c(7,8);
h14=c(7,10);
h15=c(8,10);
disp(c(2,6));
disp(c(4,8));
disp(c(7,10));
a=zeros(6); a(1,2)=h1;a(1,3)=h2;
a(1,4)=h3;a(1,5)=h4;a(1,6)=h5; a(2,3)=h6;a(2,4)=h7 ;a(2,5)=h8;a(2,6)=h9;a(3,4)=h10;
a(3,5)=h11;a (3,6)=h12;a(4,5)=h13;a(4,6)=h14;a(5,6)=h15;
a=a+a'; a(find(a==0))=inf;
Hung_Al(a);
%原矩阵的2，4，6，7，8，10分别对应于奇点矩阵的1，2，3，4，5，6顶点
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
接着调用文件找出以奇点为顶点的完全图的最优匹配
function [Matching,Cost] = Hung_Al(Matrix)
Matrix=a;
Matching = zeros(size(Matrix));
% 找出每行和每列相邻的点数
num_y = sum(~isinf(Matrix),1); num_x = sum(~isinf(Matrix),2);
% 找出每行和每列的孤立点数

x_con = find(num_x~=0); y_con = find(num_y~=0); %将矩阵压缩、重组
P_size = max(length(x_con),length(y_con));
P_cond = zeros(P_size);
P_cond(1:length(x_con),1:length(y_con)) = Matrix(x_con,y_con);
if isempty(P_cond)
Cost = 0;
return;
end
% 确保存在完美匹配，计算矩阵边集
Edge = P_cond;
Edge(P_cond~=Inf) = 0;
cnum=min_line_cover(Edge);
Pmax = max(max(P_cond(P_cond~=Inf)));
P_size = length(P_cond)+cnum;
P_cond = ones(P_size)*Pmax;
P_cond(1:length(x_con),1:length(y_con)) = Matrix(x_con,y_con);

%主函数程序,此处将每个步骤用 switch 命令进行控制调用步骤函数
exit_flag = 1;
stepnum = 1;
while exit_flag
switch stepnum
case 1
[P_cond,stepnum] = step1(P_cond);
case 2
[r_cov,c_cov,M,stepnum] = step2(P_cond);
case 3
[c_cov,stepnum] = step3(M,P_size);
case 4
[M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(P_cond,r_cov,c_cov,M);
case 5
[M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov);
case 6
[P_cond,stepnum] = step6(P_cond,r_cov,c_cov);
case 7
exit_flag = 0;
end
end
Matching(x_con,y_con) = M(1:length(x_con),1:length(y_con));
Cost = sum(sum(Matrix(Matching==1)));
Matching
Cost
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%下面是 6 个步骤函数 step1~step6

%步骤 1：找到包含 0 最多的行，从该行减去最小值
function [P_cond,stepnum]=step1(P_cond)
P_size = length(P_cond);
for ii = 1:P_size
rmin = min(P_cond(ii,:));
P_cond(ii,:) = P_cond(ii,:)-rmin;
end
stepnum = 2;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%步骤 2：在 P-cond 中找一个 0，并找出一个以该数 0 为星型的覆盖
function [r_cov,c_cov,M,stepnum] = step2(P_cond)
%定义变量 r-cov，c-cov 分别表示行或列是否被覆盖
P_size = length(P_cond);
r_cov = zeros(P_size,1);
c_cov = zeros(P_size,1);
M = zeros(P_size);
for ii = 1:P_size
for jj = 1:P_size
if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0
M(ii,jj) = 1; r_cov(ii) = 1; c_cov(jj) = 1;
end
end
end
% 重初始化变量
r_cov = zeros(P_size,1);
c_cov = zeros(P_size,1);
stepnum = 3;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%步骤 3：每列都用一个 0 构成的星型覆盖，如果每列都存在这样的覆盖，则 M 为最大
匹配
function [c_cov,stepnum] = step3(M,P_size)
c_cov = sum(M,1);
if sum(c_cov) == P_size
stepnum = 7;
else stepnum = 4;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%步骤 4：找一个未被覆盖的 0 且从这出发点搜寻星型 0 覆盖。如果不存在，转步骤 5，
否% 则转步骤 6
function [M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(P_cond,r_cov,c_cov,M)
P_size = length(P_cond);
zflag = 1;
while zflag
row = 0;

col = 0;
exit_flag = 1; ii = 1; jj = 1;
while exit_flag
if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0
row = ii;
col = jj;
exit_flag = 0;
end
jj = jj + 1;
if jj > P_size; jj = 1; ii = ii+1; end
if ii > P_size; exit_flag = 0; end
end
if row == 0
stepnum = 6;
zflag = 0;
Z_r = 0;
Z_c = 0;
else
M(row,col) = 2;
if sum(find(M(row,:)==1)) ~= 0
r_cov(row) = 1; zcol = find(M(row,:)==1); c_cov(zcol) = 0;
else stepnum = 5; zflag = 0; Z_r = row; Z_c = col;
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%步骤 5：
function [M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov)
zflag = 1; ii = 1;
while zflag
rindex = find(M(:,Z_c(ii))==1);
if rindex > 0
ii = ii+1;
Z_r(ii,1) = rindex;
Z_c(ii,1) = Z_c(ii-1);
else zflag = 0;
end
if zflag == 1;
cindex = find(M(Z_r(ii),:)==2); ii = ii+1; Z_r(ii,1) = Z_r(ii-1); Z_c(ii,1) = cindex;
end
end
for ii = 1:length(Z_r)
if M(Z_r(ii),Z_c(ii)) == 1
M(Z_r(ii),Z_c(ii)) = 0;

else M(Z_r(ii),Z_c(ii)) = 1;
end
end
r_cov = r_cov.*0; c_cov = c_cov.*0; M(M==2) = 0; stepnum = 3;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 步骤 6：
function [P_cond,stepnum] = step6(P_cond,r_cov,c_cov)
a = find(r_cov == 0);
b = find(c_cov == 0);
minval = min(min(P_cond(a,b)));
P_cond(find(r_cov == 1),:) = P_cond(find(r_cov == 1),:) + minval; P_cond(:,find(c_cov == 0)) =
P_cond(:,find(c_cov == 0)) - minval;
stepnum = 4;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function cnum=min_line_cover(Edge)
[r_cov,c_cov,M,stepnum]=step2(Edge);
[c_cov,stepnum] = step3(M,length(Edge));
[M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(Edge,r_cov,c_cov,M);
cnum = length(Edge)-sum(r_cov)-sum(c_cov);








Hung_Al运行的结果如下：

即对于所有奇点构成的矩阵的1和3，2和5，4和6之间增加边。

%原矩阵的2，4，6，7，8，10分别对应于奇点矩阵的1，2，3，4，5，6顶点
相对原矩 阵即2和6，4和8，7和10增加边，（相当于2—3—6，4—5—8，7—10不变）
边长为原来 求得的最短距离即7,7,2.
得到新的矩阵如下：
inf 5 inf 6 inf inf inf inf inf inf
5 inf 5 inf 6 7 inf inf inf inf
inf 5 inf inf inf 2 inf inf inf inf
6 inf inf inf 3 inf 4 7 inf inf
inf 6 inf 3 inf 6 inf 4 inf inf
inf 7 2 inf 6 inf inf inf 4 inf
inf inf inf 4 inf inf inf 4 inf 2
inf inf inf 7 4 inf 4 inf 3 inf
inf inf inf inf inf 4 inf 3 inf inf
inf inf inf inf inf inf 2 inf inf inf
用 Fleury 方法求出其欧拉回路即为所求的最佳邮差回路，文件如下：
clear;
w=[inf 5 inf 6 inf inf inf inf inf inf
5 inf 5 inf 6 7 inf inf inf inf
inf 5 inf inf inf 2 inf inf inf inf
6 inf inf inf 3 inf 4 7 inf inf
inf 6 inf 3 inf 6 inf 4 inf inf
inf 7 2 inf 6 inf inf inf 4 inf
inf inf inf 4 inf inf inf 4 inf 2
inf inf inf 7 4 inf 4 inf 3 inf
inf inf inf inf inf 4 inf 3 inf inf
inf inf inf inf inf inf 2 inf inf inf];
begin=10;
total=0; %用来记录迭代次数
for i =1 :size(w,1)
for j=1:size(w,1)
if w(i,j)~=inf & w(i,j)~=0
total=total+1;
end
end
end
for i = 1:size(w,1)
remain(i)=i;
end
remain(find(remain==begin))=[]; %创建remain它将包含所有已经做出判断的点
时使用
temp=w %创建temp它在判断是否是桥的时候使用
d=w; %d用来记录整个过程中图的变化
parrent(1)=begin; %用来记录父亲点
current=begin; %用来记录当前点
终止条件

rc=[]; %用来记录与current相关的点
newpa=2;
for m=1:total2 %此循环由终止条件判断成立后跳出
for ii = 1:size(w,1)
newre=1; %newre用来记录与current有关的点的数量
if (d(current,ii)~=inf & d(current,ii)~=0)|(d(ii,current)~=inf & d(ii,current)~=0)

rc(newre)=ii;
newre=newre+1;
break;
end
end
if newre==2 %只有一个点 没得选了
next=rc(1);
else
for k=1:size(rc,2)

temp=d; temp(rc(k),current)=inf; temp(current,rc(k))=inf;
if tell(rc(k),current,temp)~=0 break; %如果不是桥退出
elseif k==size(rc,2) break; %最后一个点不管是不是都推出
else
end
end
next=rc(k);

end
parrent(newpa)=next; newpa=newpa+1; %父亲点里加上这个点
d(current,next)=inf; d(next,current)=inf; %表示这条边已经选掉了
remain(find(remain==next))=[]; %剩余点里除掉这个点
current=next; %当前点变成next
end
end
parrent
s=0;

for i=1:(length(parrent)-1)
s=s+w(parrent(i),parrent(i+1));
end
s=s+w(parrent(length(parrent)),parrent(1));
s
%%%%%%%%%%%%%%%%该文件用到文件如下%%%%%%%%%%
function [res ] = tell(next,current,temp )
%TELL Summary of this function goes here
% 判断next current在temp下是不是桥 是对话返回1

flag1=0;flag2=0;
for i = 1:size(temp,1)
if temp(next,i)~=0&temp(i,next)~=inf %说明有点和next相连
flag1=1;
end
if temp(current,i)~=0&temp(i,current)~=inf
flag2=1;
end
end
if flag1==1&flag2==1 res=0;
else res=1;
end
end
end
运行得到的结果如下:
其中6—2原来没有直接的路，应 为6—3—2，4—8原来也没有直接的路，应为4—5
—8；
最后路径为10—7——4— —1——2——3——6——3——2——5——4——5——8——
5——6——9——8——7—— 10。
即走完所有街道最短路径为70。