数学建模～最短路问题(课件ppt).ppt

最短路问题 二 最小生成树问题及其解法 三 最短路问题及其解法 一 图论的基本概念 图论的基本概念 一 图的概念 1 图的定义 2 顶点的次数 3 子图 二 图的矩阵表示 1 关联矩阵 2 邻接矩阵 返回 图的定义 定义 定义 返回 顶点的次数 例2在一次聚会中 史密斯先生和他太太邀请四对夫妻参加晚会 每个人到的时候 房间里的一些人都要与别的一些人握手 当然 每个人都不会与自己的配偶握手 也不会跟同一个人握手两次 之后 史密斯先生问每个人和别人握了几次手 他们的答案都不一样 那么史密斯太太和别人握了几次手呢 返回 例1在一次聚会中 认识奇数个人的人数一定是偶数 由图可知 8号的配偶是0号 7号的配偶是1号 6号的配偶是2号 5号的配偶是3号 史密斯太太是4号 所以史密斯太太和别人握了4次手 返回 邻接矩阵 注 假设图为简单图 返回 最短路问题及其算法 一 基本概念 二 固定起点的最短路 三 每对顶点之间的最短路 返回 基本概念 返回 返回 求图的最小生成树最常用的两种算法 1 Prim算法 2 Kruskal算法 注意 在一个加权连通图G中 权最小的那棵生成树称为图G的最小生成树 返回 Prim算法思想 输入加权图的带权邻接矩阵 1 建立初始候选边集B 2 从候选边中选取最短边 u v 3 调整候选边集B 4 重复 2 3 直到T含有n 1条边 Prim算法的实现过程 111123458inf15 439 453 527 236 实现Prim算法的MATLAB程序 a 08inf15 806inf7 inf60910 1inf903 571030 T e 0 v 1 n 5 sb 2 n 1代表第一个红点 sb代表白点集 forj 2 n 构造初始候选边的集合b 1 j 1 1 b 2 j 1 j b 3 j 1 a 1 j end whilesize T 2 n 1 min i min b 3 在候选边中找最短边 T size T 2 1 b i e e b 3 i v b 2 i v表示新涂的红点 temp find sb b 2 i sb temp b i forj 1 length sb 调整候选边d a v b 2 j ifd b 3 j b 1 j v b 3 j d endendend Kruskal算法思想 假设给定了一个加权连通图G G的边集合为E 顶点个数n 则假设最小生成树T中的边和顶点均涂为红色 其余为白色 初始时G中的边均为白色 1 将所有的顶点涂成红色 2 在白色边中 挑选一条权最小的边 使其与红色边不形成圈 将该白色边涂红 3 重复 2 直到n 1条红色边 这n 1条红色边就构成了最小生成树T的边集合 注意 在用Kruskal算法求最小生成树时 在第 2 步判断是否形成圈在程序实现时比较麻烦 实现Kruskal算法的MATLAB程序 加权图的存储结构采用边权矩阵 b i j m 3b 1112233424535455815679103 B I sortrows b 3 B B m size b 2 n 5 t 1 n k 0 T c 0 fori 1 mift B 1 i t B 2 i 判断第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 nift j tmaxt j tmin endendendifk n 1break endendT c Kruskal实现过程 初始化后排序 B 1412213345535245135678910 第一轮 tmin 1 tmax 4 t 12315 第二轮 tmin 4 tmax 5 t 12311 第三轮 t 1 t 5 直接进入下一轮第四轮 tmin 2 tmax 3 t 12211 第五轮 tmin 1 tmax 2 t 11111 求最短路径的最常用的两种算法 1 Dijkstra算法 2 Floyd算法 注意 普通路径长度定义为该路径所包含的全体边的长度之和 最短路径是指在图中 从顶点u到顶点v的路径中普通路径长度最短的路径称为u到v的最短路径 固定起点的最短路 最短路是一条路径 且最短路的任一段也是最短路 假设在u0 v0的最短路中只取一条 则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此 可采用树生长的过程来求指定顶点到其余顶点的最短路 算法步骤 TOMATLAB road1 1 2 3 4 5 6 7 8 返回 Dijkstra算法的MATLAB实现 w 0218infinfinfinf 20inf61infinfinf 1inf07infinf9inf 8670512inf inf1inf503inf9 infinfinf13046 infinf92inf403 infinfinfinf9630 n size w 1 w1 w 1 赋初值fori 1 nl i w1 i z i 1 ends s 1 1 u s 1 k 1 whilekl u w u i l i l u w u i z i u endendendendl z 求v ll l fori 1 nforj 1 kifi s j ll i ll i elsell i inf endendend lv inf fori 1 nifll i lvlv ll i v i endendlv vs k 1 vk k 1u s k endl z 每对顶点之间的最短路 1 求距离矩阵的方法 2 求路径矩阵的方法 3 查找最短路路径的方法 一 算法的基本思想 三 算法步骤 返回 二 算法原理 算法的基本思想 返回 算法原理 求距离矩阵的方法 返回 算法原理 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R 即当k被插入任何两点间的最短路径时 被记录在R k 中 依次求时求得 可由来查找任何点对之间最短路的路径 返回 算法原理 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为 返回 算法步骤 TOMATLAB road2 floyd 返回 Folyd算法的MATLAB实现 function D R floyd a n size a 1 D afori 1 nforj 1 nR i j j endend fork 1 nfori 1 nforj 1 nifD i k D k j D i j D i j D i k D k j R i j R i k endendendk D Rend 在命令窗口中输入 a 09inf3inf 902inf7 inf2024 3inf20inf inf74inf0 floyd a 一 可化为最短路问题的多阶段决策问题 二 选址问题 1 中心问题 2 重心问题 返回 可化为最短路问题的多阶段决策问题 返回 选址问题 中心问题 TOMATLAB road3 floyd S v1 10 S v2 7 S v3 6 S v4 8 5 S v5 7 S v6 7 S v7 8 5 S v3 6 故应将消防站设在v3处 返回 选址问题 重心问题 返回 实验作业 生产策略问题 现代化生产过程中 生产部门面临的突出问题之一 便是如何选取合理的生产率 生产率过高 导致产品大量积压 使流动资金不能及时回笼 生产率过低 产品不能满足市场需要 使生产部门失去获利的机会 可见 生产部门在生产过程中必须时刻注意市场需求的变化 以便适时调整生产率 获取最大收益 某生产厂家年初要制定生产