数学建模最短时间路径.doc

《数学建模最短时间路径.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.word格式,最短时间路径摘要：本问题是一个最短时间问题，本文首先对路线图进行分析，找出并画出了汽车在拐弯时所消耗时间的等效图，经分析，找到四条规则（具体见：五、模型的建立与求解），可以按这四条规则把转弯的时间算在南北走向的路线上，对图形上数据进行处理，然后通过Dijkstra算法求的从入口点v1到出口点的v8最短时间路径为：v1——>v2——>v4——>v7——>v8，时间为：15。关键词：最短路径Dijkstra算法一、问题重述在一个城市交通系统中取出一段如下图所示，其入口为定点v1，出口为定点v8，每条弧段的数字表示通过该路段所需的时间，每次转弯需

2、要附加时间为3，求v1到V8的最短时间路径。（看图时，以上下为北南，左右为西东，那么城市路线分为南北路线、东西路线）V11v23v31v56v6223v42v74v8（图一）二、问题分析本问题是最短路模型，所求为从城市的一定点（入口点）到另一定点（出口点）所需时间最少路径。由于每次转弯时要耽搁一定时间为3，所以必须对图形及数据进行等效处理易便找出最短时间路径。于是就有以下猜想和分析看法：1.是否可以把转弯的的时间附加在某条路线上，假如可以的，那么应该加在出口点的那几条路线上（例如图一的v7---v8与v6---v8这两条路）还是其他路线上.2.若加在出口点

3、的那几条路线上，那么应在v7---v8加6而在v6---v8应加3或15（5个拐弯）这样就可以解决此题，但是对于稍微复杂一点交通路线图这种做法就不科学了。3.由于每次拐弯要附加一定的时间消耗，而城市路线以2条东西路线为主，南北3条路线使东西2条路线相同，那么是否可以把转弯的时间统一加在南北路线上，经分析是可行的，而且有一定的规则（具体见：五、模型的建立与求解）问题的关键:1.找到把转弯时间附加在南北路线的内在规则。2.找到一个等效的图形（等效的办法）使得求解更为方便。三、模型假设,专业.专注..word格式,1.无论何时交通路线是可行的。2.城市的路线均为

4、方行路线（直线图）。四、符号说明vi——两条路的交汇处或重要地点.Li,j——vi与vj两地之间的这条路。Tij——vi到vj所花费的时间T——是时间的总和。五、模型建立与求解一、问题的回答观察问题中给出的图、数据，发现通过把转弯时间附加于在竖直路线上（即：把转弯时所要花费的时间一律加在所要经过的南北路线上）。具体来说就是满足偶一下规则：1.若规定出口点在此条南北路线上，则在此条路所花时间上加3（即把一个拐弯时花费的时间算在要经过的这条南北路线上）2.若规定出口点不在此条南北路线上，则在此条路所花时间上加6（即把两个拐弯时花费的时间算在要经过的这条南北路线

5、上）3.若规定的出口只在东西路线上，则在任一南北路线所花时间上加6（即把两个拐弯时花费的时间算在要经过的这条南北路线上）4.东西路线上的每段路所花时间不变。例如：若v8为出口点，此时v6到v8的时间由图一T68=3变为图二T68=3+3=6，而此时v2到v4的时间以及由图一T24=2变为图二T24=2+6=8，v5到v7的时间以及由图一T57=2变为图二T57=2+6=8。（对于其他点为出口点时，可类似求的Tij）按上述所述，此时图一可以等效化为下图二：v1　1　v23v31v56v6　　2+62＋63＋3v42v74v8（图二：即G）于是建立问题的最短时

6、间模型如下：T=Tij+Tjk+···+Tkm(1)按照图二写出G的带权邻接矩阵,专业.专注..word格式,Dijkstra算法【1】：求G中从顶点(即v1)到其余顶点的最短路.设G为赋权有向图或无向图，G边上的权均非负．对每个顶点，定义两个标记（，），其中:：表从顶点到v的一条路的权．：v的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终为从顶点到v8的最短时间的权．S：具有永久标号的顶点集。输入:G的带权邻接矩阵(1)赋初值：令S＝{,=0},，令=,=（2）更新、：,若>则令=,=(3)设是使取最小值的中的顶点，则令S=S∪

7、{}，（4）若φ，转2，否则，停止用上述算法求出的就是到8的最短路的权，从的父亲标记追溯到,就得到到8的最短时间路径。利用通过Dijkstra算法程序求的一点到其余点的最短时间可查路径表一：L(vi)v1v2v3v4v5v6v7v8最后标记：l(v)01495111115z(v)v1v1v2v2v3v5v4v7（表一）从表中可知v1到v8的最短时间路径为：v1——>v2——>v4——>v7——>v8；所用时间为：T=T12+T24+T47+T78=15二、对数据的几点讨论1.明显的v1到v8按图三进行追踪所得路线为：v1——>v2——>v4——>v7——>

8、v8，所用时间为15（最后标记值），所得值可达到最少；2.对于v1