张家界景区空中缆车模型介绍

HYPERLINK张家界景区空中缆车模型摘要本文将张家界景区各景点铺设索道路线抽象为图论最短路模型，采用最小生成树进行表述。根据张家界景区管理部门的需求，利用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地图一、问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。但时间往往是限制人们旅游一个难题，为了满足旅游者的需要，张家界景区打算造高空浏览缆车，让人们可以在最短的时间内游览更多的景点，现定游览车的起点在张家界国家森林公园，造价为每米10万元，请解决以下问题：1、针对张家界景点地图，自建坐标系，标出各个景点坐标2、设计最佳的缆车运行路线二、问题分析现在的旅游业日益发达，但因时间紧迫，很多人希望找到最佳旅游线路。而旅游线路遇到的最直接的问题是：景点的具体位置。比如张家界景区，里面的景点多达五十个，怎样才能准确找到自己要去景点的位置，已经成为了亟待解决的关键问题。为此，张家界景区决定铺设空中缆车索道，以解决广大游客的时间问题。1、问题一的分析：对于张家界景区里景点的做标问题，首先定位出各景点在地图上的经、纬度；然后运用计算机技术对经、纬度进行处理，再以张家界国家森林公园为新建坐标系原点，以东、北方向为新建坐标系的X、Y轴，新建张家界平面坐标系；经计算机处理，最后给出各景点在新建坐标系中的具体坐标。2、问题二的分析：对于问题二，本文先考虑张家界各景点建空中缆车站的理想化情况，即在张家界景区的51个景点都建一个可供游客来回坐的缆车旅游站台，考虑到雷电，狂风等地理环境因素，使得某些旅游景点是不能能够只考虑空中缆车距离最小等等，建立理想模型2.1；但实际上需要考虑费用、路径、空中缆车站的最佳位置等等各方面因素，在理想状态的基础上，考虑运用最小生成树法及聚类分析等方法，建立实际模型2.2；再对本文建立的模型二进行检验分析。三、模型假设1、假设所有景区的海拔是一样的，不考虑景点间的高度差。2、假设总缆车站台的费用相对于总缆车索道的费用很低，可以不计入张家界建造空中缆车系统的总费用。3、假设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张家界闺门岩-21610张家界天悬白练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张家界各景点以国家森林公园为原点的坐标系图图1.1即为问题一所需求得的张家界景区内各景点的位置所构成的直角坐标系图形。2、问题二的模型建立与求解：2.1、模型一模型2.1是一个理想化的模型，即每个景点都有一个空中缆车站。则根据模型2.1的要求，可以将张家界景区内的51个景点都有空中缆车站问题，转化为求51个景点的最小生成树问题，也就是在一个连通图的赋权网络中，寻找最小权数的支撑树。现给定网络,设为的一个支撑树，令表示的权，则中权最小的支撑树即为的最小生成树。在模型2.1中,表示51个景点之间的最短距离。因为单位长度的建造费用是确定的，所以要求空中缆车各景点的总费用最小，也就是求各景点距离最小的最小生成树，即连通所有景点的权最小的支撑树。根据以上信息，考虑运用Floyd算法，并可用Matlab程序将其实现。Floyd算法基本思想：令表示一个N×N矩阵，它的(i,j)元素是。如果已知图中每条线段的长度，则可以确定矩阵，最终希望得到最短路长度的矩阵。Floyd算法从开始，由计算，然后Floyd算法再由计算。将这个过程重复进行下去，直至由求得为止。计算思路如下，设已知：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作为中间顶点。因为不存在有负长度的回路，所以4)项与5)项中给出的2条路中较短的1条一定是从i到j的最短路，其中只容许前m个顶点即顶点1，2，⋯，m作为中间顶点。4)、1)项和2)项2条路的并。5)、3)项的路。因此，从以上方程可以看出，只需要矩阵的各个元素，就可以计算出矩阵的各个元素；而且，无需参看基本图就可以进行计算。现在，求图中每一对顶点之间最短路的Floyd算法。Floyd算法基本步骤：第1步：将图中各顶点编为1，2，⋯，N。确定矩阵，其中(i,j)元素等于从顶点i到顶点j最短线段的长度(如果有最短线段的话)。如果没有这样的线段，则令，对于i，令，第2步：对m=1，2，⋯，N，依次由的元素确定的元素,应用下列递归公式每当确定一个元素时，就记下它所表示的路。在算法终止时，矩阵的元素(i,j)元素就表示从顶点i到顶点j最短路的长度。注意：对所有的i和m，，矩阵的对角线元素都无需计算，而且，对所有的i=1，2，⋯，n，和。这是因为不存在有负长度的回路，所以在顶点m处起始的任一最短路中，顶点m不是中间点的缘故。因此，在矩阵的计算中，第m行和m列都不需计算。在每一个矩阵中，不在对角线上，也不在第m行和第m列的(N–1)(N-2)个元素需要计算。由以上信息，加上Matlab技术，对模型1.1的51个景点坐标进行处理。第一步：由51个景点的坐标，用Matlab实现任意两点之间的的距离。（程序见附录程序2.1.1）第二步：根据51个景点之间的权重，运用Floyd算法找到缆车索道建构最优路径（程序见附录程序2.1.2），其距离d=454.6550mm，实际距离D=45465.50图2.1.150个景点的最小生成树这一步，将51个空中缆车站坐标进行了处理，得到图2.1.1的权最小的支撑树；因而我们可以得到铺设缆车索道的路线图，即第三步:画出其路线图：图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—137—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算法，但考虑到其他因素，本文还加上了经典算法：聚类分析法。将景区内经典比较密集的景点进行分类，以节省建造空中缆车索道的费用。聚类分析的基本思想：研究的样品（网点）或指标（变量）之间存在程度不同的相似性（亲疏关系——以样品间距离衡量）。于是根据一批样品的多个观测指标，具体找出一些能够度量样品或指标之间相似程度的统计量，以这些统计量为划分类型的依据。把一些相似程度较大的样品（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样品（或指标）又聚合为另一类，直到把所有的样品（或指标）聚合完毕，这就是分类的基本思想。聚类分析法可分三种：直接聚类法、最短距离聚类法和最长距离聚类法，本文所需的是第二中聚类算法思想，并根据所添加的约束条件（景点到搜索点的距离不大于500m）进行适当的改进。聚类分析的基本步骤：计算n个样本两两间的距离{dij}，记D；计算出这n个样板是所在长方形最小区域；搜索出景区满足约束条件的最密集的区域所表示的坐标（i,j）和包含点数k；如果k等于1，转到（5），否者剔除（3）所搜索的区域所包含的点，回（3）；将搜索的（i,j）和未剔除的点看作m个类；画出这m类的位置。由聚类分析基本步骤，得到其算法流程图（图2.2.1）图2.2.1聚类分析算法流程图根据上述聚类算法步骤，利用最小生成树法中的Floyd算法可得到最佳缆车索道线。具体的操作可如下：由于以国家森林公园为旅游的出发点，可以从所有景点中剔除出去，利用聚类分析法对剩余的50个景点进行处理，得到替代两个或两个以上聚点的坐标（表2.2.1表2.2五点聚点（29，30，32，33，34）2625四级聚点（23，26，27，28）1831四点聚（15，16，18，21）3743三点聚（12，13，14）2247三点聚（38，39，40）5850三点聚（46，48，49）7887两点聚（35，36）2014两点聚（22，24）527两点聚（19，20）1237两点聚（7，41）5261两点聚（47，50）8591由聚类后得到的景点与未被搜索到的18个景点坐标相组合，构出30个新的空中缆车站坐标。运用Matlab技术对表2.2.1的数据进行处理，用图片的形式展现，可以得到图2.2.2。图2.2.230个新的空中缆车站坐标聚类后，将得到的30个空中缆车站坐标，运用Floyd算法，找出缆车索道建构最优路径（图2.2.3、程序见附录程序2.2.2）其距离：d=445.0506mm，实际距离D=44505.06m，所需最小费用为S=图2.2.330个空中缆车站形成的最小生成树这一步，将新得到的30个空中缆车站坐标进行了处理，得到图2.2.3的权最小的支撑树；因而我们可以得到铺设缆车索道的路线图，即第三步：画出其线路图；图2.2.430个新缆车站的大致走向表2.2.2聚类后的缆车站坐标序号地名名坐标x坐标y序号地名名坐标x坐标y11-1811516433077223114174456713311951845468944218619511092255-97520五点聚点（29，30，32，33，34）262566216821四级聚点（23，26，27，28）183178245522四点聚（15，16，18，21）374389-196323三点聚（12，13，14）224791005724三点聚（38，39，40）58501011-165025三点聚（46，48，49）78871117184026两点聚（35，36）20141225573627两点聚（22，24）5271331122828两点聚（19，20）123714370029两点聚（7，41）52611542426830两点聚（47，50）8591根据图2.2.4及表2.2.2做出其最优路线表，以便游客查找最佳旅游路线及铺设索道的最优路线。起点国家森林公园1414—26—20—21—13—2714—26—20—21—28—9—10—8—514—26—20—21—28—11—23—2214—26—20—21—28—11—23—7—6—16—1814—26—20—21—28—11—23—7—6—16—4—3—2—114—26—20—21—28—11—23—7—6—16—15—29—17—25—3014—26—20—21—28—11—23—7—6—16—15—29—24—12—19图2.2.4标示出了实际建造缆车索道的大致走向，这个走向是在考虑实际因素的条件下，铺设缆车索道的最短距离，所用费用最小的走向，即为本文所构建的张家界旅游最佳路线。六、模型评价问题一：利用Google地图对张家界51个景点进行定位搜索，可以精确的定位出各个点的经、纬度；但由于各点的经、纬度相差不大，对所给经、纬度标准化处理，得到的景点的相对平面坐标有着较大的系统误差。计算机对这些景点坐标进行数据处理和作图与原图比较，存在细微的差别。问题二：由于建设缆车索道所要考虑的因素有很多，而这些因素有些是难以数据化，譬如地理环境和每个景点的客流量等。本文只能忽略这些因素对张家界旅游管理部门建造缆车索道的影响，相应的构建比较理想的模型环境。在构建最佳路线模型，本文是假设所有景点的海拔时相同的，实际上张家界旅游景点有高山、平地以及湖泊等，它们在二维图上缆车索道建造的长度是不相同的。根据景点坐标运用聚类分析——最小生成树法作出缆车索道图形，聚类分析法可以精确、清晰的分析51个旅游景点的密集程度，保证聚合得每一类聚点都是唯一确定的且满足约束条件。本文的创新点在于对密集程度比较高的景点进行新型聚类处理。一般的聚类分析法对已知的所有点中两个最近点合并一类，看作一个新点，反复查找，层层聚类，直到类数只有一个停止。而本文的聚类相对于一般聚类法多出一个约束条件，也就是旅客所能接受步行距离的最大值为500m。本文对所有可能设置缆站进行迭代搜索，搜寻最密集的区域，进行聚类，看作一类，去除这类所有的缆站，对剩余的缆站再进行迭代搜索，反复迭代，直到搜索到一点归为一类停止，将剩下的一点为一类，通过这种算法可节省张家界旅游管理部门对缆车索道的投资近1亿人民币。七、模型改进针对模型评价的某些缺点与不足，我们可以进行适当的改进，具体方法如下：张家界的所有风景区的人流量和地势是不同的。因此，人步行到各个风景区的最大距离，如到高山、平地以及湖泊可以赋予不同的权重；人流量比较高或地势较平的景区可以赋予相对小点的权重，而比较冷僻或地势比较高的景区可以赋予相对大点的权重。对于实际的景区环境进行实地考察，将一些不适合建缆车的景区当作异常点剔除，一些景区间有着比较大的屏障，可以设它们的距离为无穷大，也就是说它们间不能建缆车索道。人们对张家界旅各游景区的选择：旅游景点的风景好坏对旅客的吸引力有着重要的影响，不同的季节的人流量也略有不同，所以我们可以对每个景点的步行距离的最大值的权重赋多次值进行模拟。具体操作过程为：（1）到各个景区进行实地考察，找出每个景区中的地理异常，并大致对比下每个景区的人流情况。对异常的地理环境进行分析是否能建缆车索道以及对人流量的多少进行。（2）对不能实现缆车索道铺建的景点进行剔除和路线的删减，根据人流量的多少和地势高低赋于不同权重。（3）通过新型的聚类法，聚类合并出满足约束条件的若干个缆站，通过最小生成树法找到需要铺造缆车索道的路线。（4）改变各点权重，反复运算，得到最省钱且满足实用的路线。根据以上步骤，得到改进后的聚类分析流程图（图2.2.5）图2.2.5改进后的聚类算法流程图八、模型的推广与应用最小生成树法和聚类分析法，就是要在一个连通网络中，寻找最枝数的支撑树，即找到最优解。最小生成树法和聚类分析法不仅仅能够在旅游业中可以用到，在许多服务各地的公司中，如燃气公司、送电公司、有多个分公司的大型公司等的作用尤其明显。聚类分析的主要作用是：1、不但可以了解个别变量之间的关系的亲疏程度，而且可以了解各个变量组合之间的亲疏程度。2、根据变量的分类结果以及它们之间的关系，可以选择主要变量进行聚类分析。九、参考文献①、谷歌地图②、张威主编，Matlab基础与编程入门【M】,西安电子科技大学出版社，2008年③、刘承平，数学建模方法【M】，北京：高等教育出版社，2002年④、李祥会、张红，基于模糊动态聚类分析的教学质量评估方法研究【M】，四川师范大学学报（自然科学版），2004年1月⑤、叶其孝主编，大学生数学建模竞赛辅导教材【M】，湖南教育出版社，2001年⑥、姜启源、谢金星、叶俊，数学建模（第三版）【M】，北京：高等教育出版社，2003年十、附录表1张家界各景点经纬、度表旅游点经度纬度旅游点经度纬度张家界九天洞29.324645110.119486张家界天书宝匣29.325169110.433884张家界天子山镇29.408273110.447962张家界南天门29.401321110.499115张家界将军岩29.311474110.045457张家界劈山救母29.319182109.790057张家界天子峰29.408049110.448389张家界定海神针29.318839109.790057张家界龙泉飞瀑29.321570109.971429张家界天桥29.371405110.466156张家界鸳鸯瀑布29.311324109.945518张家界花果山29.351058110.442810张家界空中田园29.309275109.930712张家界护鞭神鹰29.317472109.775251张家界观光电梯29.310301109.897399张家界金鞭岩29.234882110.463409张家界天波府29.324987109.930712张家界闺门岩29.319183109.753042张家界天悬白练29.318497109.904802张家界夫妻岩29.321571109.738237张家界空中走廊29.323962109.878892张家界国家森林公园29.316788110.434914张家界天下第一桥29.318839109.878892张家界张良墓29.308592109.867787张家界迷魂台29.319182109.867787张家界水绕四门29.221101110.465469张家界五女拜师29.319181109.856683张家界神兵聚会29.307909109.889996张家界后花园29.342678110.433197张家界老屋场29.307909109.923309张家界重欢树29.313032109.845579张家界采药老人29.304152109.945518张家界跳鱼潭29.342678110.467529张家界仙人桥29.373948110.467701张家界紫草潭29.315423109.841877张家界雄狮回首29.299372109.956622张家界天桥遗墩29.322254109.841877张家界天台129.379028110.493487张家界黑枞脑29.321571109.834474张家界天台229.379034110.493453张家界千里相会29.366618110.455172张家界仙女献花29.296638110.019547张家界九重仙阁29.348664110.419464张家界御笔峰29.407301110.490875张家界黄狮寨29.333701110.432167张家界西海29.407301110.494995张家界鸳鸯泉29.323962109.790057张家界贺龙公园29.371106110.514565张家界双龟探溪29.299029109.827071张家界鹰窝寨29.281268109.775251张家界南天一柱29.327264110.435944程序2.1.1x=[-18 3 11 21 -9 21 27 24 -19 0 -16 -1 -2 -2 9 16 18 9 -11 -9 11 -24 -5 -16 57 -6 -9 -8 -2 -1 12 5 3 2 -2 -9 0 29 35 31 31 42 30 56 46 53 64 55 50 56 109];y=[115 114 95 86 75 68 64 55 63 57 50 50 47 44 45 41 40 40 40 38 39 28 34 26 36 29 27 28 26 28 28 25 22 21 16 12 0 47 45 53 62 68 77 71 89 83 88 90 86 92 22];d(:,:)=zeros(51,51);fori=1:51;forj=1:51;d(i,j)=sqrt((x(j)-x(i)).^2+(y(j)-y(i)).^2);endenda程序2.1.2aa(find(a==0))=M;result=[];p=1;tb=2:length(a);whilelength(result)~=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d);j=p(jb(1));k=tb(kb(1));result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];endresultd=sum(result(3,:))输出结果：1.00002.00003.00004.000043.00006.00007.000041.00002.00003.00004.000043.00006.00007.000041.000040.000021.024020.616013.454012.728012.72807.21114.47219.000038.000039.00008.000040.000041.000038.000017.000016.000040.000038.000040.00008.000042.000017.000016.000021.00006.32466.32467.28017.280112.530013.03802.23615.385221.000018.000015.000014.000013.000012.000014.000020.000018.000015.000014.000013.000012.000010.000020.000019.00002.23615.000011.04503.00003.16237.07119.21952.828420.000023.000026.000028.000026.000029.000029.000033.000023.000026.000028.000027.000029.000034.000030.000033.00005.65695.09902.23611.41425.00002.23616.40311.414233.000034.000027.000032.000035.000024.000019.000011.000032.000035.000024.000031.000036.000022.000011.00009.00003.60566.40317.07117.61588.06238.246211.180013.342042.000044.000046.000049.000049.000048.000050.000036.000044.000046.000049.000045.000048.000050.000047.000037.000014.318012.36904.24265.00006.40312.23618.944315.00009.000039.000025.00005.000025.000051.000015.620023.770053.8520d=454.6550程序2.2.1p=5;%500mxx=[-18 3 11 21 -9 21 24 -19 0 -16 18 -9 -24 57 12 42 30 56 46 109];yy=[115 114 95 86 75 68 55 63 57 50 40 38 28 36 28 68 77 71 89 22];%所有点的坐标x=xx+25;y=yy+1;x1=minmax(x);%x轴的最值y1=minmax(y);%y轴的最值d(:,:,:)=zeros(size(x'),x1(2)-x1(1)+1,y1(2)-y1(1)+1);%定义变量(k,i,j)fori=x1(1):x1(2)forj=y1(1):y1(2)fork=1:size(x')if(j-y(k)).^2+(i-x(k)).^2<p^2;%约束条件d(k,i,j)=1;%0-1规划endendendendd1=sum(d);z1=d1(:,:,1);z2=d1(:,:,2);z3=d1(:,:,3);...z115=d1(:,:,115);z116=d1(:,:,116);X=[z1',z2',z3',z4',z5',z6',z7',z8',z9',z10',z11',z12',z13',z14',z15',z16',z17',z18',z19',z20',z21',z22',z23',z24',z25',z26',z27',z28',z29',z30',z31',z32',z33',z34',z35',z36',z37',z38',z39',z40',z41',z42',z43',z44',z45',z46',z47',z48',z49',z50',z51',z52',z53',z54',z55',z56',z57',z58',z59',z60',z61',z62',z63',z64',z65',z66',z67',z68',z69',z70',z71',z72',z73',z74',z75',z76',z77',z78',z79',z80',z81',z82',z83',z84',z85',z86',z87',z88',z89',z90',z91',z92',z93',z94',z95',z96',z97',z98',z99',z100',z101',z102',z103',z104',z105',z106',z107',z108',z109',z110',z111',z112',z113',z114',z115',z116'];bb=X(:);n=max(bb)[cc,dd]=find(X==n);cc(1)dd(1)ddd=zeros(1,size(x'));fork=1:size(x')if(dd(1)-y(k)).^2+(cc(1)-x(k)).^2<p^2;ddd(k)=1;endendddd程序2.2.2clearclcx=[-18 3 11 21 -9 21 24 -19 0 -16 18 57 12 0 42 30 56 46 109 26 18 37 22 58 78 20 5 12 52 85];y=[115 114 95 86 75 68 55 63 57 50 40 36 28 0 68 77 71 89 22 25 31 43 47 50 87 14 27 37 61 91];d(:,:)=zeros(30,30);fori=1:30;forj=1:30;d(i,j)=sqrt((x(j)-x(i)).^2+(y(j)-y(i)).^2);endendaa(find(a==0))=M;result=[];p=1;tb=2:length(a);whilelength(result)~=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d);j=p(jb(1));k=tb(kb(1));result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];endresultd=sum(result(3,:))输出结果：1.00002.00003.00004.000016.00006.00007.000023.00002.00003.00004.000016.00006.00007.000023.000011.000021.024020.616013.454012.728012.728013.34208.24628.062311.000028.000021.000013.000021.000020.000016.000015.000028.000021.000013.000027.000020.000026.000015.000029.00006.70828.48536.70827.071110.000012.530015.000012.207029.000029.000024.000023.000016.000028.00009.000010.000017.000024.000012.000022.000018.00009.000010.00008.000010.770012.530014.036015.524020.000023.324017.464013.34208.000026.000017.000025.000012.00005.000014.000025.000030.000019.000015.620024.413027.20308.062353.8520d=445.0506

