基于java的多目的地路径规划.pptx

指导教师：卢小峰,基于java的多目的地路径规划系统的设计与实现,班级：1301015学生：高金金学号第一部分：系统的背景及意义第二部分：多目的地导航算法第三部分：导航的实现第四部分：总结与展望,论文的结构和主要内容,背景：随着科技，经济的高速发展，导航成为了人们生活中不可或缺的一部分。常见的有：面向驾车线路的车载导航，基于地铁用户的地铁地图导航和基于游客的旅行地图导航等。可以说几乎每个人的智能手机里都有至少一款导航软件，导航软件为人们的生活提供了很大便利，同时也在很大程度上缓解了日渐严重的交通拥塞问题。无论是基于何种出行方式，都可以借助导航软件规划出一条最省事，最经济的路线。,系统的背景及意义,意义：针对目前市面上的这些导航软件都有的一个共同的缺陷，只能规划两地之间的路线，不能进行多目的地的导航。因此本文提出了多目的地路径规划的需求，并针对用户从一地出发途径多地这一特定问题，通过对几种旅行商算法的分析，提出将最临近算法嵌套到Dijkstra算法上的双标号最临近算法。多目的地路径规划对于游客去多地旅游、商家送外卖等都有很重要的意义，因此这是一个很值得深入研究的课题。,系统的背景及意义,研究框架,研究的展开思路,分析和研究用于本系统的最合适的算法,算法代码的实现,将算法代码在android上进行展示,双标号最临近算法,双标号最临近算法,双标号最临近算法,旅行商问题,Dijkstra算法,多目的地路径规划,最临近算法,旅行商问题及算法,旅行商问题：从某城市出发，经过其他各个城市一次且仅一次，然后回到出发点。,最临近算法,最临近算法：总是优先前往与当前所在的点最临近的点，直到走完所有的节点，最后得到的路径近似等于最短路径，要求任意两点之间的距离是确定的。,最短路径算法,最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。Dijkstra算法能得出最短路径的最优解，下面对Dijkstra算法进行详细介绍。,Dijkstra(迪杰斯特拉)算法,核心思想：通过逐步标定到达目的节点路径长度的方法来求解最短的路径。图解：,G,F,E,C,B,A,H,1,4,6,2,2,5,VS,6,1,2,3,ABHGCEF,双标号最临近算法,核心思想：使用最临近法的核心思想，对节点进行宽度优先搜索，并像Dijkstra算法那样对图中的节点进行标号。图解：,G,F,E,C,B,A,H,1,4,6,2,2,5,VS,6,1,2,3,ABHGCE,算法代码的思路及实现,节点的属性,name,节点名称,IsClient,目的地boolean值,isMarked,节点是否已经处理,path,最短路径长度,算法代码的思路及实现,调用Dijkstra算法找下一个节点,若节点是目的节点，将该节点加入集合，num减1,num为目的节点个数不为0时,距离矩阵,本文中使用距离矩阵来描述各个地点之间的距离，用于程序对其数据的调用。由于具体程序中的距离矩阵数据较多，不能再次展示，下面采用一个简单的示例来描述。,Android实现,Android界面,SVG地图,输入出发点,输入目的地,点击查询,输出路径,绘制矢量地图,对西安电子科技大学老校区的地图进行模拟，用AutoCAD工具进行绘制SVG地图。,Android上的实现,在Android上展示给用户的界面如下，用户可以输入一个出发点和多个目的地，点击查询，即可规划出到达多个目的地的最短路径。,Android上的展示,总结与展望,总结：本课题的论文题目是基于Java的多目的地路径规划，指的是从某地出发途经多个目的地，且仅经过每个目的地一次，所走的路程最短。完成这项功能必须考虑的是：（1）图中的所有点之间的路径，即两两之间路径；（2）计算两个地点之间的最短路径；（3）走完所有的目的地点的最短路径；（4）在Android界面上如何进行人机交互。展望：（1）本课题研究的是多目的地路径规划，考虑旅行商问题的情况，但同时有和旅行商问题有所区别，旅行商问题最后旅客又回到了出发点，但是本文中并没有实现最后回到出发点