图论模型在实际中的应用

数学建模雷涛 罗睿辞 王尧 汪瑜婧

数学建模的定义 目前还没有统一的定义 数学模型是为一种特殊目的而建立 的一个抽象的、简化的结构。 描述现实世界的一部分特征 表现事物之间的一部分客观联系

数学模型的分类 微分方程模型 差分方程模型 层次分析模型 线性规划模型 动态规划模型 图论模型 其它模型

主要内容 建模的方法和步骤 ——汪瑜婧 图论模型的建立 ——罗睿辞 图论模型的选择和关系的简化 ——雷涛 其它数学模型举例 ——王尧

建模的方法和步骤 模型准备 模型假设 模型的建立 模型求解与分析 模型检验 模型应用

问题的提出 2007CUMCM B题 乘公交，看奥运

给定若干条公交线路，以及在每条公交线 路中任意相邻的两站之间所花费的时间。 并且给定乘客在任意站点换乘的耗时 要求给出任意两公汽站点之间线路选择问 题的一般数学模型与算法，求出最佳的公 交线路.

模型的假设 对”最优”的理解有三个具有代表性的指标： 时间最短 花费最少 最方便(换乘次数最少) 不同的人群对最优的理解不同,需要根据实 际定义.可以根据需要定义代价函数,三个指 标的权重不同,代价值也不同。 以时间最短为例

模型的建立 G=(V,E) 每个车站：G的顶点 每条公交线路相邻两点的连线：G的边 边的权重：耗费时间 点的权重：换乘时间 并不是一个简单图，两点间可能有多条边7 a 9 5 b(8) c

3

与经典最短路径问题比较 考虑a经过b到c的最短路径 由于有换乘的情况，只记录任意两点间的 最短路径是不够的。 并非一个标准的图论模型7 a 6 5 b(8) c

Min(a,b)=5 Min(b,c)=3

Min(a,c)=5+6=113

转化成标准的图论模型 每条公交线路抽象 为一层 层与层之间相连的 顶点均代表同一个 车站 它们之间的边(虚 线)的权值为换乘 花费的时间

调用M*M次Dijkstra算法才能得到最优解 M为公交线路的总数

7 a6

c

Min(a,b)=5Min(b,c)=3

5b(8)

3

Min(a,c)=5+6=11

回顾上图 导致无法使用标准算法原因:– Min(a,b)和Min(b,c)之间需要计算附加耗时 – 不用换车的线路成为最佳路径

改进的想法:一次性地处理不用换车的情况

模型的求解 标准算法: – 每次选择一个新顶点进行扩展 – 所有顶点扩展完毕即为最优解

修改后的算法 – 每次对一个顶点所能选择的所有公交线路扩 展 – 所有不用换乘就能到达的顶点均在一次中处 理 – 所有顶点扩展完毕即为最优解.

算法描述 一次将扩展出多个顶点,用最小值堆保存 初始: 起点对应的节点S入堆

;并赋予标 志信息Time(S)=0 取堆顶,对此定点,逐一枚举所有不用换乘 就能到达的顶点,更新堆中对应点的标志信 息. 不断重复取堆顶的过程,直到取出的顶点为 最终目标T Time(T)即为所求

举例说明算法步骤c12 a 3 g 2

2

9 4

d 15 8 11

9 9

22

5

3f b 6 5 20 1 e

考虑顶点b到顶点g的路径

问题重述 加入步行的因素,即任意两个车站之间人都 可能通过步行到达,并给出步行的时间代价.

20

7 a6

c

加入步行的路径 并给定权值

5

由于每两点之间均有步行路径,每次扩展都将涉及 到所有顶点,复杂度增加不少 改进的办法 – 预处理 找到两个相邻顶点之间路径的最小值, 如果它加上两个顶点的权值之后后,仍然小于一 些其它的路径,就可以将其它路径删除.这样至少 可以删除不少步行路径 – 考虑实际情况,可设定步行时间的上限.