《城市交通》问题解题报告.doc

《城市交通》问题解题报告
题目分析
《城市交通》问题的图论模型很简单。如果只考虑从城市1到城市N的最少时间，那么，这个问题就是一道求最短路径的问题。求最短路径问题在图论中是一道很基本的试题，有很多方法可以解决。这个问题，开始就给人一种熟悉的感觉，而实质呢？问题的“变数”在于“市政府”的改革措施很奇特，即每加一条公共汽车路线，则两个街区之间的旅行时间就缩短为原来的一半。这就给人一种“无处着手”的感觉。显然，这个改革不能分步执行，即它不具有“贪心法”的要求，而如果用搜索的方法解决，时间会很庞大。那么，该如何解决呢？
在求两点之间的最短路径时，有一种比较优秀的方法：“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。
这个算法实质上就是一个“动态规划”算法。它是以最短路中间结点的取值来划分阶段的。第K个阶段为所有最短路的中间结点<=K时的情况。而第K个阶段只与前(K-1)个阶段有关系，所以，这个问题同时满足“无后效性”与“最优子问题”这两个性质，这个“动态规划”算法是正确的。
而在求改进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算法相同，所