图与网络模型实验.pptx
- 文档编号:18720307
- 上传时间:2023-10-18
- 格式:PPTX
- 页数:25
- 大小:3.03MB
图与网络模型实验.pptx
《图与网络模型实验.pptx》由会员分享,可在线阅读,更多相关《图与网络模型实验.pptx(25页珍藏版)》请在冰点文库上搜索。
图与网络模型实验,2023/10/18,数学建模1,a=zeros(6);%邻接矩阵初始化a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;a(4,5)=10;a(4,6)=25;a(5,6)=55;a=a;b=sparse(a)h=view(biograph(b,ShowArrows,off,ShowWeights,off),实验项目名称:
图论模型MATLAB软件预处理,实验目的与原理:
掌握图与网络在计算机中数据存取方法,将图与网络转化为领接矩阵、稀疏矩阵等多种方法,矩阵的各种读写方式。
2023/10/18,数学建模1,实验内容与步骤:
渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸,河上只有一条独木舟,每次除了人以外,只能带一样东西;另外,如果人不在,狼就要吃羊,羊就要吃白菜,问应该怎样安排渡河,才能做到既把所有东西都运过河去,并且在河上来回次数最少?
这个问题就可以用求最短路方法解决。
2023/10/18,数学建模1,最短路问题,定义:
1)人M(Man),狼W(Wolf),羊G(Goat),草H(Hay)2)点vi表示河岸的状态3)边ek表示由状态vi经一次渡河到状态vj4)权边ek上的权定为1,我们可以得到下面的加权有向图,2023/10/18,数学建模1,最短路问题,状态说明:
v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G),此游戏转化为在下面的二部图中求从v1到u1的最短路问题。
v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,根据题意,人不在场时,狼要吃羊,羊要吃菜,因此,人不在场时,不能将狼与羊,羊与蔬菜留在河的任一岸。
例如,状态(0,1,1,0)表示人和菜在对岸,而狼和羊在此岸,这时人不在场狼要吃羊,因此,这个状态是不可行的。
通过穷举法将所有可行的状态列举出来,可行的状态有(1,1,1,1),(1,1,1,0),(1,1,0,1),(1,0,1,1),(1,0,1,0),(0,1,0,1),(0,1,0,0),(0,0,1,0),(0,0,0,1),(0,0,0,0)可行状态共有十种。
每一次的渡河行为改变现有的状态。
现构造赋权图,其中顶点集合中的顶点(按照上面的顺序编号)分别表示上述十个可行状态,当且仅当对应的两个可行状态之间存在一个可行转移时两顶点之间才有边连接,并且对应的权重取为1,当两个顶点之间不存在可行转移时,可以把相应的权重取为inf。
因此问题变为在图中寻找一条由初始状态(1,1,1,1)出发,经最小次数转移达到最终状态(0,0,0,0)的转移过程,即求从状态(1,1,1,1)到状态(0,0,0,0)的最短路径。
这就将问题转化成了图论中的最短路问题。
该题的难点在于计算邻接矩阵,由于摆渡一次就改变现有的状态,为此再引入一个四维状态转移向量,用它来反映摆渡情况。
用1表示过河,0表示未过河。
例如,(1,1,0,0)表示人带狼过河。
状态转移只有四种情况,用如下的向量表示(1,0,0,0),(1,1,0,0),(1,0,1,0),(1,0,0,1)。
clc,cleara=1111;1110;1101;1011;10100101;0100;0010;0001;0000;%每一行是一个可行状态b=1000;1100;1010;1001;%每一行是一个转移状态w=zeros(10);%邻接矩阵初始化fori=1:
9forj=i+1:
10fork=1:
4iffindstr(mod(a(i,:
)+b(k,:
),2),a(j,:
)w(i,j)=1;endendendendw=w;%变成下三角矩阵i,j,v=find(w);%找非零元素c=sparse(i,j,v,10,10)%构造稀疏矩阵x,y,z=graphshortestpath(c,1,10,Directed,false)%该图是无向图h=view(biograph(c,ShowArrows,off,ShowWeights,off);Edges=getedgesbynodeid(h);%提取句柄h中的边集set(Edges,LineColor,000);%为了将来打印清楚,边画成黑色set(Edges,LineWidth,1.5);%线型宽度设置为1.5,clc,cleara=zeros(7);a(1,2)=4;a(1,3)=2;a(2,3)=3;a(2,4)=2;a(2,5)=6;a(3,4)=5;a(3,6)=4;a(4,5)=2;a(4,6)=7;a(5,6)=4;a(5,7)=8;a(6,7)=3;b=sparse(a);%构造稀疏矩阵,这里给出构造稀疏矩阵的另一种方法x,y,z=graphshortestpath(b,1,7,Directed,true,Method,Dijkstra)%Directed是有向的h=view(biograph(b,ShowArrows,on,ShowWeights,on),2023/10/18,数学建模1,最短路问题软件求解,
(1)用狄克斯屈拉算法写代码
(2)用逐次逼近法写代码(3)用graphshortestpath()(4)0-1线性整数规划模型x=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,options)x=bintprog(f,A,b,Aeq,beq),2023/10/18,数学建模1,S=112233444456678;%起始节点向量E=235446578678999;%终止节点向量W=1212634415727715310;%边权值向量,有向图,G(9,9)=0;9个节点G=sparse(S,E,W);%关联矩阵的稀疏矩阵表示G(9,9)=0;P=biograph(G,ShowWeights,on);%建立有向图对象PH=view(P);%显示各个路径权值Dist,Path=graphshortestpath(G,1,9,Method,Dijkstra)%求节点1到节点9的最短路径set(H.Nodes(Path),Color,10.40.4);%以下三条语句用红色修饰最短路径edges=getedgesbynodeid(H,get(H.Nodes(Path),ID);set(edges,LineColor,100);set(edges,LineWidth,2.0);,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 模型 实验