网络分析模型ppt课件

网络模型,一、概述网络模型的典型的例子就是研究交通，包括陆上、海上及航空线路，以及通过管线与隧道分析水、汽油及电力的流动。在考虑交通问题时，讲两点之间的直线距离是没有意义的。因为，对于交通运输而言，两点之间的传输并不是沿着两点之间的直线进行的，一切都只能是在交通运输网中的特定路径上进行。因此，两点间的距离表现为两点之间路径的长度。因为两点之间的相关路径可能有许多条。因此以最短路径的长度来描述网络上两点之间的距离。,网络模型,网络是用于实现资源的运输和信息的交流的相互联接的线性特征。网络模型是对现实世界网络的抽象。在模型中，网络由链(Link)、结点(Node)、站点(Stop)、中心(Center)和转向点(Turn)组成。建立一个好的网络模型的关键是清楚地认识现实网络的各种特性与以网络模型的要素(Link,Node,Stop,Center,Turn)表示的特性的关系。,网络模型,二、网络组成要素（1）链(Link)网络的Link构成了网络模型的框架。Link表示用于实现运输和交流的相互联接的线性实体。它可用于表示现实世界网络中的运输网络的高速公路、铁路，和电网中的传输线和水文网络中的河流。其状态属性包括阻力和需求。（2）结点(Node)Node指Link的起止点。Link总是在Node处相交。Node可以用来表示道路网络中道路交叉点、河网中的河流交汇点。（3）站点(Stops)Stop指在某个流路上经过的位置。它代表现实世界中邮路系统中的邮件接收点、或高速公路网中所经过的城市。,网络模型,（4）中心(Center)Center指网络中一些离散位置，它们可以提供资源。Center可以代表现实世界中的资源分发中心、购物中心、学校、机场等。其状态属性包括资源容量，如总的资源量；阻力限额，如中心与链之间的最大距离或时间限制。（5）转向点(Turn)Turn代表了从一个Link到另一个Link的过渡。与其它的网络要素不同，Turn在网络模型中并不用于模拟现实世界中的实体，而是代表Link与Link之间的过渡关系。,网络模型,3.常用的网络模型（1）网络跟踪(Trace)网络用于研究网络中资源和信息的流向，这就是网络跟踪的过程。在水文应用中，网络跟踪可用于跟踪污染物从污染源开始，沿溪流向下游扩散的过程。在电网应用中，可以根据不同开关的开与关的状态，确定电力的流向。网络跟踪中涉及的一个重要概念是“连通”(Connectivity)，这定义了网络中弧段与弧段的连接方式，也决定了资源与信息在网络中流动时的走向。,网络模型,（2）路径选择(PathFinding)在远距离送货、物资派发、急救服务和邮递等服务中，经常需要在一次行程中同时访问多个站点(收货方、邮件主人、物资储备站等)，如何寻找到一个最短和最经济的路径，保证访问到所有站点，同时最快最省地完成一次行程，这是很多机构经常遇到的问题。在这类分析中，最经济的行车路线隐藏在道路网络中，道路网络的不同弧段(网络模型中的Link)有不同的影响物流通过的因素(网格模型中的Impedance:阻抗)，路径选择分析必须充分考虑到这些因素，在保证遍历需要访问的站点(在网络模型中的STOP)的同时，为用户寻找出一条最经济(时间或费用)的运行路径。,网络模型,（3）资源分配(ALLOCATE)反映现实世界网络中资源的供需关系模型。“供(Supply)”代表一定数据的资源或货物，它们位于被称之为“CENTER”的设施中。“需(Demand)”指对资源的利用。Allocate分析就是在空间中的一个或多个点的资源分配的过程。为了实现供需关系，在网络中必然存在资源的运输和流动。资源要么由供方送到需方，要么由需方到供方处索取。,网络模型,（4）地址编码与匹配(GeoCoding)利用人们习惯的地址(街道门牌号)信息确定它在地图上的确切位置的技术，称为地址编码与匹配。客户名单、事故报告、报警中所使用的定位信息多数是按人们习惯的街道门牌号等文字形式提供的，经常在地图上需要迅速定位，例如110接警后，需要迅速定位求救地点，然后才可以采取进一步措施(例如寻求最优路径前往救助)。,网络模型,Geocoding是基于空间定位技术的一种编码方法，它提供了一种把描述成地址的地理位置信息转换成可以被用于GIS系统的地理坐标的方式。通过对现有的信息系统的数据资源进行分析可以发现：非空间数据资源都有具体的发生地，这也是非空间数据资源与空间数据发生联系的一个关键环节。利用地理编码技术可以在地理空间参考范围中确定数据资源的位置，建立空间信息与非空间信息之间的联系，实现在各种地址空间范围(即行政区，人口普查区，街道)内进行信息的整合。,网络模型,（5）选址和分区(Location-Allocation)分析Location-allocation分析是决定一个或多个服务设施的最优位置的过程，它的定位力求保证服务设施可以以最经济有效的方式为它所服务的人群提供服务。在此分析中，既有定位过程，也有资源分配过程。常用来解决的实际问题包括：1）加油站位置的选择；2）急救服务站位置的选择：救火、医疗急救；3）学校的选址。,网络模型,（6）空间相互作用和引力模型用于理解和预测某点发生的活动和人、资源及信息的流动。两点间发生多大程度的相互作用与两点的性质以及发生相互作用的消耗或费用有关。通常情况下两点间距离越近，发生相互作用的可能性越大。解决的实际问题包括：1)为什么物资总是向沿海地区流动；2)为什么某一区域的人们总是去特定的商场购物；3)从家到电影院超过多长时间后，就不会选择去这个电影院看电影了。,图的搜索策略,盲目搜索（不考虑权重）广度优先搜索：以同层邻近节点依次扩展节点，逐层进行，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。深度优先搜索：首先扩展最新产生（即最深的）节点。分支有界搜索：每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层。,图的搜索策略,启发式搜索是深度优先的改进，搜索时不是任取一个分支，而是根据一些启发式信息，选择最佳的一个分支或几个分支往下搜索（考虑权重）。,推销员问题,定义对于给定一个平面初始集，给定一个起始点和终止点，寻找一条路径，该路径通过所有数据点且每个数据点只通过一次，同时位于这两个起始点和终止点间的路径的长度最短。推销员要不重复地经过所有的推销点，且又要使所走的路程最短。例子：对不规则的空间分布，建立基于点集的Y坐标的一个路径。建立初始集根据Y序，将排列其后的点插入到初始集中，原则：插入后路径增加的长度为最小迭代，遵循同样的插入原则。,第一步：P11,P4第二步：P9,P11,P4,插入原则：插入后路径增加的长度为最小以此类推,Dijkstra算法,它属于单源最短路径问题，可给出从某指定结点到图中其它所有结点之间的最短路径。Dijkstra算法所采用的一致代价搜索在人工智能中称为贪心搜索策略，是初级的启发性搜索策略。在赋权有向图中，从起点Vs出发最先达到且路径最短的结点，一定是所有与Vs相邻且弧长最小的点，记为Vs的第一短路径点V1，如果V1就是目标点Ve，问题求解结束，否则继续求第二短路径点，取min与Vs相邻的除V1之外的最短路点，由Vs到V1到与V1邻接的长度最小的一条弧段所到达的点，记为V2。如果V2Ve，退出，否则继续求从Vs出发的第三、第四最短路径点，直到VnVe。,Dijkstra算法,开始，Xx0,然后每一步向X中加入一个顶点，加入x的条件是已知从x0到x的最短路径的路程，以及在这个路程中位于x之前的顶点。当所有从x0可达的顶点都加入到X中时，运算结束。,第一步：初始化X=X0=V1M=V2,V3,V4,V5,V6DIS=0,10,3,0,6,PRED=1,1,1,1,1,1第二步：在M中，V1到V3的路程最近，故X=X+V3=V1,V3M=M-V3=V2,V4,V5,V6DIS=0,7,3,0,5,PRED=1,3,1,1,3,1,Dijkstra算法,Dijkstra算法,第三步：在M中，V1到V5的路程最近X=X+V5=V1,V3,V5M=M-V5=V2,V4,V6DIS=0,5,3,0,5,6,PRED=1,3,1,1,3,1第四步：在M中，V1到V2的路程最近X=X+V2=V1,V3,V5,V2M=M-V6=V4,V6DIS=0,5,3,5,6,PRED=1,5,1,1,3,5第五步：在M中，V1到V6的路程比V1到V4的路程近X=X+V6=V1,V3,V5,V2,V6M=M-V6=V4DIS=0,5,3,5,6,PRED=1,5,1,1,3,5第六步：仅剩V4,计算结束PREDi=j:从x0到Vi的最短路径经过Vj，且Vj是此路径上Vi的前一个顶点。PRED6=5;PRED5=3;PRED3=1;,A*算法,算法原理：建立在典型的Dijkstra算法基础之上的启发式搜索算法，创新之处在于选择下一个被搜索的节点时引入了已知的路网信息，特别是目标点信息，对当前节点距终点的距离进行评估，作为评价该节点属于最优路径节点可能性的评价指标。这样就可以优先搜索可能性较大的节点，从而提高搜索过程的效率。,A*算法,其估价函数表示为：f(n)=g(n)+h(n)其中，f(n)是估价函数，g(n)是起点到结点n的最短路径值，h(n)是结点n到目标点的最短路径的启发值。对当前节点的评估方法有许多，如方向、距离或其他指标，甚至各种指标综合应用。评估原则：评估值与实际值越接近，则评估函数就越好。H（n）需要满足一个约束条件：不能大于节点到终点的实际最短距离。,存在问题：常规的路径规划模型中所使用的标准比较单一。理论上最优的算法不一定在实践中最优。,结果及偏好分析标准的感知,路径搜索策略分析层次策略:人们趋向于在主干道上行驶。方向策略:人们在实际环境中找路是有一定方向性的，出发前，先确定目的地的大概方向，然后在该方向上搜索相关路径。局部策略:一个人总是首先在距自己最近的周围寻找出路，进而才会考虑更大范围内情况。人们喜欢在熟悉的路径上行驶；,基于道路网络空间层次结构的路径寻找方法,道路网络结构特点最短路径算法和基于知识的方法层次空间推理机制道路网络的空间层次结构基于层次推理和路网知识的路径寻找算法层次算法的扩展,1.道路网络结构特点,道路网络结构特点同一地区的道路网具有不同的尺度；道路网路具有区域性；道路可以按照不同的使用特点分为不同的等级；从现实数据中抽象出来的弧段和结点不能完全脱离空间定位上的地理意义，必须能够反馈现实世界网络的特征；信息丰富、数据量大是地理信息的一般特点。,2.最短路径算法和基于知识的方法,最短路径算法和基于知识的方法最短路径算法,DijkstraA*算法,最优解有效,直接用于路径寻找,计算时间不可接受计算存在浪费解不一定适合人类偏好,基于知识的问题解决方法人类并不是有效的路径寻找者，他们很少能找到最佳的路径除非出行距离很短。人类很擅长使用关于道路网络的启发式知识，即很擅长于使用各种场所的地理知识把整个道路网分离成包含解和不包含解的部分，但是他们不擅长在分离区域内搜索到最佳解。,2.最短路径算法和基于知识的方法,两者相结合的方法基于层次推理和道路网络知识的路径寻找方法，在这个组合方法中，知识用于分离搜索范围而算法用于在缩小了范围的独立区域内搜索最佳解。,2.最短路径算法和基于知识的方法,3.层次空间推理机制,层次空间推理机制分层的思想和方法分层通常定义为两种含义：某机构或系统的组织和结构形式，一般称多级层次结构；人类求解问题的一种分解协调，逐层深入的方法。,层次空间推理层次空间推理是使用层次来细分任务或者空间的一种推理过程。为了形式化的定义层次空间推理，它需要包含以下几个要素：问题空间的层次结构：如何把非层次的结构转换为平衡的层次结构。规则：定义一系列如何在层次结构上进行推理的规则。结果的比较：根据结果的正确性和性能的改善程度进行结果的比较。,3.层次空间推理机制,4.道路网络的空间层次结构,道路网络的空间层次结构道路网络的空间层次结构知识人类把大型的道路网络按照层次划分；主要道路分割了整个道路网络；高层路网的重要特性；层次细节由高到低逐渐增多，高层次是低层次的子集。,分层道路网络的表示（a）典型的城市道路网络模型（b）主要道路层（c）次要道路层把数字道路地图按照道路等级进行层次划分高层次地图和低层次地图；分别对二层次地图数据生成拓扑关系，分别用不同的结构体数组存储；,4.道路网络的空间层次结构,分层道路网络的表示道路网络格网索引高层次地图数据形成自然格网（多边形）；用高层次多边形作为索引格网，分别判断落入每个多边形的低层次道路结点和路段。,4.道路网络的空间层次结构,算法思想层次路径算法的基本步骤如下：在O-grid格网中找到最佳出结点并计算O与该结点间路径；在D-grid格网中找到最佳入结点并计算D与该结点间路径；在高层次路网上计算最佳入、出结点间路径。合并各部分最短路径并输出最终解。,5.基于层次推理和路网知识的路径寻找算法,算法关键技术实现判断高层次路网与自然格网相联系的结点,5.基于层次推理和路网知识的路径寻找算法,局部扩展网络,算法关键技术实现层次算法中入/出结点的确定,5.基于层次推理和路网知识的路径寻找算法,算法关键技术实现启发式结点提升技术选择一个合适的估价函数来删除不必要的路径计算，使其寻找最优路径的搜索方向更快地趋近于终点。a.当路径计算是基于最小行驶距离标准时b.当路径计算时是基于最小行驶时间标准时,5.基于层次推理和路网知识的路径寻找算法,算法分析该方法所需条件条件1：整个道路网络G应该是连通的；条件2：主要道路网络应该是连通的；条件3：在网格中存在一个结点u,它既在主要道路上，也在次要道路上。,5.基于层次推理和路网知识的路径寻找算法,算法分析搜索空间和时间分析Dijkstra算法运行时间为O（n2）n为非层次图中的结点数层次算法的运行时间为O（m2）m指层次路径算法中被访问的结点数mnO（m2）O（n2）,5.基于层次推理和路网知识的路径寻找算法,算法分析搜索结果路径分析O-grid中O到选中的E-node的最短路径；D-grid中D到选中的E-node的最短路径；E-node之间的最短路径。,5.基于层次推理和路网知识的路径寻找算法,1.实例研究,6.层次算法的扩展,层次算法的扩展道路网络的多层次划分为了各层次路段均衡性及充分体现分级的优点，可以使用多个层次道路网络的分区搜索用一定的网格对导航数据所覆盖的区域进行划分分层方法中使用城市分区图来代替相同层次的城市地图大区域的路径寻找,基于描述性知识的路径寻找方法,路径寻找的描述性知识最简单路径寻找算法基于典型事例推理的路径寻找方法,1.路径寻找的描述性知识,路径寻找的描述性知识需要一条容易解释、理解、记忆或者执行路线导航指令的路径。路径寻找过程通常通过最小化当前行驶方向与所计算出的目的地方向间的角度来表现。喜欢在熟悉的路径上行驶驾驶是从以前的经历中不断学习的过程，在某条陌生路径上行驶过，就会变得熟悉。,最简单路径寻找方法基于道路转向的认知研究路径（i1，i2，i3，i6，i9），“从当前你所在的位置往前直走，到路尽头朝右拐”，路径（i1，i2，i5，i8，i9），“从当前你所在的位置往前直走，在第一个交叉口处右拐，然后直走，在第三个交叉口处左拐”,2.最简单路径寻找方法,适合道路转向的数据模型路段作为图的顶点，将允许转向行为作为图的弧，称之为路段链模型,2.最简单路径寻找方法,最简单路径算法权重函数的