图论模型及其算法概要.ppt

* * * * * * * * * * * * * * * * * * * * * * 图论模型构建 长沙市一中 曹利国 最短路模型构建 例题1: (TRAVEL) 一个城市中有N个车站，已知M条连接这些车站的公共汽车单向路线，设计算法求出从第一号车站到第N号车站的最少换车次数. 分析 这道题粗看起来似乎不太简单，但我们仔细分析一下题目就会发现，这道题实际上可以转化为最短路径问题来进行求解。 考虑经过的所有路线中，每条路线都只保留一头一尾两个车站，则经过的车站数目再减2实际上就是所求的换车次数了。要使换车次数最少，也就是要找从1到N的一条最短路径。而图中的边也需要重新设计。 在每一条路线中，任两个结点均由其中的前者向后者连一条边，然后将每条边的长度都定为1。 最短路 例题2：求第一、第二、第三最短路问题 例题3：城市交通 见文档 城市交通分析 在求两点之间的最短路径时，有一种比较优秀的方法：“Floyd-Warshall”算法，其算法的中心思想是这样的： 求A至B的满足中间结点不超过K的最短路径。而后，随着K逐渐增加至N而求出A至B的最短路径。 则其算法的结构如下： For K=1 To N {K从1增至N} For A=1 To N Do For B=1 To N Do {求每一对结点的中间结点不超过K的最短路径} IF (Map[A,K]0) And (Map [K,B]0) Then {如果A与K，K与B均可达} IF (Map[A,B]=0) Or (Map[A,B]Map[A,K]+Map[K,B]) Then {如果A、B不可达，或者A、B之间的路径不如A-K-B这条路径短，则改变Map[A,B]的值} Map[A,B]:=Map[A,K]+Map[K,B]; 注：Map[A,B]为从A到B的最短路的距离，如果A,B不可达，则Map[A,B]=0。 在求改进M条边使最短路下降最快中，我们同样可以发现： 1：将道路A-B改造M条边可以分为如下两个问题（如果K是最短路上的一点） 一：求A-K改造T条边； 二：求K-B改造M-T条边。 T可以取从0至M的任意值。问题A-B改造M条边的最优解取决与这两个子问题的最优解。 2：在求M条边的过程中，始终只与改造T与M-T条边的问题发生联系。 ? 以上两个特点即为“动态规划”的“无后效性”与“最优子问题”两个性质。所以，这个“城市交通”问题的算法为“动态规划”算法。 设Map[A,B,M]的值为从A到B且改造M条边的最短路长度，则： Map[A,B,M]=Min{Map[A,K,T]+Map[K,B,M-T]} 其中T为从0到M中的一个数，K为A到B中间的一点。 这个问题在确定K是与Floyd算法相同，所以这个问题实质上是一个“双重动态规划”问题。具体算法如下： For G:=1 To M Do {分M个阶段来解这个问题} ? 　　　 For K:=1 To N Do For I:=1 To N Do For J:=1 To N Do{Floyd算法} Begin For T:=0 To G Do If Map[I,K,T]+Map[K,J,G-T]Map[I,J,G] Then Map[I,J,G]:=Map[I,K,T]+Map[K,J,G-T]; End; 说明：这个问题的Map数组的初始值与上一个Floyd算法不一样，初始值均为MaxInt。算法的时间复杂度为O(N^3*M^2)，约为O(N^5)，还是一个多项式级的算法。 公路通行税 在PALMIA国家内，有N个城市由公路相连（每条公路恰好双向连接两个城市）。经由一条公路或多条公路，从任一城市出发可以到达其余各个城市。直到今年，公路上才要征收公路通行税。在每条公路的中间，有一征税员，从每一辆经由此路的车收取 1 PALMIA COIN（1PC）。 政府官员决定减少收税员而推行公路印花。如果一辆车欲进入一条公路，就必须将这张印花贴在窗上。政府官员决定：一年的公路印花的价值相当于在两个最远城市之间进行100次旅行所需的费用。两个城市之间的距离是从一个城市