最短路径导航.docx
- 文档编号:17828751
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:18
- 大小:475.03KB
最短路径导航.docx
《最短路径导航.docx》由会员分享,可在线阅读,更多相关《最短路径导航.docx(18页珍藏版)》请在冰点文库上搜索。
最短路径导航
数学建模
最短路问题
模拟GPS卫星导航系统计算北京市西四到天坛公园北门的最短路问题。
周盛友
2013/6/22
项目名称
最短路径问题
人员情况
周盛友
人员分工情况
论文:
周盛友
模型:
周盛友
假设讨论:
周盛友
算法:
周盛友
摘要
本文是一个与实际息息相关的最短路径问题,通过以北京市西四城区到天坛公园北门为例子去论述这个原理及算法,模拟出GPS卫星导航的基本原理。
它是自动定位车辆的当前位置,并执行接收用户反馈的信息:
起点,终点。
在内部进行数据的处理,经过最短路径的几种算法原理,找出最合适的一种反馈给用户。
经过模型的设计后,得出的数据与网上查询的最短路结果吻合。
对于处理这个问题,如何做到拟合性较精确的的模拟,以下我提出了一个数学模型:
矩阵对角线区域模型。
针对在实际的情况下两点连线距离最小而延伸的矩阵区域范围内求对角两点之间的最短距离。
利用Matlab软件编程,进行模拟,反馈详细的信息给用户。
并提出在多种相同的情况下根据实时路况,途径红路灯的多少,周边风景等多种客观因素进行综合性的分析,反馈用户最满意的一条路线。
改进模型,对于同时拥有多条最短路径,根据用户的需求进行客观分析问题,导入权重,进行筛选,得出唯一解。
关键字:
最短路径矩阵卫星导航筛选
1、问题重述
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
搜集资料,作一个最短路径问题算法的专题报告,阐述最短路径的的几种算法原理,并利用最短路径算法,解决下面的问题:
驾车旅行时,GPS汽车导航仪会自动确定车辆的所在位置,并以此为坐标,帮你选择一条涵盖起点和终点的最佳的道路网络图。
假设你在北京驾车,试建立数学模型模拟汽车导航仪选择一条从西四去往目的地天坛公园北门的最佳行车线路(地图上黄色的路线是可行车道路,里程数据可通过XX地图获得)。
2最短路径的的几种算法原理
一、迪杰斯特拉(dijkstra)算法
原理
首先,引进一个辅助向量D,它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。
如D[3]=2表示从始点v到终点3的路径相对最小长度为2。
这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。
它的初始状态为:
若从v到vi有弧,则D为弧上的权值;否则置D为∞。
显然,长度为D[j]=Min{D|vi∈V}的路径就是从v出发的长度最短的一条最短路径。
此路径为(v,vj)。
那么,下一条长度次短的最短路径是哪一条呢?
假设该次短路径的终点是vk,则可想而知,这条路径或者是(v,vk),或者是(v,vj,vk)。
它的长度或者是从v到vk的弧上的权值,或者是D[j]和从vj到vk的弧上的权值之和。
一般情况下,假设S为已求得最短路径的终点的集合,则可证明:
下一条最短路径(设其终点为X)或者是弧(v,x),或者是中间只经过S中的顶点而最后到达顶点X的路径。
因此,下一条长度次短的最短路径的长度必是D[j]=Min{D|vi∈V-S}其中,D或者是弧(v,vi)上的权值,或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。
迪杰斯特拉算法描述如下:
1)arcs表示弧上的权值。
若不存在,则置arcs为∞(在本程序中为MAXCOST)。
S为已找到从v出发的最短路径的终点的集合,初始状态为空集。
那么,从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[LocateVex(G,v),i]vi∈V2)选择vj,使得D[j]=Min{D|vi∈V-S}3)修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。
二、蚁群算法的原理
自然界中的蚂蚁是没有视觉的,既不知道向何处寻找食物,也不知道发现食物后如何返回自己的巢穴,它仅仅依赖于同类散发在周围环境中的特殊物质—信息素的轨迹,来决定自己何去何从。
但是尽管没有任何先验的知识,但蚂蚁们还是有能力找到从其巢穴到食物源的最佳路径。
所以大量研究发现,同一蚁群中的蚂蚁能感知信息素及其强度,后来的蚂蚁会倾向于朝信息素浓度高的方向移动,而移动留下的信息素又会对原有信息素进行加强,后续的蚂蚁而后续的蚂蚁选择该路径的可能性也越大。
由于在相同时间段 内越短的路径会被越多的蚂蚁访问,所以后续的蚂蚁选择较短路径的可能性也越大,最后所有的蚂蚁都走最短的那条路径。
三、动态规划原理概述
动态规划最优化原理,可以这样阐述:
一个最优化策略不伦过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略,及其子决策总是最优的,任何思想方法都有一定的局限性,动态规划也有其适用的条件,如果某阶段的状态给定后,则在这个阶段以后的过程的发展不受这阶段以前各段状态的影响,这个性质称为无后效性,适用动态规划的问题必须满足这个性质;其次还需满足上述最优化原理,动态规划基本思想一是正确地写出基本的递推关系和恰当的边界条件;二是在多阶段决策过程中,动态规划方法是既把当前一段和后来各段分开,又把当的效益和未来效益结合起来考虑的一种多阶段决策的最优化的方法,每阶段决策和选取是从全局来考虑的,与该段的最优选择的答案一般是不同的;三是在求整个问题的最优策略时,由于出事状态是已知的,而每阶段的决策又都是改阶段状态的函数,因而最优策略所经过的各阶段状态便可逐次变换得到,从而确定最优路线,简而言之动态规划的基本思想就是把全局的问题化为局部的问题,为了全局最优必须局部最优。
四、弗洛伊德算法 原理(Floyd-Wrashall)
Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间结点的最短路径的长度。
1.若最短路径经过点k,则Di,j,k = Di,k,k −1 + Dk,j,k −1;
2.若最短路径不经过点k,则Di,j,k = Di,j,k −1。
因此,Di,j,k =min(Di,k,k −1 + Dk,j,k −1,Di,j,k −1)。
在实际算法中,为了节约空间,可以直接在原来空间上进行迭代,这样空间可降至二维。
(见下面的算法描述)
Floyd-Warshall算法的描述如下:
for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do if (Di,k + Dk,j < Di,j) then Di,j ← Di,k + Dk,j;
其中Di,j表示由点i到点j的代价,当Di,j为∞表示两点之间没有任何连接。
3、最短路的背景介绍和发展
一:
背景介绍
设计模拟GPS卫星导航求最短路径问题。
1)求出北京市西四到天坛公园北门的最短路径
2) 在社会生活中,最短距离的运用相当广泛。
除了该课题外,还有于此相关的城市道路的设计,交通线路的设计,旅游景点的设计等等。
除了路径长度方面外,到两地花费的最少、时间的最短等等都是同样的道理。
二:
发展
以后,这不仅仅是作为数学或图论中的一个经典算法,它将逐步适应社会的各行事业的发展需求而作为一门学科去被人研究,分析。
4、最短路的问题分析和数学模型
4-1:
问题的假设
假设:
1、起点与终点作矩阵的对角线,且矩阵区域内有最短路径(连通起点与终点)解。
2、卫星监控期间,忽略突发事件造成的路面大面积出现维修而导致汽车无法通过的情况。
分析讨论:
1、模拟雷达搜索目标时的情景,再结合坐标轴的位置,设起点为原点(0,0);搜索终点的象限,进而确定矩阵的面积范围。
2、在实际过程过,道路的覆盖方式无法完全理想化恰恰好在选取的矩阵区域内,因此在处理过程中允许存在误差,但要适当。
3、节点与节点之间的选取问题:
当结点连接到下一结点时,出现多个端点的情况,但我们只选取最靠近终点的两个结点或一个结点,其他舍去。
4、在做无向图的时候采取矩阵形状去进行绘点,左上角为起点V1,右下角为终点Vn,这样的好处是能很好模拟卫星的监测方式和与地图的对应地理信息。
5、选取结点的标准:
不以公交站或标志性建筑物等为结点,这样会搞成信息的混乱度大大增大;我经模拟卫星从鸟瞰式的选取结点方式,最终决定选取转弯路段(转弯前必须包含两个方向以上的十字路口)作为结点的选取标准。
4-2:
数学模型--矩阵对角线区域模型
4-2-1:
通过对该矩阵范围内的所有满足分析结果的结点进行筛选,并绘制北京市西四到天坛公园北门的无向图,如下图:
注:
各街道名称省略,可查XX地图资料
驾车—>西四—>天坛公园北门-->把地图扩大到能看见街道名称的范围即可。
4-2-2:
Dijkstra模型的选取
因为最短路径问题的算法的根本核心是:
从每一个子决策的最优解逐渐推出最终最优解,即可用到贪心算法的基本原理去实验—Dijkstra算法。
Dijkstra算法是贪心算法的一个典型体现。
但由于我们本文的解是关于最初位置到最末位置的最短路问题求解,恰好满足Dijkstra的最初理念,因此可以直接借用Dijfastra算法,然后输入矩阵W,得出结果。
结果包含:
V1-V24的最短距离,而且还能输出结点与结点之间的索引,追溯回到V1。
这个过程正是卫星定位的最重要部分。
注:
用弗洛伊德算法 (Floyd-Wrashall)也可以。
5、最短路的算法实现和代码
5-1:
伪代码
a=ones(n)+inf;
fori=1:
n
a(i,i)=0;
end
输入结点与结点之间的权重:
a(1,2)=1.6;
a(1,3)=1.9
……
a(21,22)=0.9;
a(22,23)=0.7;
fori:
2ton
forj:
1to(i-1)
a(i,j)=a(j,i);
end
end
寻找矩阵最大值M=max(max(a))
开一个一维数组记录每个顶点的状态pb
开一个索引数组用来记录顶点的索引index2
初始化数据
Whilesum(pb) 寻找没有完成最优的顶点: tb=find(pb==0) 更新l(v) 记录最小值的顶点find(d(tb)==min(d(tb))) 若返回多个解,则取第一个即可 并记录为已完成最优解的状态 寻找索引值 If索引值返回多解 取第一个即可 End 记录索引值到index2 End 5-2: N-S框图 5-3 完整的Matlab代码: functionDijkf_one(a) n=length(a); A=a; load=cell(17,18); load{1,2}='文津街';load{1,3}='西单北大街'; load{2,4}='景山前街';load{2,5}='北长街-南长街'; load{3,5}='西长安街';load{3,6}='宣武门内大街'; load{4,7}='北河沿大街';load{5,7}='东长安街'; load{6,8}='宣武门东大街';load{6,9}='宣武门外大街'; load{7,10}='正义路';load{8,10}='门前西-东大街';load{8,11}='南新华街'; load{9,11}='骡马市大街';load{9,12}='宣武门外大街'; load{10,13}='门前东大街'; load{11,14}='珠市口西大街';load{11,15}='虎坊路'; load{12,15}='南横东街';load{13,16}='祈年大街'; load{14,16}='珠市口东大街';load{14,17}='门前大街'; load{15,17}='北纬路';load{16,18}='祈年大街'; load{17,18}='天坛路'; fori=2: n forj=1: (i-1) a(i,j)=a(j,i); end end M=max(max(a)); pb(1: length(a))=0; pb (1)=1; index1=1; index2=ones(1,length(a)); d(1: length(a))=M; d (1)=0; temp=1; whilesum(pb) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb (1)); pb(temp)=1; end index2=[]; index2=[index2n]; fori=n-1: -1: 1 ifd(i)+A(i,n)==d(n) index2=[index2i]; n=i; end ifindex2(end)==1 break; end end indexinfo=index2(end: -1: 1); fprintf('起点(西四)到终点(天坛公园北门)的最短距离为: %d\n',d(end)); fprintf('所途径的路径为: \n'); fprintf('%s',load{indexinfo (1),indexinfo (2)}); fori=2: length(indexinfo)-1 fprintf('-->%s',load{indexinfo(i),indexinfo(i+1)}); end 6、最短路的主要结果及其分析讨论 6-1: 从XX地图搜到的信息与实验结果作比较 实验结果(输入数据)得: XX地图搜索结果: 可以看出: 实验模拟的结果也从XX地图搜到的结果很吻合,其中的误差是我在建立模型选取结点的原则(两端结点取一个街道的名字)导致的,因为这样就会出现重复的街道现象,例如: 祈年大街1-祈年大街2.其实它们都是同一条街道! 但总的来说通过网上的数据录入,然后再通过自己稍微改进一下Dijkstra算法,这样得出的结果还是比较精确的。 6-2: 结果分析 1、从6-1的结果可知。 数据不会出现大幅度的偏差,正因为有了这个“矩阵对角线区域模型”的建立。 其原则模拟雷达搜索过程: 以起点作为雷达中心,以扫描式的方法去确定终点的位置。 然后再结合平面直角坐标系,确定终点象限。 最后通过靠终点方向最近点优先选取-最多选取两个点即可。 不断迭代到终点。 这样就会很好避免了结点的选取问题,也就是作了一步优化问题,这是整个模型的首要关键。 2、随后就是选取或设计合适的算法的时候。 很明显,Dijkstra算法与Floyd算法同样可以使用。 在这里我选取的是Dijkstra算法,并加以自己的修改,来充当这个模型的主要算法。 通过每一步的最优迭代到最终解的最优,这是这个算法的主要思想。 最后,顺理成章求出我们想要的答案了。 比与实际结果作比较,拟合度比较好! 7: 、模型的改进 7-1: 结点的选取问题 模型在选取结点的时候忽略了一个特例: 若起点与终点共线(东、南、西、北方向),那么按照这个模型的原则应该提供特例解。 如: 在共线的情况下 1、改进取点: 以两点连线为中线,往线的两边(包括线上的点)扩散分别寻找第一个点作为结点。 2、改进区域: 以靠近起点的方向选取最近的一个或多个次终点(次终点: 它的下一个结点则是终点),连接所有筛选出来的点构成无向图,则这个便是改进之后的区域。 7-2: 总体结果的优化问题 7-2-1: 条件不足 现该模型只给出了输入起点与终点后求出最短路径的问题。 但没能与实际接轨。 例如XX地图的“最少时间”,“不走高速”等功能选取。 但由于没有详细的道路信息数据,例如: 可以绕小巷更新大街道路信息、人为主观因素选取路线等等实际问题。 因此无法作进一步的研究。 : 7-2-2: 二次优化模型 在选取最短路过程中,若有多解,则系统可以给出一个按照用户输入的其它客观因素信息(道路周边风景、尽量途径较少红绿灯、不喜欢多转弯的道路等等)进行筛选最优的一条,当然其中要涉及的知识就是要掺进各客观因素的权重通过层次分析发的综合筛选,给出在多解的情况下,满足用户需求的唯一一条道路。 8、对本学期课程的总结和建议 总结: 1、本学期的数学课程主要是计算机数学上机实践为主,与上学期的理论课有一定的差别。 本人认为这个理论与实践的结合对学数学是很有帮助的,就譬喻数学中解决图论问题的时候用到: 数-型结合一般好! 2、本学期主要学习数学软件Matlab。 从接触这个软件起,我就觉得在自己的12年数学生涯内真正看到曙光,在数学的世界里沐浴春光般的感觉。 因为这个软件包含了对数学的各种各方面的知识的技术囊括,极大方便了,推动了应用数学的发展,以及各种有关数学项目的开发与发展。 里面不仅有图形结合,处理矩阵的极强能力,而且软件本身就考虑到用户的需求或乐趣,在其中镶嵌了一些智力小游戏,这点上我认为这是一个很不错的软件。 --在这里的基础上,有着我学不完的知识—1、连接处理操作数据库;2、建模用华立的动态与静态图形的形式展现给大众。 真真正正体现到了学海无涯这句话啊! 3、记得有一次做到房贷月利息计算,当时我记得自己就是这样按着书本的公式敲代码,去实现这个功能为目的。 后来我发现了一个同学他把问题化繁为简了,简单几行的代码就把其本质描述出来。 后来我反思这是什么原因? 这一细节我注意到了。 数学不是死的,而是我们习惯地把它默认为死的,就好比喻一条人人走的大路,傍边的草丛里却掩盖了一条风光无限的小田径。 学数学要自然,要有兴趣,因为数学就来自自然! 4、我觉得大学在上课的时候应该把自己的思维放宽到更远,因为我看到了一个这样的现象,老师在课堂上布置任务,当完成了之后有时间,他们便停留在这里,或手机,或聊天。 但他们不曾想过,他们完成的只是海洋中的一滴水而已。 因此我们要不断求进,自我增值才是王道! 5、还有一点就是,大学以来庆幸遇到两位好良师,是他们给了我指引,启发。 在不懂,迷茫的时候给我指点迷津,这默默之中无形给了我很大的动力! 谢谢。 6、感谢老师一直以来的付出。 建议 1、如果上课之前,老师能向同学们展示一点好玩的玩意或有趣的实际问题(前提是关于即将要讲的内容),这样引起睡意绵绵的同学的兴趣,精神起了,或许对他们收听效率会提高! 哈哈 值得延续 1、老师上课比较幽默风趣,对学生课堂上的活跃度是比较好的。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 路径 导航
![提示](https://static.bingdoc.com/images/bang_tan.gif)