图与网络模型实验.pptx
图与网络模型实验2023/3/6数学建模1a=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/3/6数学建模1实验内容与步骤：渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。2023/3/6数学建模1最短路问题定义：1）人M（Man），狼W（Wolf），羊G（Goat），草H（Hay）2）点vi表示河岸的状态3）边ek表示由状态 vi经一次渡河到状态 vj4）权边 ek上的权定为 1我们可以得到下面的加权有向图2023/3/6数学建模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的最短路问题。v1v2v3v4v5u5u4u3u2u1根据题意，人不在场时，狼要吃羊，羊要根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊，吃菜，因此，人不在场时，不能将狼与羊，羊与蔬菜留在河的任一岸。例如，状态（羊与蔬菜留在河的任一岸。例如，状态（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.5clc,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/3/6数学建模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/3/6数学建模1S=1 1 2 2 3 3 4 4 4 4 5 6 6 7 8;%起始起始节点向量点向量 E=2 3 5 4 4 6 5 7 8 6 7 8 9 9 9;%终止止节点向量点向量W=1 2 12 6 3 4 4 15 7 2 7 7 15 3 10;%边权值向量，有向向量，有向图，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,1 0.4 0.4);%以下三条以下三条语句用句用红色修色修饰最短路径最短路径edges=getedgesbynodeid(H,get(H.Nodes(Path),ID);set(edges,LineColor,1 0 0);set(edges,LineWidth,2.0);