附录资料：不需要的可以自行删除怎样提高电脑系统运行速度WindowsXP的启动速度比Windows2000要快30%左右，但相对于Windows98仍然要慢了不少，不过，我们可以通过优化设置，来大大提高WindowsXP的启动速度。加快系统启动速度主要有以下方法：尽量减少系统在启动时加载的程序与服务；对磁盘及CPU等硬件进行优化设置；修改默认设置，减少启动等待时间等。这些方法大部分既可减少系统启动的时间，又可以节省系统资源，加快电脑运行速度。1.加快系统启动速度WindowsXP的启动速度比Windows2000要快30%左右，但相对于Windows98仍然要慢了不少，不过，我们可以通过优化设置，来大大提高WindowsXP的启动速度。加快系统启动速度主要有以下方法：尽量减少系统在启动时加载的程序与服务；对磁盘及CPU等硬件进行优化设置；修改默认设置，减少启动等待时间等。这些方法大部分既可减少系统启动的时间，又可以节省系统资源，加快电脑运行速度。(1)MsconfigWindowsXP的启动速度在系统安装初期还比较快，但随着安装的软件不断增多，系统的启动速度会越来越慢，这是由于许多软件把自己加在了启动程序中，这样开机即需运行，大大降低了启动速度，而且也占用了大量的系统资源。对于这样一些程序，我们可以通过系统配置实用程序Msconfig将它们从启动组中排除出去。选择“开始”菜单中的“运行”命令，在“运行”对话框中键入“Msconfig”，回车后会弹出“系统配置实用程序”对话框，选择其中的“启动”选项卡(如图1)，该选项卡中列出了系统启动时加载的项目及来源，仔细查看每个项目是否需要自动加载，否则清除项目前的复选框，加载的项目越少，启动的速度就越快。设置完成后需要重新启动方能生效。(2)BootvisBootvis是微软提供的一个启动优化工具，可提高WindowsXP的启动速度。用BootVis提升WindowsXP的启动速度必须按照正确的顺序进行操作，否则将不会起到提速的效果。其正确的操作方法如下：启动Bootvis，从其主窗口(如图2)中选择“工具”菜单下的“选项”命令，在“符号路径”处键入Bootvis的安装路径，如“C:\ProgramFiles\Bootvis”，单击“保存”退出。从“跟踪”菜单中选择“下次引导”命令，会弹出“重复跟踪”对话框，单击“确定”按钮，BootVis将引导WindowsXP重新启动，默认的重新启动时间是10秒。系统重新启动后，BootVis自动开始运行并记录启动进程，生成启动进程的相关BIN文件，并把这个记录文件自动命名为TRACE_BOOT_1_1。程序记录完启动进程文件后，会重新启动BootVis主界面，在“文件”菜单中选择刚刚生成的启动进程文件“TRACE_BOOT_1_1”。窗口中即会出现“CPU>使用”、“磁盘I/O”、“磁盘使用”、“驱动程序延迟”等几项具体图例供我们分析，不过最好还是让BootVis程序来自动进行分析：从“跟踪”菜单中选择“系统优化”命令，程序会再次重新启动计算机，并分析启动进程文件，从而使计算机启动得更快。(3)禁用多余的服务WindowsXP在启动时会有众多程序或服务被调入到系统的内存中，它们往往用来控制Windows系统的硬件设备、内存、文件管理或者其他重要的系统功能。但这些服务有很多对我们用途不大甚至根本没有用，它们的存在会占用内存和系统资源，所以应该将它们禁用，这样最多可以节省70MB的内存空间，系统速度自然也会有很大的提高。选择“开始”菜单中的“运行”命令，在“运行”对话框键入“services.msc”后回车，即可打开“服务”窗口。窗口的服务列表中列出了系统提供的所有服务的名称、状态及启动类型。要修改某个服务，可从列表双击它，会弹出它的属性对话框(如图3)，你可从“常规”选项卡对服务进行修改，通过单击“启动”、“停止”、“暂停”、“恢复”四个按钮来修改服务的状态，并可从“启动类型”下拉列表中修改启动类型，启动类型有“自动”、“手动”、“已禁用”三种。如果要禁止某个服务在启动自动加载，可将其启动类型改为“已禁用”。WindowsXP提供的所有服务有36个默认是自动启动的，实际上，其中只有8个是必须保留的(见下表)，其他的则可根据自己的需要进行设置，每种服务的作用在软件中有提示。4)修改注册表来减少预读取，减少进度条等待时间WindowsXP在启动过程中会出现一个进度条，我们可以通过修改注册表，让进度条只跑一圈就进入登录画面。选择“开始”菜单中的“运行”命令，在“运行”对话框键入“regedit”命令后回车，即可启动注册表编辑器，在注册表中找HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SessionManager\MemoryManagement\PrefetchParameters，选择其下的EnablePrefetcher键，把它的键值改为“1”即可。(5)减少开机磁盘扫描等待时间当Windows日志中记录有非正常关机、死机引起的重新启动，系统就会自动在启动的时候运行磁盘扫描程序。在默认情况下，扫描每个分区前会等待10秒钟，如果每个分区都要等上10秒才能开始进行扫描，再加上扫描本身需要的时间，会耗费相当长的时间才能完成启动过程。对于这种情况我们可以设置取消磁盘扫描的等待时间，甚至禁止对某个磁盘分区进行扫描。选择“开始→运行”，在运行对话框中键入“chkntfs/t:0”，即可将磁盘扫描等待时间设置为0；如果要在计算机启动时忽略扫描某个分区，比如C盘，可以输入“chkntfs/xc:”命令；如果要恢复对C盘的扫描，可使用“chkntfs/dc:”命令，即可还原所有chkntfs默认设置，除了自动文件检查的倒计时之外。2.提高系统运行速度提升系统运行速度的思路与加快启动的速度类似：尽量优化软硬件设置，减轻系统负担。以下是一些常用的优化手段。(1)设置处理器二级缓存容量WindowsXP无法自动检测处理器的二级缓存容量，需要我们自己在注册表中手动设置，首先打开注册表，找到“HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SessionManager\MemoryManagement\”，选择其下的“SecondLevelDataCache”，根据自己所用的处理器设置即可，例如PIIICoppermine/P4Willamette是“256”，AthlonXP是“384”，P4Northwood是“512”。(2)提升系统缓存同样也是在“HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SessionManager\MemoryManagement\”位置，把其下的“LargeSystemCache”键值从0改为1，WindowsXP就会把除了4M之外的系统内存全部分配到文件系统缓存中，这样XP的内核能够在内存中运行，大大提高系统速度。通常来说，该优化会使系统性能得到相当的提升，但也有可能会使某些应用程序性能降低。需要注意的是必须有256M以上的内存，激活LargeSystemCache才可起到正面的作用，否则不要轻易改动它。(3)改进输入/输出性能这个优化能够提升系统进行大容量文件传输时的性能，不过这只对服务器用户才有实在意义。我们可在中新建一个DWORD(双字节值)键值，命名为IOPageLockLimit。一般情况下把数据设置8~16MB之间性能最好，要记住这个值是用字节来计算的，例如你要分配10MB的话，就是10×?1024×1024，也就是10485760。这里的优化也需要你的机器拥有大于256M的内存。(4)禁用内存页面调度在正常情况下，XP会把内存中的片断写入硬盘，我们可以阻止它这样做，让数据保留在内存中，从而提升系统性能。在注册表中找到“HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SessionManager\MemoryManagement\”下的“DisablePagingExecutive”键，把它的值从0改为1即可禁止内存页面调度了。(5)关闭自动重新启动功能当WindowsXP遇到严重问题时便会突然重新开机，可从注册表将此功能取消。打开注册表编辑器，找到“HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\CrashControl\”将AutoReboot键的Dword值更改为0，重新启动后设置即可生效。(6)改变视觉效果WindowsXP在默认情况下启用了几乎所有的视觉效果，如淡入淡出、在菜单下显示阴影。这些视觉效果虽然漂亮，但对系统性能会有一定的影响，有时甚至造成应用软件在运行时出现停顿。一般情况下建议少用或者取消这些视觉效果。选择桌面上“我的电脑”图标，单击鼠标右键，在弹出的快捷菜单中选择“属性”命令，打开“系统属性”对话框。选择“高级”选项卡，在其中的“性能”栏中单击“设置”按钮，会弹出“性能选项”对话框(如图4)，可选择“调整为最佳性能”单选框来关闭所有的视觉效果，也可选择“自定义”然后选择自己需要的视觉效果。(7)合理设置页面虚拟内存同样也是在“性能选项”对话框中，选择“高级”选项卡，在其中的“虚拟内存”栏中单击“更改”按钮，接下来选择虚拟内存为“自定义大小”，然后设置其数值。一般情况下，把虚拟设为不小于256M，不大于382M比较合适，而且最大值和最小值最好一样。(8)修改外观方案WindowsXP默认的外观方案虽然漂亮，但对系统资源的占用也多，可将其改为经典外观以获得更好的性能。在桌面空白位置单击鼠标右键，从弹出的快捷菜单中选择“属性”命令，会打开“显示属性”对话框，在“主题”选项卡选择主题为“Windows经典”，即可将外观修改为更为经济的Windows经典外观。(9)取消XP对ZIP支持WindowsXP在默认情况下打开了对zip文件支持，这要占用一定的系统资源，可选择“开始→运行”，在“运行”对话框中键入“regsvr32/uzipfldr.dll”，回车确认即可取消XP对ZIP解压缩的支持，从而节省系统资源。(10)关闭Dr.WatsonDr.Watson是WindowsXP的一个崩溃分析工具，它会在应用程序崩溃的时候自动弹出，并且在默认情况下，它会将与出错有关的内存保存为DUMP文件以供程序员分析。不过，记录DUMP文件对普通用户则毫无帮助，反而会带来很大的不便：由于Dr.Watson在应用程序崩溃时会对内存进行DUMP记录，将出现长时间硬盘读写操作，要很长一断时间程序才能关闭，并且DUMP文件还会占用大量磁盘空间。要关闭Dr.Watson可打开注册表编辑器，找到“HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsNT\CurrentVersion\AeDebug”分支，双击其下的Auto键值名称，将其“数值数据”改为0，最后按F5刷新使设置生效，这样就取消它的运行了。同样，我们可以把所有具备调试功能的选项取消，比如蓝屏时出现的memory.dmp，可在“系统属性”对话框中选择“高级”选项卡，单击“启动和故障恢复”栏中的“设置”按钮，并在弹出的“启动和故障恢复”对话框中选择“写入调试信息”为“无”(如图5)。(11)启动硬盘/光驱DMA模式打开“系统属性”对话框，选择“硬件”选择卡中的“设备管理器”按钮，打开“设备管理器”窗口，在设备列表中选择“IDEATA/ATAPI控制器”，双击“主要IDE通道”或“次要IDE通过”，在其属性对话框的“高级设置”选项卡中检查DMA模式是否已启动，一般来说如果设备支持，系统就会自动打开DMA功能，如果没有打开可将“传输模式”设为“DMA(若可用)”。(12)关掉不用的设备WindowsXP总是尽可能为电脑的所有设备安装驱动程序并进行管理，这不仅会减慢系统启动的速度，同时也造成了系统资源的大量占用。针对这一情况，你可在设备管理器中，将PCMCIA卡、调制解调器、红外线设备、打印机端口(LPT1)或者串口(COM1)等不常用的设备停用，方法是双击要停用的设备，在其属性对话框中的“常规”选项卡中选择“不要使用这个设备(停用)”。在重新启动设置即可生效，当需要使用这些设备时再从设备管理器中启用它们。(13)关闭错误报告当应用程序出错时，会弹出发送错误报告的窗口，其实这样的错误报告对普通用户而言几乎没有任何意义，关闭它是明智的选择。在“系统属性”对话框中选择“高级”选项卡，单击“错误报告”按钮，在弹出的“错误汇报”对话框中，选择“禁用错误汇报”单选项，最后单击“确定”即可。另外我们也可以从组策略中关闭错误报告：从“运行”中键入“gpedit.msc”，运行“组策略编辑器”，展开“计算机配置→管理模板→系统→错误报告功能”，双击右边设置栏中的“报告错误”，在弹出的“属性”对话框中选择“已禁用”单选框即可将“报告错误”禁用。(14)关闭自动更新“自动更新”功能对许多WindowsXP用户而言并不是必需的，可将其关闭以节省系统资源。在“我的电脑”上单击鼠标右键，从快捷菜单中选择“属性”命令，选择“系统属性”对话框中的“自动更新”选项卡，勾选“关闭自动更新，我将手动更新计算机”单选框，单击“确定”按钮即可关闭自动更新功能。如果在“服务”已经将“AutomaticUpdates”服务关闭，“系统属性”对话框中的“自动更新”选项卡就不能进行任何设置了。(15)去掉菜单延迟去掉菜单弹出时的延迟，可以在一定程度上加快XP。要修改的键值位置在“HKEY_CURRENT_USER\ControlPanel\Desktop”。修改其下的“MenuShowDelay”键，把默认的400修改为0，按F5刷新注册表即可生效。(16)清除预读文件WindowsXP的预读设置虽然可以提高系统速度，但是使用一段时间后，预读文件夹里的文件数量会变得相当庞大，导致系统搜索花费的时间变长。而且有些应用程序会产生死链接文件，更加重了系统搜索的负担。所以，应该定期删除这些预读文件。预计文件存放在WindowsXP系统文件夹的Prefetch文件夹中，该文件夹下的所有文件均可删除。(17)关闭自动播放功能在WindowsXP中，当往光驱中放入光盘或将USB硬盘接上电脑时，系统都会自动将光驱或USB硬盘扫描一遍，同时提示你是否播放里面的图片、视频、音乐等文件，如果是拥有多个分区的大容量的USB硬盘，扫描会耗费很长的时间，而且你得多次手动关闭提示窗口，非常麻烦。这种情况下我们可以将WindowsXP的自动播放功能关闭。运行“组策略”程序。在组策略窗口左边栏中，打开“计算机配置”，选择“管理模板”下的“系统”，然后在右边的配置栏中找到“关闭自动播放”并双击它，会弹出“关闭自动播放属性”对话框。在其中“设置”选项卡中选择“已启用”，“关闭自动播放”下拉列表中选择“所有驱动器”(如图6)。这样以后就不用担心WindowsXP的“自动播放”功能带来的麻烦了。如果你只是想禁止系统扫描某个驱动器(如USB硬盘)上的文件，可采用下面的方法。先连上你的USB硬盘，让系统将它识别出来。然后打开“我的电脑”，选择USB硬盘上的某个分区，按鼠标右键，会弹出磁盘属性窗口，选取“自动播放”选项卡，将所有内容的类型都选择为不执行操作。如果USB硬盘有多个分区，对所有分区都进行同样的操作，这样当你将USB驱动器拔掉再重新接上时，系统会将USB硬盘识别出来，而不会反复问你是否播放USB硬盘中的文件了。3.加快关机速度WindowsXP的关机速度要慢于启动速度，特别有些任务还需要手工结束，更加延缓了关机速度。因此，要加快关机速度，首先要开启WindowsXP的自动结束任务功能。具体步骤是：从注册表中找到“HKEY_CURRENT_USER\ControlPanel\Desktop”，把“AutoEndTasks”的键值设置为1即可。然后再修改“HungAppTimeout”为“4000(或更小)”(预设为5000)，该键值同样也在“HKEY_CURRENT_USER\ControlPanel\Desktop”下；最后一步再找到“HKEY_LOCAL_MACHINE\System\CurrentControlSet\Control\”，同样把WaitToKillServiceTimeout设置为“4000”；通过这样设置后的关机速度明显要加快了。够全面吧~~◆二、硬件优化设置◆1、关掉不用的设备

