PDF《第十六章习题》

41 第十六章习题 1.

某城市要建立一个消防站,为该市所属的七个区服务,如图 16-13 所示,问应 设在哪个区,才能使它至最远区的路径最短.

1 v

2 v

3 v

4 v

5 v

6 v

7 v

3 2

6 2.5 1.5 1.8

4 3

2 图16-13

1 v

2 v

3 v

4 v

5 v

6 v

7 v

3 2

6 2.5 1.5 1.8

4 3

2 1 v

2 v

3 v

4 v

5 v

6 v

7 v

3 2

6 2.5 1.5 1.8

4 3

2 图16-13 解:本题首先需要求出任意两点间的最短路,然后判断选择在哪个区建立消 防站解: (1)求任意两点间的最短路,matlab 程序如下 clear;

clc;

M=10000;

a(1,:)=[0,3,M,M,M,M,M];

a(2,:)=[zeros(1,2),2,M,1.8,2.5,M,];

a(3,:)=[zeros(1,3),6,2,M,M];

a(4,:)=[zeros(1,4),3,M,M];

a(5,:)=[zeros(1,5),4,M];

a(6,:)=[zeros(1,6),1.5];

a(7,:)=zeros(1,7);

b=a+a';

path=zeros(length(b));

for k=1:7 for i=1:7 for j=1:7 if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j);

path(i,j)=k;

end end end end b, path 得任意两点间距离矩阵(列表) :

42 To from

1 v

2 v

3 v

4 v

5 v

6 v

7 v 最大值

1 v

0 3

5 7.8 4.8 5.5

7 7.8

2 v

3 0

2 4.8 1.8 2.5

4 4.8

3 v

5 2

0 5

2 4.5

6 6

4 v 7.8 4.8

5 0

3 7 8.5 8.5

5 v 4.8 1.8

2 3

0 4 5.5 5.5

6 v 5.5 2.5 4.5

7 4

0 1.5

7 7 v

7 4

6 8.5 5.5 1.5

0 8.5 (2) 计算在点 i v 设立服务设施时的最大服务距离,即iv到各点距离的最大值 (见表中最后一列) ;

(3) 第二个区距离最远的区路径最短,为4.8,所以应该选择第二个区建立 消防站. 2.对图 16-14,求最小生成树. 图16-14 图16-14 解:最小生成树 matlab 程序如下 clc;

clear;

a(1,:)=[0,56,35,2,51,60];

a(2,:)=[zeros(1,2),21,57,78,70];

a(3,:)=[zeros(1,3),36,68,68];

a(4,:)=[zeros(1,4),51,61];

a(5,:)=[zeros(1,5),13];

a(6,:)=zeros(1,6);

a=a+a';

result=[];

p=1;

tb=2:length(a);

while length(result)~=length(a)-1 temp=a(p,tb);

temp=temp(:);

d=min(temp);

[jb,kb]=find(a(p,tb)==d);

j=p(jb(1));

k=tb(kb(1));

43 result=[result,[j;

k;

d]];

p=[p,k];

tb(find(tb==k))=[];

end result 最小生成树见最小生成树图. (说明:本题最小生成树不唯一)

1 v

2 v

3 v

4 v

5 v

6 v 最小生成树

1 v

2 v

3 v

4 v

5 v

6 v

1 v

2 v

3 v

4 v

5 v

6 v 最小生成树 3. 从北京(Pe)乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎 (Pa)五城市做旅游,每个城市仅去一次再回北京,应如何安排旅游线,使旅程最 短?各城市之间的航线距离如表 16-1. 表16-1 六个首都之间的航线距离 L M N Pa Pe T L

0 56

35 21

51 60 M

56 0

21 57

78 70 N

35 21

0 36

68 68 Pa

21 57

36 0

51 61 Pe

51 78

68 51

0 13 T

60 70

68 61

13 0 分析:本题为 H 圈问题 解:最短旅游线为北京->巴黎->伦敦->纽约->墨西哥城->东京->北京,最短距 离为

211 matlab 程序如下: M 文件 function [circle, long]=modifycircle(c1,L);

global a 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))