数学建模实验四

数学实验与数学建模实验报告。

信息学院通信工程

第十三章树与最小生成树。

实验一最小生成树问题。

试用prim算法和kruskal算法求下图所示网络中的最优树。

matlab程序如下：

1）kruskal算法。

b=[11122334;

b,i]=sortrows(b',3);

b=b';m=size(b,2);n=5;

t=1:n;k=0;t=c=0;

fori=1:m

ift(b(1,i))~t(b(2,i));

k=k+1;t(k,1:2)=b(1:2,i),c=c+b(3,i)

tmin=min(t(b(1,i)),t(b(2,i)))

tmax=max(t(b(1,i)),t(b(2,i)))

forj=1:n

ift(j)==tmax

t(j)=tmin;

endend

endifk==n-1

breakend

endt,c

运行结果。t =

c =2）prim算法。

prim'salgorithm

clear;

a=[0173inf;

106inf2;

3inf904;

inf2540];

t=c=0;v=1;n=5;sb=2:n;

forj=2:n

b(1,j-1)=1;

b(2,j-1)=j;

b(3,j-1)=a(1,j);

endwhilesize(t,2)[tmin,i]=min(b(3,:)

t(:,size(t,2)+1)=b(:,i)

c=c+b(3,i);

v=b(2,i);

temp=find(sb==b(2,i));

sb(temp)=[b(:,i)=[

forj=1:length(sb)

d=a(v,b(2,j));

ifdb(1,j)=v;b(3,j)=d;

endend

endt,c

运行结果。t =

c =因此，图中的最小生成树的边集合为，费用为11

第十四章最短路径及算法。

实验一求最短路问题。

求图14.9所示有向网络中自点1到点6的最短有向路。

matlab程序如下：

floyd算法。

function[d,path]=floyd(a)

n=size(a,1);

设置d和path的初值。

d=a;path=zeros(n,n);

fori=1:n

forj=1:n

ifd(i,j)~=inf

path(i,j)=j;%j是i的后继点。

endend

end做n次迭代，每次迭代均更新d(i,j)和path(i,j)

fork=1:n

fori=1:n

forj=1:n

ifd(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j);

path(i,j)=path(i,k);

endend

在matlab命令窗口键入：

a=[05inf3infinf;

inf042infinf;

infinf0243;

infinfinf05inf;

infinfinfinf02;

infinfinfinfinf0];

d,path]=floyd(a)

运行结果：d=

inf04277

infinf0243

infinfinf057

infinfinfinf02

infinfinfinfinf0path=

path(1,6)＝4，意味着顶点1的后继点为4．又path(4,6)＝5，从而顶点4的后继点为5，同理，因path(5,6)＝6，从而顶点5的后继点为6，故1→4→5→6便是顶点1到顶点6的最短路径。所以，顶点1到顶点6最短路径长度为d（1,6）=10：即最短路径：

1—4—5—6。

实验小结：对于数学建模这门课程学起来感觉还是很吃力，很多时候看到题目完全没有头绪，这次的作业也只是选择了简单一点的题目，过程中遇到了一些问题，有的是matlab的问题，有的则是写的**的问题，不过最终都解决了。

数学建模实验四

数学建模实验

数学建模实验

数学建模实验

其他用户还读了