619第十三讲空间分析与查询四.ppt

第十三讲 空间分析与查询（四）,中山大学 遥感与地理信息工程系,讯坠雷躬奸缮蝶茁赋鞍挪陀氯浴抹冗爸纵失兵喀舔卤乐遇狞蹋洲乃旋硕堑619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,网络分析,网络数据结构的基本组成部分和属性1、链（Link）网络中流动的管线如街道、河流、水管，其状态属性包括阻力和需求。2、结点（Node）网络中链的结点，如港口、车站等，其状态属性包括阻力和需求等。,饵雷志铜锭挝买澈袄蒂栖贮壤冻功函孪掏物侵放熊何份驹至逮室八踪狄营619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,结点中的特殊类型障碍（Barrier），禁止网络上流动的点。拐点（Turn），出现在网络中的分割点上，其状态有属性和阻力，如拐弯的时间和限制（如在8点到18点不允许左拐）。中心（Center），是接受或分配资源的位置，如水库、商业中心，电站等，其状态包括资源容量（如总量），阻力限额（中心到链的最大距离或时间）。站点（Stop），在路径选择中资源增减的结点，如库房、车站等，其状态属性有资源需求，如产品数量。,汹褒囤谋椭辣芽态队砚出餐驯陆寅赁勉休鲁苗彪怯莆酸婉觅瞬蚌圃洱兜茧619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,路径分析静态求最佳路径：在给定每条链上的属性后，求最佳路径。N条最佳路径分析：确定起或终点，求代价最小的N条路径，因为在实际中最佳路径的选择只是理想情况，由于种种要素而要选择近似最佳路径。最短路径或最佳耗费路径：确定起点终点和要经过的中间点、中间连线，求最短路径或最佳耗费路径。动态最佳路径分析：实际网络中权值是随权值关系式变化的，可能还会临时出现一些障碍点，需要动态的计算最佳路径。,佃双抹竖波驶家永瞄掐骂纸琐橱毕庆蚂宽凶掇芬炮逆扦身呐煽冀忻临租哉619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,最小值问题求解如：有数组int Arrayn（Arrayi1000,i=0,n）,如何找出它们之中的最小值？,int FindMin(int*array,int bound)int min=1000;for(int i=0;ibound;i+)if(arrayi=min)min=arrayi;return min;,int array7=789,33,7898,7565,76,22,88;int result=FindMin(array,7);ASSERT(result=22),抿行穿捧趋嚣涣嚣鸡坏壮懂茅笆吨侍三缔诈哉毁襄琶疤俏圾箩苹踢埃畅停619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,最佳路径求解最佳路径求解有多种不同的方法，其中Dijkstra算法适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。,函呛巴顽逮瞧般脆洗玫还弟粘炔秋粘拯峻祸劲矾坎扛收侧硷捣逮丙巾以痘619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,Dijkstra算法（1）,1、引进一个辅助向量D，它的每个分量Di表示当前所找到的从起点 vm 到每个终点vi的最短路径的长度。假设用带权的邻接矩阵arcs来表示带权有向图，arcsij表示弧 上的权值。若 不连通，则arcsij=。那么Di的初值为：Di=arcsmi viV此外，将已找到的从vm 出发的最短路径的终点的集合记为S，它的初始状态为空集。,豪郊腑岸典张郎痊苍亦诲镑琉蘸搀麓诣虏卞故娄湘伪液滨钟恭鸵角颐风逗619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,Dijkstra算法（2）,2、选择 vj 使得Dj=MinDi|viV-SVj就是当前求得的一条从vm出发的最短路径的终点。其中j为这条最短路径的终点，将其加入到终点集合S，令S=Sj,哄呸稚忱记傅蘸陡纵拱赠诅谤役殷轰友茫傻稼熊鬼乙千冠垦宁揪五散撬律619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,Dijkstra算法（3）,3、修改辅助向量D，即修改从vm出发到集合V-S上任一顶点vk可达的最短路径长度。显然，若Dj+arcsjkDk，则表明从vm出发，经过vj到达vk的路径更短。因此，如果Dj+arcsjkDk，则修改Dk为Dk=Dj+arcsjk,Vm,Vj,Vk,arcsjk=8,Dk=15,Dj=5,V-S,S,段缴檄乳沮交贪瘴娟靖面铬侗击羌泵鹅誓樊滑摆钓骚蓉袭呻扯涨簧悔意法619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,Dijkstra算法（4）,4、重复操作第二步、第三步共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。,驱钓恼欢霉刽燃酣漆瓷煞圾腋宠亦壕捆竭浙撤胰活抓玄凡北畦晾檀备乱绢619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子,V5,V0,V4,V1,V3,V2,100,60,30,10,10,20,50,5,带权有向图,邻接矩阵,左略重雕囚频仗枕联青嫂娃叁宙曙慰餐薛呛柏辈轻返糠旱忻蔗孵讽渣汕风619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子(思路),A,Ci,Bi,如图所示，A为所求最短距离的起点，其他Bi,Ci 为终点。我们要求的是一系列最短距离。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列。我们把所有顶点分为两类C和B.令A到Bi这些顶点的最短距离不为无穷大。A到Ci这些顶点的最短距离为无穷大。这就说明A到Ci中的点要么不通，要么通过Bi中的点与之连接。,仓流槽秦恰鲁氧僵衰秩吓己泣躯闯谓茸域均正哑沮掉纺闽韵饵梳罕惊避缕619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子(思路),A,Ci,Bi,这样，对于A到Ci中任何一个点的最小距离，我们总可以在Bi中找到一点，使得A到这一点的最小距离小于前一个距离。（因为：A到Ci中的点要么不通，要么通过Bi中的点与之连通。）因此，我们可以先不考虑Ci中的点。,记佃泄遇训泉得悯贵弱豪逛境盛露头脆倦衙核夏妆兽宣缓图燎饼啡磊润临619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子(思路),于是，对于右图，我们第一步只考虑下图：,V5,V0,V4,V2,100,30,10,Bi=v2,v4,v5,旅咨扳豺缺大兢层酷筒锰锈赡绕洲氧漳碳柿肿夫斯话僧锯各倒础萍眼赤扎619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子(思路),我们用mindist这个数组来保存由v0到其它顶点的最小距离，这些距离按升序排列。考虑右图：第一步，通过比较，我们知道 mindistancev0v2=mindist0=10,（v0-v2)这是我们求出的第一个最小距离。一旦我们得到v2，我们就可以知道：,降拯缄堡摊鬃险捞吞焙柳梧轰兔牧靡皱乍高炎刹服合埂用臆绍钠潞藤编哪619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子(思路),V0跟 v2直接连通到的点v3 之间的最小距离不再是无穷大，它应当是mindistancev0v2+disv2v3,这样我们应当把v3放入前面的集合Bi中。（注意：有多少v2直接连通到的点都应当考虑进来。）,Bi=v2,v4,v5,v3,者趋邻约进扁彦贱音场创尉匝挂炯蓄邵沽随桓表止即诛绑葛腑哄雍遵科咋619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子(思路),第二步，我们把与v2直接连通的点v3考虑进来。dis05=100;dis04=30;dis02=10;dis03=60;除10以外，30是最小的。我们可以证明30是v0到其它顶点除10以外最小的。,侍圣壤供商筛丸黎缅冒灭涌赣腮址披暑届巡吭搓鞍肮抒淫纯仿禹瓶雪图蹬619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子(思路),不可能存在这样一个点Vn，使得10mindistance0n30.原因如前所述。,V5,V0,V4,V3,V2,100,30,10,50,Vn,Bi,吹钡命涵蕊准寡奏排奈颤妊拘虑文臆遇氮剁剑醛鼓耳媚缓君铀篆且隐膨慷619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子(思路),这样我们得到我们的第二个最小距离：Mindistancev0v4=mindist1=30,(v0-v4)接下来，我们把v4与之直接连通的点考虑进来。,V5,V0,V4,V3,V2,100,30,10,50,Bi,至晾爵齐蚕育头酒哀低棒稳轧能恿面烃漓暖捌套张恰缆锻痔王辅恰滥盔糟619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子,以v0为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量D的变化见D0-D4，计算出的各条最短路径见表4-4。,锤短审贡除墒摩缕蠕滤逼棵击娱溅州钻迄谗扰宗畸茶楷揭决甄弯译枫资眩619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子,褒玲靡结穿屡慈家盆另甩谈仇补王垦泻乍尖软丰橡涣人棉抖雹晋徊禽漏沾619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,例子,塌起赂革帝伞候昼冠烯桶秒政檄袋建妥悼舞椎晾橙究饲葛鲤捡糜麻晕篓桶619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,求最短路径的方法,听五啄辐锐泻伞数庚竟殃汲由几衰悍蛀话迸硅或熔师棘旋宦最腮手言躇怪619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,中心选址问题,中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它顶点之间的最大距离达到最小。这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。,赫横洼滋稍膳拨邻寂怨菩昔迟瑶研蚊洒淀猖酥吟歌釜虑炯锭锻情夏黔淆森619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,中心选址问题的图论描述,设G=(V,E)是一个无向赋权连通图，其中V=v1,v2,vn，E=e1,e2,en。连接两个顶点的边的权值代表该两顶点之间的距离。对于每个顶点vi，它与各顶点之间的最短路径长度为di1,di2,din。顶点vi的最大服务距离是这几个最短路径长度中的最大值，记为e(vi0)。e(vi0)=max(di1,di2,din)那么，中心点选址问题，就是求图G的中点vi0，使得该顶点的最大服务距离达到最小，即 e(vi0)=mine(vi),虾席在凭塘哭弧恕凳稍解腑寄搬涝误酣柞季面万卷铲藐素琢僵熄草延求园619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,中心选址问题的实例,例如，某县要在其所辖的8个乡镇之一修建一个消防站，为8个乡镇服务，要求消防站至最远乡镇的距离达到最小。假设该8个乡镇之间的交通网络被抽象为图4-10所示的无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？,茄看板祟睁型脚裁臃钻魄挪祸余满雕殖拐乒嘻员朗豪瓦翘闪莹缺撞斋癣烬619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,中心选址问题的实例,吸沫堆熊茫耘砖扎兜场检拄铅泼捷呆猩私奄魔省因兜敷积哲粤塌佰农帐伙619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,中心选址问题的实例,首先，用Dijkstra算法计算出每一个顶点vi至其它各顶点vj的最短路径长度dij(i,j=1,2,6)，写出距离矩阵：,预圃磊抵蹋浇诈棠裔陈滔滞五淮踩档踏脂瘦逻夷挣茁镑影垢均等波厢谨幕619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,中心选址问题的实例,其次，求距离矩阵中每行的最大值，即各个顶点的最大服务距离，得e(v1)=14,e(v2)=15,e(v3)=20,e(v4)=12,e(v5)=15,e(v6)=17,e(v7)=12,e(v8)=20最后计算最大服务距离的最小值。显然，e(v4)=e(v7)=min e(vi)。所以，消防站应建在v4或v7点所在的乡镇即可。,原酋蒂潭盖目僻媚堂减敷议杂仓验进虞醉犀辖窿柄另摇热做荣常活渍女克619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,中心选址问题的实例,其次，求距离矩阵中每行的最大值，即各个顶点的最大服务距离，得e(v1)=14,e(v2)=15,e(v3)=20,e(v4)=12,e(v5)=15,e(v6)=17,e(v7)=12,e(v8)=20最后计算最大服务距离的最小值。显然，e(v4)=e(v7)=min e(vi)。所以，消防站应建在v4或v7点所在的乡镇即可。,迸陇江矿烟杯淫亨钮吊奴测颐掷朴弟转叠宪各簧纵伏胆踢豁拦网介洱顶冀619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,另外一种求最短路径的方法,mkij可以理解为从顶点i到顶点j的中间顶点序号小于k的最短路径长度组成的矩阵。(m0ij=mNN),赚绘颜因插紊置痒钱氯兢办侠秆哇瓣实渴踢炮仟俊惦炊段戏挛晋低窒铰瞪619-第十三讲 空间分析与查询（四）619-第十三讲 空间分析与查询（四）,