基本知识及最短路最小树问题.pptVIP

二元关系 父子关系 同学关系 夫妻关系 老乡关系 常见图类 完全图：任意两点间都有边 圈 树：没有圈的连通图 二分图： 较简单的图的模型的建立 可以建立图的模型的问题的特征： 研究对象是离散的；对象之间存在某种二元关系。 以城市为点，两个点之间有边当且仅当两个城市之间有公路相通 以每个人为点，两个点之间有边当且仅当两个人相互认识。若单向的认识可用有向边。 有五个工人、五项工作，这五个工人能够干五项工作中的一个或几个，并且有不同的质量。用一个图来表示这一关系。 1、在下面这个去掉了一个角的棋盘上，能够用1×2的小棋盘不重不漏的全部覆盖住呢？ 常见网络优化问题 最短路问题 最大流问题 最优匹配 规划审核技术与关键路径法 最小费用流问题 装箱问题 TSP问题、中国邮递员问题 网络可靠性问题 其中很多问题现在没有成熟的方法，或者说根本就不存在好的算法。 许多现实问题是在上述问题的基础上增加要求得到的。如多邮递员等。 返回 §6.4 树及其算法 § 6.4.1 相关的概念 定义 6.4.1 无圈的连通图称为树。 定义 6.4.2 若图 G 的生成子图 H 是树，则称 H 为 G 的生成树或支撑树。 一般来讲，一个图的生成树不唯一。 定义 6.4.3 在赋权图 G 中，边权之和最小（大）的生成树称为 G 的最小（大）生成树。 § 6.4.2 最小生成树算法 一个简单连通图只要不是树，其生成树就不唯一，而且非常多。一般地，n 个顶点地完全图，其不同地生成树个数为 nn?2。因而，寻求一个给定赋权图的最小生成树，一般是不能用穷举法的。所以，穷举法求最小生成树是无效的算法，必须寻求有效的算法。 在求最小生成树的有效算法中，最著名的两个是 Kruskal（克罗斯克尔）算法和 Prim（普瑞姆）算法，其迭代过程都是基于贪婪法来设计的。 最短路问题、最小生成树问题、TSP问题、最大流、最小费用最大流问题、匹配问题都能建立优化模型用lingo求解。 * 1．图 论 的 基 本 概 念 2．最 短 路 问 题 及 其 算 法 3．最 短 路 的 应 用 最短路问题 图 论 的 基 本 概 念 一、 图 的 概 念 1．图的定义 2．顶点的次数 二、 图 的 矩 阵 表 示 1． 关联矩阵 2． 邻接矩阵 返回 定义 有序三元组G=(V,E, )称为一个图,如果： 图的定义 定义 定义 1、以方块为点，两点相邻当且仅当两个方块有公共边，得到一个二分图。 2、匹配：一个边的集合，其中任意两条边没有公共点。 3、完美匹配：包含了所有的点的匹配即完美匹配。 4、若一个二分图有完美匹配，其点集的两个二分划必须有相同点数。 关联矩阵 注：假设图为简单图 返回 邻接矩阵 注：假设图为简单图 返回 最 短 路 问 题 及 其 算 法 一、 基 本 概 念 二、固 定 起 点 的 最 短 路 三、每 对 顶 点 之 间 的 最 短 路 返回 基 本 概 念 固 定 起 点 的 最 短 路 最短路是一条路径，且最短路的任一段也是最短路． 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树． 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路． 迪杰斯特拉 算法步骤： TO MATLAB(road1) 1 2 3 4 5 6 7 8 返回 每 对 顶 点 之 间 的 最 短 路 1．求距离矩阵的方法 2．求路径矩阵的方法 3．查找最短路路径的方法 （一）算法的基本思想 （三）算法步骤 返回 算法的基本思想 返回 算法原理—— 求距离矩阵的方法 返回 算法原理—— 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R． 即当　k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径． ) ( n R i j 算法原理—— 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为： 返回 算法步骤 TO　MATLAB　(road2(floyd)) 返回　 可化为最短路问题的多阶段决策问题 设备更新问题 返回 可化为最短路问题的多阶段决策问题