搜索
C201117071张家界景区空中缆车模型摘要本文将张家界景区各景点铺设索道路线抽象为图论最短路模型，采用最小生成树进行表述。根据张家界景区管理部门的需求，利用Floyd算法——聚类分析法进行模型的建立和求解，得到问题的最优解。第一问，本文根据Google地图定位出张家界景区51个旅游景点的经、纬度；通过计算机处理，以国家森林公园为原点，东、北为X,Y轴，建立张家界景区直角坐标系（表1.1、图1.1）。第二问，假设在每个景点上都建造缆车站，采用图论中的最小生成树法，得出铺设索道的最优路径（图2.1.1）和最小费用S=454655.0万元。观察到许多景点的距离比较近，可以用一个缆车站来接送这些景点的游客，这个站台就是这些景点的聚点，即可优化传统的聚类分析法，使其满足所给定的约束条件（旅客所能容忍步行最小距离为500m），在这些聚点建造缆车站，采用最小生成树法，得出铺设索道的最优路径（图2.2.2）和最小费用S=445050.6万元。针对上述Floyd算法——聚类分析法模型的优缺点，本文给出了具体的改进，使得更符合实际情况以及节省最多的钱。关键词Floyd算法聚类分析法Google地图C201117072一、问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。但时间往往是限制人们旅游一个难题，为了满足旅游者的需要，张家界景区打算造高空浏览缆车，让人们可以在最短的时间内游览更多的景点，现定游览车的起点在张家界国家森林公园，造价为每米10万元，请解决以下问题：1、针对张家界景点地图，自建坐标系，标出各个景点坐标2、设计最佳的缆车运行路线二、问题分析现在的旅游业日益发达，但因时间紧迫，很多人希望找到最佳旅游线路。而旅游线路遇到的最直接的问题是：景点的具体位置。比如张家界景区，里面的景点多达五十个，怎样才能准确找到自己要去景点的位置，已经成为了亟待解决的关键问题。为此，张家界景区决定铺设空中缆车索道，以解决广大游客的时间问题。1、问题一的分析：对于张家界景区里景点的做标问题，首先定位出各景点在地图上的经、纬度；然后运用计算机技术对经、纬度进行处理，再以张家界国家森林公园为新建坐标系原点，以东、北方向为新建坐标系的X、Y轴，新建张家界平面坐标系；经计算机处理，最后给出各景点在新建坐标系中的具体坐标。2、问题二的分析：对于问题二，本文先考虑张家界各景点建空中缆车站的理想化情况，即在张家界景区的51个景点都建一个可供游客来回坐的缆车旅游站台，考虑到雷电，狂风等地理环境因素，使得某些旅游景点是不能能够只考虑空中缆车距离最小等等，建立理想模型2.1；但实际上需要考虑费用、路径、空中缆车站的最佳位置等等各方面因素，在理想状态的基础上，考虑运用最小生成树法及聚类分析等方法，建立实际模型2.2；再对本文建立的模型二进行检验分析。三、模型假设1、假设所有景区的海拔是一样的，不考虑景点间的高度差。2、假设总缆车站台的费用相对于总缆车索道的费用很低，可以不计入张家界建造空中缆车系统的总费用。C2011170733、假设Google地图所查询的经纬度是可信的。4、假设景区地理环境对缆车索道不产生影响，即所有景区间都能够建立笔直的缆车索道。5、假设旅客所能容忍步行的距离为500m。四、符号约定G：连通网络T：连通网络中的一个支撑树E：连通网络中的点W：支撑树的权重d：地图上的最优路径D：实际距离S：最小费用五、模型建立于求解1、问题一的模型建立与求解：旅游已成为现今人们减轻压力的最直接有效的方法，旅游景点线路的选择,是旅游行业的一项基础性工作，也是旅游爱好者比较关心的问题，那么如何在最短的时间内游览到最多的景点呢？本文以张家界景区为例，建立相应的数学模型，以解决上面提到的问题。根据在网上查找的资料，可以得到张家界景区各景点的经、纬度（附录表1）。运用计算机知识，将附录表1的数据进行处理，可以得到以张家界国家森林公园为原点的平面坐标系（表1.1）。表1.1张家界各景点以国家森林公园为原点的坐标系表序号旅游点X轴Y轴序号旅游点X轴Y轴1张家界九天洞-1811527张家界天书宝匣-9272张家界天子山镇311428张家界南天门-8283张家界将军岩119529张家界劈山救母-2264张家界天子峰218630张家界定海神针-1285张家界龙泉飞瀑-97531张家界天桥12286张家界鸳鸯瀑布216832张家界花果山5257张家界空中田园276433张家界护鞭神鹰3228张家界观光电梯245534张家界金鞭岩2219张家界天波府-196335张家界闺门岩-216C20111707410张家界天悬白练05736张家界夫妻岩-91211张家界空中走廊-165037张家界国家森林公园0012张家界天下第一桥-15038张家界张良墓294713张家界迷魂台-24739张家界水绕四门354514张家界五女拜师-24440张家界神兵聚会315315张家界后花园94541张家界老屋场316216张家界重欢树164142张家界采药老人426817张家界跳鱼潭184043张家界仙人桥307718张家界紫草潭94044张家界雄狮回首567119张家界天桥遗墩-114045张家界天台1468920张家界黑枞脑-93846张家界天台2538321张家界千里相会113947张家界仙女献花648822张家界九重仙阁-242848张家界御笔峰559023张家界黄狮寨-53449张家界西海508624张家界鸳鸯泉-162650张家界贺龙公园569225张家界双龟探溪573651张家界鹰窝寨1092226张家界南天一柱-629为了更加清楚明白的表示各景点的具体位置，本文运用Matlab技术对表1.1的数据进行处理，可以得到图1.1。图1.1张家界各景点以国家森林公园为原点的坐标系图C201117075图1.1即为问题一所需求得的张家界景区内各景点的位置所构成的直角坐标系图形。2、问题二的模型建立与求解：2.1、模型一模型2.1是一个理想化的模型，即每个景点都有一个空中缆车站。则根据模型2.1的要求，可以将张家界景区内的51个景点都有空中缆车站问题，转化为求51个景点的最小生成树问题，也就是在一个连通图的赋权网络中，寻找最小权数的支撑树。现给定网络,,GVEW,设',TVE为G的一个支撑树，令eEWTWe表示T的权，则G中权最小的支撑树即为G的最小生成树。在模型2.1中*minWTWT,表示51个景点之间的最短距离。因为单位长度的建造费用是确定的，所以要求空中缆车各景点的总费用最小，也就是求各景点距离最小的最小生成树，即连通所有景点的权最小的支撑树。根据以上信息，考虑运用Floyd算法，并可用Matlab程序将其实现。Floyd算法基本思想：令mD表示一个N×N矩阵，它的(i,j)元素是mijd。如果已知图中每条线段的长度，则可以确定矩阵0D，最终希望得到最短路长度的矩阵ND。Floyd算法从0D开始，由0D计算1D，然后Floyd算法再由1D计算2D。将这个过程重复进行下去，直至由1ND求得ND为止。计算思路如下，设已知：1)、顶点i到顶点m的最短路，其中只容许前m-1个顶点即1，2，⋯，m-1作为中间顶点。2)、从顶点m到顶点j的最短路，其中只容许前m-1个顶点即1，2，⋯，m-1作为中间顶点。3)、从顶点i到顶点j的最短路，其中只容许前m-1个顶点即1，2，⋯，m-1作为中间顶点。C201117076因为不存在有负长度的回路，所以4)项与5)项中给出的2条路中较短的1条一定是从i到j的最短路，其中只容许前m个顶点即顶点1，2，⋯，m作为中间顶点。4)、1)项和2)项2条路的并。5)、3)项的路。因此，m111ijdmin,mmmimmjijddd从以上方程可以看出，只需要1mD矩阵的各个元素，就可以计算出矩阵mD的各个元素；而且，无需参看基本图就可以进行计算。现在，求图中每一对顶点之间最短路的Floyd算法。Floyd算法基本步骤：第1步：将图中各顶点编为1，2，⋯，N。确定矩阵0D，其中(i,j)元素等于从顶点i到顶点j最短线段的长度(如果有最短线段的话)。如果没有这样的线段，则令0ijd，对于i，令00iid，第2步：对m=1，2，⋯，N，依次由1mD的元素确定mD的元素,应用下列递归公式m111ijdmin,mmmmmjijddd每当确定一个元素时，就记下它所表示的路。在算法终止时，矩阵nD的元素(i,j)元素就表示从顶点i到顶点j最短路的长度。注意：对所有的i和m，miid0，矩阵12nD,D,...,D的对角线元素都无需计算，而且，对所有的i=1，2，⋯，n，1immmimdd和1mimmmidd。这是因为不存在有负长度的回路，所以在顶点m处起始的任一最短路中，顶点m不是中间点的缘故。因此，在矩阵mD的计算中，第m行和m列都不需计算。在每一个矩阵mD中，不在对角线上，也不在第m行和第m列的(N–1)(N-2)个元素需要计算。由以上信息，加上Matlab技术，对模型1.1的51个景点坐标进行处理。第一步：由51个景点的坐标，用Matlab实现任意两点之间的的距离。（程序见附录程序2.1.1）C201117077第二步：根据51个景点之间的权重，运用Floyd算法找到缆车索道建构最优路径（程序见附录程序2.1.2），其距离d=454.6550mm，实际距离D=45465.50m所需最小费用为S=445050.6万元。图2.1.150个景点的最小生成树这一步，将51个空中缆车站坐标进行了处理，得到图2.1.1的权最小的支撑树；因而我们可以得到铺设缆车索道的路线图，即第三步:画出其路线图：C201117078图2.1.250个景点最小生成树的大致走向根据图2.1.2做出其最优路线表，以便游客查找最佳旅游路线及铺设索道的最优路线。起点国家森林公园3737—36—35—34—3—32—3137—36—35—34—33—29—3037—36—35—34—33—29—26—28—27—24—2237—36—35—34—33—29—26—23—20—19—11—9—537—36—35—34—33—29—26—23—20—14—13—12—1037—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—40—837—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—39—25—5137—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—40—41—7—6—43—4—3—2—1C20111707937—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—40—41—42—44—46—49—4537—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—40—41—42—44—46—49—48—50—47图2.1.2标示出了建造理想状态下缆车索道的大致走向，在此状态下铺设缆车索道的最短距离，所用费用最小。2.2、模型二在模型2.1中，本文建立的是一个理想化的模型，但这种理想化模型不适用于实际。因而，在考虑建造空中缆车索道费用最小这个大前提下，本文给出了一个符合实际要求的模型，即模型2.2。模型2.1中，运用了Floyd算法，在这个模型中，仍然考虑运用Floyd算法，但考虑到其他因素，本文还加上了经典算法：聚类分析法。将景区内经典比较密集的景点进行分类，以节省建造空中缆车索道的费用。聚类分析的基本思想：研究的样品（网点）或指标（变量）之间存在程度不同的相似性（亲疏关系——以样品间距离衡量）。于是根据一批样品的多个观测指标，具体找出一些能够度量样品或指标之间相似程度的统计量，以这些统计量为划分类型的依据。把一些相似程度较大的样品（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样品（或指标）又聚合为另一类，