619第十三讲 空间分析与查询四.ppt
第十三讲 空间分析与查询(四),中山大学 遥感与地理信息工程系,网络分析,网络数据结构的基本组成部分和属性1、链(Link)网络中流动的管线如街道、河流、水管,其状态属性包括阻力和需求。2、结点(Node)网络中链的结点,如港口、车站等,其状态属性包括阻力和需求等。,结点中的特殊类型障碍(Barrier),禁止网络上流动的点。拐点(Turn),出现在网络中的分割点上,其状态有属性和阻力,如拐弯的时间和限制(如在8点到18点不允许左拐)。中心(Center),是接受或分配资源的位置,如水库、商业中心,电站等,其状态包括资源容量(如总量),阻力限额(中心到链的最大距离或时间)。站点(Stop),在路径选择中资源增减的结点,如库房、车站等,其状态属性有资源需求,如产品数量。,路径分析静态求最佳路径:在给定每条链上的属性后,求最佳路径。N条最佳路径分析:确定起或终点,求代价最小的N条路径,因为在实际中最佳路径的选择只是理想情况,由于种种要素而要选择近似最佳路径。最短路径或最佳耗费路径:确定起点终点和要经过的中间点、中间连线,求最短路径或最佳耗费路径。动态最佳路径分析:实际网络中权值是随权值关系式变化的,可能还会临时出现一些障碍点,需要动态的计算最佳路径。,最小值问题求解如:有数组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),最佳路径求解最佳路径求解有多种不同的方法,其中Dijkstra算法适合于求解某个起点(源点)到网络中的其它各个结点的最佳路径。,Dijkstra算法(1),1、引进一个辅助向量D,它的每个分量Di表示当前所找到的从起点 vm 到每个终点vi的最短路径的长度。假设用带权的邻接矩阵arcs来表示带权有向图,arcsij表示弧 上的权值。若 不连通,则arcsij=。那么Di的初值为:Di=arcsmi viV此外,将已找到的从vm 出发的最短路径的终点的集合记为S,它的初始状态为空集。,Dijkstra算法(2),2、选择 vj 使得Dj=MinDi|viV-SVj就是当前求得的一条从vm出发的最短路径的终点。其中j为这条最短路径的终点,将其加入到终点集合S,令S=Sj,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,Dijkstra算法(4),4、重复操作第二步、第三步共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。,例子,V5,V0,V4,V1,V3,V2,100,60,30,10,10,20,50,5,带权有向图,邻接矩阵,例子(思路),A,Ci,Bi,如图所示,A为所求最短距离的起点,其他Bi,Ci 为终点。我们要求的是一系列最短距离。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序(从小到大)排列。我们把所有顶点分为两类C和B.令A到Bi这些顶点的最短距离不为无穷大。A到Ci这些顶点的最短距离为无穷大。这就说明A到Ci中的点要么不通,要么通过Bi中的点与之连接。,例子(思路),A,Ci,Bi,这样,对于A到Ci中任何一个点的最小距离,我们总可以在Bi中找到一点,使得A到这一点的最小距离小于前一个距离。(因为:A到Ci中的点要么不通,要么通过Bi中的点与之连通。)因此,我们可以先不考虑Ci中的点。,例子(思路),于是,对于右图,我们第一步只考虑下图:,V5,V0,V4,V2,100,30,10,Bi=v2,v4,v5,例子(思路),我们用mindist这个数组来保存由v0到其它顶点的最小距离,这些距离按升序排列。考虑右图:第一步,通过比较,我们知道 mindistancev0v2=mindist0=10,(v0-v2)这是我们求出的第一个最小距离。一旦我们得到v2,我们就可以知道:,例子(思路),V0跟 v2直接连通到的点v3 之间的最小距离不再是无穷大,它应当是mindistancev0v2+disv2v3,这样我们应当把v3放入前面的集合Bi中。(注意:有多少v2直接连通到的点都应当考虑进来。),Bi=v2,v4,v5,v3,例子(思路),第二步,我们把与v2直接连通的点v3考虑进来。dis05=100;dis04=30;dis02=10;dis03=60;除10以外,30是最小的。我们可以证明30是v0到其它顶点除10以外最小的。,例子(思路),不可能存在这样一个点Vn,使得10mindistance0n30.原因如前所述。,V5,V0,V4,V3,V2,100,30,10,50,Vn,Bi,例子(思路),这样我们得到我们的第二个最小距离:Mindistancev0v4=mindist1=30,(v0-v4)接下来,我们把v4与之直接连通的点考虑进来。,V5,V0,V4,V3,V2,100,30,10,50,Bi,例子,以v0为起点,计算它到其它各顶点的最短路径,计算过程中最短路径长度向量D的变化见D0-D4,计算出的各条最短路径见表4-4。,例子,例子,求最短路径的方法,中心选址问题,中心点选址问题中,最佳选址位置的判定标准,是使其所在的顶点与图中其它顶点之间的最大距离达到最小。这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。,中心选址问题的图论描述,设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),中心选址问题的实例,例如,某县要在其所辖的8个乡镇之一修建一个消防站,为8个乡镇服务,要求消防站至最远乡镇的距离达到最小。假设该8个乡镇之间的交通网络被抽象为图4-10所示的无向赋权连通图,权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇,即哪个顶点?,中心选址问题的实例,中心选址问题的实例,首先,用Dijkstra算法计算出每一个顶点vi至其它各顶点vj的最短路径长度dij(i,j=1,2,6),写出距离矩阵:,中心选址问题的实例,其次,求距离矩阵中每行的最大值,即各个顶点的最大服务距离,得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点所在的乡镇即可。,中心选址问题的实例,其次,求距离矩阵中每行的最大值,即各个顶点的最大服务距离,得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点所在的乡镇即可。,另外一种求最短路径的方法,mkij可以理解为从顶点i到顶点j的中间顶点序号小于k的最短路径长度组成的矩阵。(m0ij=mNN),