空间分析与查询四

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,网络分析,网络数据结构的基本组成部分和属性,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,，,它的每个分量,D,i,表示当前所找到的从起点,v,m,到每个终点,v,i,的最短路径的长度。,假设用带权的邻接矩阵,arcs,来表示带权有向图，,arcs,i,j,表示弧,上的权值。,若,不连通，则,arcs,i,j,=。,那么,D,i,的初值为：,D,i,=,arcs,m,i,v,i,V,此外，将已找到的从,v,m,出发的最短路径的终点的集合记为,S,，,它的初始状态为空集。,Dijkstra,算法（2）,2、选择,v,j,使得,D,j,=,Min,D,i,|,v,i,V,-,S,V,j,就是当前求得的一条从,v,m,出发的最短路径的终点。其中,j,为这条最短路径的终点，将其加入到终点集合,S,，,令,S,=,S,j,Dijkstra,算法（3）,3、修改辅助向量,D,，,即修改从,v,m,出发到集合,V,-,S,上任一顶点,v,k,可达的最短路径长度。,显然，若,D,j,+,arcs,j,k,D,k,，,则表明从,v,m,出发，经过,v,j,到达,v,k,的路径更短。因此，如果,D,j,+,arcs,j,k,D,k,，,则修改,D,k,为,D,k,=,D,j,+,arcs,j,k,V,m,V,j,V,k,arcs,j,k,=,8,D,k,=,15,D,j,=5,V,-,S,S,Dijkstra,算法（4）,4、重复操作第二步、第三步共,n,-1,次。由此求得从,v,到图上其余各顶点的最短路径是依路径长度递增的序列。,例子,V,5,V,0,V,4,V,1,V,3,V,2,100,60,30,10,10,20,50,5,带权有向图,邻接矩阵,例子(思路,),A,C,i,B,i,如图所示，,A,为所求最短距离的起点，其他,Bi,Ci,为终点。,我们要求的是一系列最短距离。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列。,我们把所有顶点分为两类,C,和,B.,令,A,到,Bi,这些顶点的最短距离不为无穷大。,A,到,Ci,这些顶点的最短距离为无穷大。,这就说明,A,到,Ci,中的点要么不通，要么通过,Bi,中的点与之连接。,例子(思路,),A,C,i,B,i,这样，,对于,A,到,Ci,中任何一个点的最小距离，我们总可以在,Bi,中找到一点，使得,A,到这一点的最小距离小于前一个距离。,（,因为：,A,到,Ci,中的点要么不通，要么通过,Bi,中的点与之连通。,）,因此，我们可以先不考虑,Ci,中的点。,例子(思路,),于是，对于右图，我们第一步只考虑下图：,V,5,V,0,V,4,V,1,V,3,V,2,100,60,30,10,10,50,5,V,5,V,0,V,4,V,2,100,30,10,Bi=v2,v4,v5,例子(思路,),我们用,mindist,这个数组来保存由,v0,到其它顶点的最小距离，这些距离按升序排列。,考虑右图：,第一步，通过比较，我们知道,mindistancev0v2=mindist0=10,（v0-v2),这是我们求出的第一个最小距离。,一旦我们得到,v2，,我们就可以知道：,V,5,V,0,V,4,V,2,100,30,10,例子(思路,),V0,跟,v2,直接连通到的点,v3,之间的最小距离不再是无穷大，它应当是,mindistancev0v2+disv2v3,这样我们应当把,v3,放入前面的集合,Bi,中。,（注意：有多少,v2,直接连通到的点,都应当考虑进来。,）,V,5,V,0,V,4,V,3,V,2,100,30,10,50,Bi=v2,v4,v5,v3,例子(思路,),第二步，我们把与,v2,直接连通的点,v3,考虑进来。,dis05=100;dis04=30;,dis02=10;dis03=60;,除10以外，30是最小的。,我们可以证明30是,v0,到其它顶点除10以外最小的。,V,5,V,0,V,4,V,3,V,2,100,30,10,50,例子(思路,),不可能存在这样一个点,Vn，,使得,10mindistance0n30.,原因如前所述。,V,5,V,0,V,4,V,3,V,2,100,30,10,50,V,n,B,i,例子(思路,),这样我们得到我们的第二个最小距离：,Mindistancev0v4=mindist1=30,(v0-v4),接下来，我们把,v4,与之直接连通的点,考虑进来。,V,5,V,0,V,4,V,3,V,2,100,30,10,50,B,i,例子,以,v,0,为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量,D,的变化见,D,0,-,D,4,，,计算出的各条最短路径见表4-4。,例子,终点,从,v0,到其它各结点的最短路径,v1,v2,10,(,v0,v2),v3,60,(,v0,v2,v3),50,(,v0,v4,v3),v4,30,(,v0,v4),30,(,v0,v4),v5,100,(,v0,v5),100,(,v0,v5),90,(,v0,v4,v5),60,(,v0,v4,v3,v5),vj,v2,v4,v3,v5,例子,起点,终点,最短路径,路径长度,v,0,v,1,无,v,2,(,v,0,v,2,),10,v,3,(,v,0,v,4,v,3,),50,v,4,(,v,0,v,4,),30,v,5,(,v,0,v,4,v,3,v,5,),60,求最短路径的方法,中心选址问题,中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它顶点之间的最大距离达到最小。,这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。,中心选址问题的图论描述,设,G,=(,V,E,),是一个无向赋权连通图，其中,V,=,v,1,v,2,v,n,，,E=,e,1,e,2,e,n,。,连接两个顶点的边的权值代表该两顶点之间的距离。对于每个顶点,v,i,，,它与各顶点之间的最短路径长度为,d,i,1,d,i,2,d,in,。,顶点,v,i,的最大服务距离是这几个最短路径长度中的最大值，记为,e,(,v,i,0,),。,e,(,v,i,0,)=,max,(,d,i,1,d,i,2,d,in,),那么，中心点选址问题，就是求图,G,的中点,v,i,0,，,使得该顶点的最大服务距离达到最小，即,e,(,v,i,0,)=,min,e,(,v,i,),中心选址问题的实例,例如，某县要在其所辖的,8,个乡镇之一修建一个消防站，为,8,个乡镇服务，要求消防站至最远乡镇的距离达到最小。假设该,8,个乡镇之间的交通网络被抽象为图,4-10,所示的无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？,中心选址问题的实例,v6,v8,v1,v7,v5,v4,v2,v3,8,9,3,6,3,2,5,3,7,5,7,中心选址问题的实例,首先，用,Dijkstra,算法计算出每一个顶点,v,i,至其它各顶点,v,j,的最短路径长度,d,ij,(,i,j,=1,2,6),，,写出距离矩阵：,中心选址问题的实例,其次，求距离矩阵中每行的最大值，即各个顶点的最大服务距离，,得,e,(,v,1,)=14,e,(,v,2,)=15,e,(,v,3,)=20,e,(,v,4,)=12,e,(,v,5,)=15,e,(,v,6,)=17,e,(,v,7,)=12,e,(,v,8,)=20,最后计算最大服务距离的最小值。显然，,e,(,v,4,)=,e,(,v,7,)=,min,e,(,v,i,)。,所以，消防站应建在,v,4,或,v,7,点所在的乡镇即可。,中心选址问题的实例,其次，求距离矩阵中每行的最大值，即各个顶点的最大服务距离，,得,e,(,v,1,)=14,e,(,v,2,)=15,e,(,v,3,)=20,e,(,v,4,)=12,e,(,v,5,)=15,e,(,v,6,)=17,e,(,v,7,)=12,e,(,v,8,)=20,最后计算最大服务距离的最小值。显然，,e,(,v,4,)=,e,(,v,7,)=,min,e,(,v,i,)。,所以，消防站应建在,v,4,或,v,7,点所在的乡镇即可。,另外一种求最短路径的方法,m,k,ij,可以理解为从顶点,i,到顶点,j,的中间顶点序号小于,k,的最短路径长度组成的矩阵,。(m,0,ij=mNN),