基于prim算法的陕西省旅游景点线路规划

叶美丽

（商洛学院数学与计算机应用学院，陕西 商洛 726000）

1 引言

旅游线路的设计是旅游者和旅行社都十分关注的问题，好的旅游线路设计，不仅可以使游客尽享优美风光，而且使游客的抱怨值降到最低。科学设计旅游线路是旅行社的需要，也是一个地区旅游业发展的需要。旅游景区是一个旅游目的地系统中的重要吸引物，在地理位置上具有不可移动的性质，因而，在旅游景区的位置已定的情况下，谋求最短旅游线路，不仅可以减少旅游者的生理疲劳，而且可以相对增加游玩时间，提高旅游效率，也可使旅游公司降低成本。本文将采用prim算法来研究陕西省著名旅游景区间最短旅游线路的构建。

2 实证分析

2.1 陕西省旅游景区概述

陕西简称陕或秦，位于我国内陆腹地，黄河中游，是中国毗邻省市区最多的省份。陕西省旅游景点众多，周、秦、汉、唐这些中国古代的辉煌时期给陕西留下了丰厚的人文遗产，黄土高原、秦岭巴山的自然风光也令人陶醉。陕西全省南北长约870 km，东西宽200～500 km，土地面积 20.58万 km2，占全国土地面积的2.1%。北山和秦岭把陕西分为三大自然区：北部是陕北高原，南部是秦巴山区，中部是关中平原，。陕西境内主要河流有黄河、渭河、汉江、嘉陵江等。因而，陕西省的古文化资源非常丰富，旅游景区众多，其中世界遗产景点2个，世界地质公园1个，国家5A景区7个和国家风景名胜区3个，以西安火车站A为起点（见表 1）。

表1 陕西省著名旅游景区统计

图是一种非线性结构，在工程、数学、计算机等方面有广泛的用途。图由两个集合V和E组成，其中，V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，通常情况下，将图G中的顶点集和边集分别记为V（G）和E（G）。将陕西省的旅游景区作为图中的顶点，那么连接景区之间的交通线路即为图中的边。游客在陕西省进行旅游活动时，一般以西安火车站作为旅游起点，故将西安火车站看作是图中的一个顶点。基于以上特点，整个图可以看作是有向连通图。

2.2 引入最小生成树

图1 旅游路线规划图

对于连通网络 G=（V，E），边是带权的（在此处，边是连接景区之间的交通线路，权是该交通线路的长度，即景区之间的距离），因而G的生成树的各边也是带权的，我们把生成树各边的权值总和称为生成树的权，并把权最小的生成树称为G的最小生成树（Minimum Spanning Tree）。最小生成树是数据结构中的一种思想，它应用于图论中有向连通图、无向连通图、网络等，生成树是对连通图所做的一种遍历，最小生成树是对连通网络所做的一种特殊遍历，除在数据结构中的应用之外，现实生活中有许多重要用途。在旅游线路的设计中使用此方法，构造旅游线路的最短路径。

2.3 构建连通图

2.3.1 构建邻接矩阵。假定，在同等路径长度的道路选择上，首选高速公路和国道，最坏状态下，选择省级公路。测得有道路连接的各个景区之间的最小距离值，以公里为单位，其中，各旅游景区之间的距离值如表2。

表2 陕西省及各旅游景区间距离值

2.3.2 构建连通图。将陕西省的各个著名景区和西安火车站为起点均抽象化为顶点，顶点之间的道路抽象化为连接两个顶点之间的边，将图1和矩阵构造成连通图G14=(V，E)，其中各景点形成的顶点集合为：V(G)={A，B，C，D，E，F，G，H，I，J，K，M，N}，边的 集 合为 ：E(G)={(A，B)，(A，D)，(A，J)，(A，L)，(A，K)，(A，M)，(B，F)，(B，H)，(B，J)，(B，K)，(C，G)，(C，I)，(C，M)，(D，L)，(D，M)，(D，N)，(E，F)，(F，H)，(F，J)，(G，M)，(H，I)，(I，M)，(J，N)，(K，L)，(K，N)，(L，N)}，其中 ，采用抽象分析法，假定各个顶点之间的边长不代表各景区之间的距离值，得到如下连通图G14（图2）。

图2 连通图

2.4 采用prim算法，求最短旅游线路

2.4.1 最小生成树。在构造最小生成树算法中有多种算法，其中，大多数构造算法都利用了最小生成树的MST性质。在此，采用prim算法，利用最小生成树的MST性质来构造网络G14的最小生成树 T14=（U，TE）。初始，U=Φ，TE=Φ。游客到陕西进行旅游活动时，首先要到达西安火车站，将其作为旅游起点，因此，首先从集合V中取顶点A将生成树T14置为一个仅有一个结点A的树，U={u0}，U是V的真子集，，然后在所有的一个端点在T中，另一个端点不在T的边中，找一条权最小的边（u，v），并把该条边（u，v）和不在T中的顶点v并入到T的边集和顶点集中。如此进行下去，直到把所有顶点都并入T中。最后得到最小生成树T14，如图3。

图3 最小生成树T14

2.4.2 求得最短旅游线路。陕西省到达各个旅游景区的最短旅游线路图（图4），即若选择西安火车站作为旅游的起点和终点， 那么旅游线路遵循 A，M，G，C，I，H，E，F，J，N，D，L，K，B，A 才是最短路径。 也就是说西安火车站-太白山-天台山-丝绸之路-法门寺佛文化-黄帝陵-黄河壶口瀑布-合阳洽川-华山-金丝峡-终南山-大雁塔-大唐芙蓉园-华清池-秦始皇陵及兵马俑-西安火车站，是最短旅游线路。

图4 最短旅游线路图

3 结语

求最短旅游线路的问题，也是求耗费时间最短的问题，在旅游线路设计模型方面，通过构建最小生成树问题，求得从起地出发，游历其余各个景区的路线，然后回到终点。在一次难得的外出旅游时机中，在有限的时间内游览更多的旅游景区是游客的诉求，最短旅游线路的设计不仅可以使旅途最短，提高游客时间利用率，减少旅途劳顿，而且能够使自驾车游客的旅游路线更加有序，使游客的旅游过程更加完美。