基于距离可达矩阵的自驾游路线优化研究

发布时间：2018-02-15 07:01

本文关键词： 邻接矩阵距离可达矩阵最短路径自驾游路线环路　出处：《东北大学》2012年硕士论文　论文类型：学位论文

【摘要】：改革开放以来,国民经济飞速发展的同时自驾游旅游也悄然发展。自驾游旅行的飞速发展使得自驾游旅游国民经济中作用越来越来重要,自驾游旅行已经成为大众化的旅游形式。在对自驾游旅游研究时,自驾游路线的研究越来越来受到重视,传统的自驾游路线优化只是考虑最短路径和成本最低问题,而现在自驾游路线的优化不再是单纯的考虑最短距离和最小成本,而是充分考虑路线中可能存在的环路问题并对存在环路的自驾游路线进行优化。本文将图论的理论引入自驾游路线优化研究,并介绍了图的基本概念,将自驾游旅游可能经过的景点与路线转化为带权值的有向图中的顶点和边权值,并应用邻接矩阵来存储图,然后从应用图论中最短路径算法研究自驾游路线出发,对几种路径算法进行比较后,提出应用距离可达矩阵方法发现自驾游路线中潜在的环路,并提出距离可达矩阵算法可以灵活应用,并用实际例子证明了距离可达矩阵算法的灵活应用,然后提出路径失效法和顶点失效法来解决自驾游路线中可能存在的环路问题。
[Abstract]:Since the reform and opening up to the outside world, the rapid development of the national economy has been accompanied by the quiet development of self-driving tourism. The rapid development of self-driving tourism has made the role of self-driving tourism in the national economy more and more important. Self-driving travel has become a popular form of tourism. In the study of self-driving tour, more and more attention has been paid to the study of self-driving route. The traditional self-driving route optimization only considers the shortest path and the lowest cost. At present, the optimization of self-driving route is not only to consider the shortest distance and minimum cost, but also to consider the possible loop problem and optimize the self-driving route. In this paper, the theory of graph theory is introduced into the study of route optimization of self-driving tour, and the basic concept of graph is introduced. The scenic spots and routes that the self-driving tour may pass through are transformed into the vertex and edge weight value of the weighted directed graph. Then the shortest path algorithm in graph theory is applied to study the self-driving route. After comparing several path algorithms, the distance reachability matrix method is proposed to find the potential loop in the self-driving route. It is proposed that the distance reachability matrix algorithm can be applied flexibly, and the flexible application of the distance reachable matrix algorithm is proved by practical examples. Then, the path failure method and the vertex failure method are proposed to solve the possible loop problem in the self-driving route.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：O157.5;F592.7

【参考文献】