在设备管理器中，将PCMCIA卡、调制解调器、红外线设备、打印机端口(LPT1)或者串口(COM1)等不常用的设备停用，在要停用设备属性对话框中的“常规”选项卡中选择“不要使用这个设备(停用)”。当需要使用这些设备时再从设备管理器中启用它们。◆2、内存性能优化

WindowsXP中有几个选项可以优化内存性能，它们全都在注册表下面位置：HKEY_LOCAL_MACHINESYSTEMCurrentControlSetControlSession

ManagerMemory

Management

1）禁用内存页面调度（Paging

Executive）

XP会把内存中的片断写入硬盘，我们可以阻止它这样做，让数据保留在内存中，从而提升系统性能。256M以上内存才使用这个设置。把“DisablePagingExecutive”的值从0改为1就可以禁止内存页面调度了。

2）提升系统缓存

必须有256M以上的内存，才激活它。把LargeSystemCache键值从0改为1，一般来说，这项优化会使系统性能得到相当的提升，但也有可能会使某些应用程序性能降低。

3）输入/输出性能

内存大于256M才更改这里的值，这个优化只对server（服务器）用户才有实在意义，它能够提升系统进行大容量文件传输时的性能。建一个DWORD（双字节值）键值，命名为IOPageLockLimit，数值设8M－16M字节之间性能最好，具体设什么值，可试试哪个值可获得最佳性能。这个值是用字节来计算的，比如你要分配12M，就是12×1024×1024，也就是12582912。◆3、启动硬盘/光驱DMA模式

“系统属性”－“硬件”－“设备管理器”，在设备列表中选择“IDE

ATA/ATAPI控制器”，双击“主要

IDE

通道”或“次要

IDE

通道”，在其属性对话框的“高级设置”选项卡中检查DMA模式是否已启动，一般来说如果设备支持，系统就会自动打开DMA功能，如果没有打开可将“传输模式”设为“DMA（若可用）”（在BIOS里也应该要先设为支持DMA）。

◆4、关闭自动播放功能

运行“组策略”程序,在组策略窗口左边栏中打开“计算机配置”，选择“管理模板”下的“系统”，然后在右边的配置栏中找到“关闭自动播放”并双击它，会弹出“关闭自动播放属性”对话框，在其中“设置”选项卡中选择“已启用”，“关闭自动播放”下拉列表中选择“所有驱动器”。

◆5、设置二级缓存容量

WindowsXP有时无法自动检测处理器的二级缓存容量，需要我们手动设置。运行注册表编辑器，找到HKCU_LOCAL_MACHINESYSTEMCurrentControlSetControlSession

ManagerMemory

Management,选择Dword值SecondLevelDataCache（如果没有就