学海网 文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 最短路径算法及其在路径规划中的应用
免费下载此文档

最短路径算法及其在路径规划中的应用

最短路径算法及其路径规划中的应用

摘要:

这篇文章把徒步运动的路径规划问题转化为求解图中任意两点间的最短路径问题,进而针对此问题介绍了Floyd算法,对该算法的时间花费进行分析,并介绍了在实际问题中如何灵活运用该算法解决路径决策中遇到的问题。

关键词:路径规划、最短路径、决策、Floyd算法

将实际地图的转化为有向图

在策划一次徒步旅行时,设计正确的旅行的线路特别重要,首先我们必须先要得到那个地区的地图,以便进行后续的线路规划。当我们拿到某一地区的地图时,我们可以把地图上的每一条线路用线段表示,用顶点表示地图上的岔路口,即多条线段的交点,这样就形成了一个由点和线段组成的图。我们可以在每条线段上标上数字,表示两点之间的实际距离,或者表示通过这条路径所需的时间。当然,如果两点之间没有线段相连,我们可以认为距离为无穷大,用∞表示。有时候某些线路是单向的,即只能从一个方向到另一个方向,不能逆行。这种情况在具体的路径设计中非常常见,比如,在繁华的都市内会有一些单行道,在山区景点中,常会出现一些上山索道,这些都是单向线路的常见例子。有时候,沿某条线路的两个方向所需的时间不同,这种例子更为常见,比如上山与下山,顺风与逆风等等。对于这两种情况,我们可以在表示路径的线段上加上箭头表示该路径的方向,形成有向图。

比如,在右图所示的有向图中,从点v1直接

到达v2的距离为8,而从v2到v1的距离为3。 从点v1到v0的距离为5,而从v0到v1的距离 为∞。这种带有箭头的有向图,比不带箭头的无

向图能够表示更一般的情形,可以说无向图只是

有向图的一种特殊情况。 如果我们知道任意两点间的最短路径,这对 我们进行路径规划将会有很大的帮助,但当地图 较为复杂时,凭直觉估计最短路径的方法往往不

可靠,这时就必须借助计算机的强大计算能力,寻找最短路径。下面,我们就以这种有向图为工具,来探究寻找最短路径的方法。

最短路径算法及其在路径规划中的应用

第1页

免费下载Word文档免费下载:最短路径算法及其在路径规划中的应用

(下载1-3页,共3页)

我要评论

相关文档

  • 路径规划算法及其应用综述

    因 而从算法本身特点及其应用来研究路径规划智能算法, 对 路径规划技术的发展具有...2) Dijkstra 算法[ 33, 34 ] 是一种典型的最短路径算法, 它 是以起始点...

  • 最短路径算法在旅游线路规划中的应用_以庐山为例_邹时林

    最短路径算法在旅游线路规划中的应用_以庐山为例_邹时林_天文/地理_自然科学_.../ /图的邻接矩阵类型 31 2 旅游景点 知名度权重及等级划分 旅 游线路的设 ...

  • 几种常用的最短路径算法

    几种常用的最短路径算法_计算机软件及应用_IT/计算机_专业资料。简述几种常用的...比方说若路径规划问题较为简单, 可采用 Floyd 算法;若路径规划问题涉及到负权...

  • 最短路径算法在交通咨询系统中的应用

    开发与应用 计算机与信息技术 ·23· 最短路径算法在交通咨询系统中的应用高寒...车辆定位与导航系统中的快 速路径规划算法.北京航空航天大学学报, 2002, (1) ...

  • 路径规划算法及其应用综述_张广林

    路径规划算法及其应用综述_张广林_机械/仪表_工程科技_专业资料。专题、 综述 ·...2) Dijkstra 算法[ 33, 34 ] 是一种典型的最短路径算法, 它 是以起始点...

  • A_算法的改进及其在路径规划中的应用

    A 算法的改进及其在路径规划中的应用史 辉, 曹闻, 朱述龙, 朱宝山 (信息...的运行, 目 前大多数方法是将全部数据读入到内存当中, 然后搜索 * 最短路径...

  • 路径规划算法及其应用综述

    85? 路径规划算法及其应用综述木张广林。胡小梅,柴剑飞,赵磊,俞涛(上海市机械...2)Dijkstra算法m_’是一种典型的最短路径算法,它 是以起始点为中心向外层层...

  • 最短路径规划实验报告

    最短路径规划实验报告_计算机软件及应用_IT/计算机_专业资料。电子科技大学 计算机...这里强调相对就是说在算法过程中 D[i]的值是在不断逼近最终结果但在过程中不...

  • 【论文】免疫算法在路径规划中的应用

    免疫算法在路径规划中的应用_生物学_自然科学_专业资料 暂无评价

站点地图 | 文档上传 | 侵权投诉 | 手机版
新浪认证  诚信网站  绿色网站  可信网站   非经营性网站备案
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.xuehai.net All Rights Reserved.  email
返回顶部