gis二次开发课件1.ppt

1、网络分析算法,对地理网络（如交通网络）、城市基础设施网络（如各种网线、电力线、电话线、供排水管线等）进行地理分析和模型化，是地理信息系统中网络分析功能的主要目的。网络分析是运筹学模型中的一个基本模型，它的根本目的是研究、筹划一项网络工程如何安排，并使其运行效果最好，如一定资源的最佳分配，从一地到另一地的运输费用最低等。其基本思想则在于人类活动总是趋于按一定目标选择达到最佳效果的空间位置。这类问题在社会经济活动中不胜枚举，因此在地理信息系统中此类问题的研究具有重要意义。,图,图（Graph）是较树更为复杂的数据结构，在图中，结点之间的关系是任意的，图中任意两个数据元素都可能相关。下图给出了图的示

2、例。,图,图的形式化定义为： Graph = (V,R) 其中： V=x|xdataobject R=VR VR=|P(x,y)(x,yV) 图中数据元素称为顶点（Vertex），V是顶点的有穷非空集合；VR 是两个顶点之间的关系的集合，其定义中P(x,y)表示x到y的一条 单向通路；若VR，则表示从x到y的一条弧，此时图 称为有向图（Digraph）；若图中的边没有方向，则此时图称为无 向图。 在图中，如果VR，则x，y互为邻接点。路径（Path） 是一个顶点序列（V1,V2,Vn），其中Vi和Vi+1为邻接点。 图可以有多种存储结构，其中最普通的是采用邻接矩阵，如果两 个结点VR，则矩阵对

3、应元素Ai,j=1，反之，Ai,j=0。,图,无向图的邻接矩阵是对称的，而有向图的邻接矩阵则不一定对称，图中两个图的邻接矩阵如下（其中没有考虑相同点邻接性）：,0,1,网络分析算法,网络数据结构的基本组成部分和属性： 1、链（Link） 网络中流动的管线如街道、河流、水管，其状态属性包括阻力 和需求。 2、结点（Node） 网络中链的结点，如港口、车站等，其状态属性包括阻力和需 求等。,结点中的特殊类型 障碍（Barrier）：禁止网络上流动的点。 拐点（Turn）：出现在网络中的分割点上，其状态有属性和阻 力，如拐弯的时间和限制（如在8点到18点不允许左拐）。 中心（Center）：是接受或

4、分配资源的位置，如水库、商业中 心，电站等，其状态包括资源容量（如总量），阻力限额（中 心到链的最大距离或时间）。 站点（Stop）：在路径选择中资源增减的结点，如库房、车站 等，其状态属性有资源需求，如产品数量。,路径分析 1.静态求最佳路径：在给定每条链上的属性后，求最佳路径。 2.N条最佳路径分析：确定起或终点，求代价最小的N条路径， 因为在实际中最佳路径的选择只是理想情况，由于种种要素而 要选择近似最佳路径。 3.最短路径或最佳耗费路径：确定起点终点和要经过的中间 点、中间连线，求最短路径或最佳耗费路径。 4.动态最佳路径分析：实际网络中权值是随权值关系式变化 的，可能还会临时出现一些

5、障碍点，需要动态的计算最佳路 径。,最小值问题求解 如：有数组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) ,最佳路径求解 最佳路径求解有多种不同的方法，其中

6、Dijkstra算法适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。,Dijkstra算法（1）,1、引进一个辅助向量D，它的每个分量Di表示当前所找到的从起点 vm 到每个终点vi的最短路径的长度。 假设用带权的邻接矩阵arcs来表示带权有向图，arcsij表示弧 上的权值。 若 不连通，则arcsij=。 那么Di的初值为： Di=arcsmi viV 此外，将已找到的从vm 出发的最短路径的终点的集合记为S，它的初始状态为空集。,Dijkstra算法（2）,2、选择 vj 使得 Dj=MinDi | viV-S Vj就是当前求得的一条从vm出发的最短路径的终点。其中j为这条最

7、短路径的终点，将其加入到终点集合S，令 S=Sj,Dijkstra算法（3）,3、修改辅助向量D，即修改从vm出发到集合V-S上任一顶点vk可达的最短路径长度。 显然，若Dj+arcsjkDk，则表明从vm出发，经过vj到达vk的路径更短。因此，如果Dj+arcsjkDk，则修改Dk为 Dk=Dj+arcsjk,Dijkstra算法（4）,4、重复操作第二步、第三步共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。,例子,V5,V0,V4,V1,V3,V2,100,60,30,10,10,20,50,5,带权有向图,邻接矩阵,例子(思路),A,Ci,如图所示，A为所求最

8、短距离的起点，其他Bi, Ci 为终点。 我们要求的是一系列最短距离。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列。 我们把所有顶点分为两类C和B.令A到Bi这些顶点的最短距离不为无穷大。 A到Ci这些顶点的最短距离为无穷大。 这就说明A到Ci中的点要么不通，要么通过Bi中的点与之连接。,例子(思路),A,Ci,Bi,这样，对于A到Ci中任何一个点的最小距离，我们总可以在Bi中找到一点，使得A到这一点的最小距离小于前一个距离。（因为：A到Ci中的点要么不通，要么通过Bi中的点与之连通。 ） 因此，我们可以先不考虑Ci中的点。,例子(思路),于是，对于右图，我

9、们第一步只考虑下图：,V5,V0,V4,V1,V3,V2,100,60,30,10,10,50,5,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放入

10、前面的集合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 ,

11、(v0-v4) 接下来，我们把v4与之直接连通的点考虑进来。,V5,V0,V4,V3,V2,100,30,10,50,Bi,例子：,以v0为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量 D 的变化见 D 0-D 4，计算出的各条最短路径。,例子,V5,V0,V4,V1,V3,100,60,30,10,10,50,5,V2,20,例子,求最短路径的方法,中心选址问题,中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它顶点之间的最大距离达到最小。 这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。,中心选址问题的图论

12、描述,设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个乡镇之间的交通网络被抽象为下图所示的无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？,中心选址问题的实例,首先，用Dijkstra算法计算出每一个顶点vi至其它各顶点v的最短路径长度dij(i, j=1,2,6)，写出距离矩阵：,中心选址问题的实例,其次，求距离矩阵中每行的最大值，即各个顶点的最大服务距离，得 e(v1)=14, e(v2