《网络分析方法在GPS控制网优化设计中的应用.docx》由会员分享，可在线阅读，更多相关《网络分析方法在GPS控制网优化设计中的应用.docx（4页珍藏版）》请在三一文库上搜索。
1、第 28卷第 6期测绘与空间地理信息V o .l 28, N o. 62005年 12月GEOMAT ICS & SPAT IAL IN FORMAT ION TECHN OLOGYD ec. , 2005网络分析方法在 GPS控制网优化设计中的应用贺同江,杨国东(吉林大学地球探测科学与技术学院, 吉林长春 130026)摘 要: 讨论了网络分析方法中的深度优先遍历算法在 GPS 控制网优化设计中资源配置问题中的应用, 并在该算法的基础上, 进行了一定的改进, 提出了并行项目的解决建议, 为网络的资源配置提出了一种新的解决方法。关键词: 网络分析; 优化; 深度优先遍历中图分类号: D 157
2、5; P228. 4文献标识码: B文章编号: 1672- 5867( 2005) 06- 0085- 03Application of Network AnalysisM ethod in GPSControlNetwork OptimalDesignH E Tong jiang, YANG Guo dong( C artog raphy and G IS Eng ineering D epartm ent,Jilin U niversity,Changchun 130026,Ch ina)Abstract: Th is paper d iscussed the deeply optim a
3、 l search spread a lgo rithm o f network ana lys is m ethod and its app lication in the resources configure o f GPS contro l netw ork optim al design.It a lso mprovedi the algor ithm and presented the adv ice to paralle l pro jects.F ina lly,It put forw ard a new me thod to do the resources con figu
4、re o f netw ork.K ey word s: netwo rk ana lysis;optima ;ldeep ly optim al search spread0 引言网络分析是运筹学的一个基本模型, 它的根本目的是研究一项网络工程如何安排, 实现资源在网络上流动和分配的最优化问题, 目前优化资源分配、寻找最佳路径、确定最近的设施、生成旅行方向指示、确定商业服务机构的服务范围等已经广泛地被应用在资源和环境领域。但总体来说, 目前网络分析技术在 GPS控制网优化设计方面的研究成果还不多见。GPS控制网也是一种网络系统, 这决定了网络分析技术在处理与 GPS控制网优化设计有关的问题中
5、也具有潜在的应用价值。本文将探讨网络分析技术在 GPS控制网优化设计中的应用方法。1 问题的提出到目前为止, GPS网的优化大多还仅仅局限于选点与埋石、布网、提高 GPS 网精度等几个方面, 而在优化资源配置、节省时间和经费等方面还是甚少提及, 大多数 GPS 网的观测过程都是要依靠负责人的经验来进行管理。一般来说, 目前所布设的 GPS 网都是分布面积广、点数多、同步环数目较多, 这无疑为 GPS 网观测过程的人员仪器安排制造了相当的难度。以某地四等 GPS控制网 ( 如图 1所示 ) 为例, 其中四等点共 140 个, 高等级三等控制点 10 个, 安排总指挥 1 人, 观测人员 10人,
6、 GPS接收机 10台, 车辆 1部。图 1某地四等 GPS网图F ig. 1The fourth levelGPS control network of a place在观测过程中, 每次在 10 个点上进行同步观测 ( 如图 2所示 ), 10个圆点代表了 10 个待测点, 两点之间的连线代表连接两点的道路 ( 由资料图矢量化而来 ), 无连接的表示无道路直接相连, 只要解决了这 10个点观测前的路线安排问题, 整个 GPS网络的问题也就迎刃而解了。收稿日期: 2005- 04- 15作者简介: 贺同江( 1979- ), 男, 山东省潍坊市人, 吉林大学地球探测科学与技术学院 2003级
7、研究生, 研究方向为地图制图学与地理信息工程。86测绘与空间地理信息2005年图 2同步观测点网例图F ig. 2The illustration of the network bysim ultaneous observation points2 解决原理分析本文所提出的问题, 可以知道, 我们所需要的路线有以下特点:经过图中所有点, 即遍历整个图形;路线是整体连通的, 允许回路。! 图中各边以道路为权, 所求的路径与权相关, 即所求的路径应能做到遍历实现或路径最短。图的遍历也是从某个顶点出发, 沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图算法的基础。由于任一顶点都有可能
8、和其余的顶点相邻接 , 所以在访问了某个顶点之后, 可能沿着某条路径搜索, 又回到该顶点上, 为了避免同一个顶点被访问多次,在遍历过程中必须记下每个已访问过的顶点, 为此设一个辅助数组 V ISITED 0 1 n - 1 , 它的初始值为# false, 一旦访问了该顶点 v 后, 则将 V IS ITED i 置为# true。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。深度优先搜索显然是递归形式的算法简单, 广度优先搜索就无法递归, 它应用于求最短路径比较合适, 故结合实际,我们将采用深度优先搜索的算法, 如图 3、图 4所示, 即为深度优先搜索方
9、法的算法实现过程。图 3深度优先遍历过程Fig. 3The processes of deeply optim al search spread深度优先搜索的思想: 假设给定图 G 的初态是所有顶点均未曾访问过。在 G 中任选一顶点 v 为初始出发点(源点 ), 则深度优先遍历可定义如下: 首先访问出发点 v,图 4深度优先遍历算法流程F ig. 4The flow chart of deeply optima lsearch spread algorithm并将其标记为已访问过; 然后依次从 v出发搜索 v的每个邻接点 w。若 w未曾访问过, 则以 w为新的出发点继续进行深度优先遍历, 直至
10、图中所有和源点 v 有路径相通的顶点 (亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点, 则另选一个尚未访问的顶点作为新的源点重复上述过程, 直至图中所有顶点均已被访问为止。在深度优先搜索过程中, 设 x 是当前被访问顶点, 在对 x做过访问标记后, 选择一条从 x 出发的未检测过的边 (x, y )。若发现顶点 y已访问过, 则重新选择另一条从 x 出发的未检测过的边, 否则沿边 (x, y)到达未曾访问过的 y, 对 y访问并将其标记为已访问过; 然后从 y 开始搜索,直到搜索完从 y 出发的所有路径, 即访问完所有从 y出发可达的顶点之后, 才回溯到顶点 x, 并且再
11、选择一条从 x 出发的未检测过的边。上述过程直至从 x 出发的所有边都已检测过为止。此时, 若 x 不是源点, 则回溯到在 x 之前被访问过的顶点; 否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点 )都已被访问过, 若图 G 是连通图, 则遍历过程结束, 否则继续选择一个尚未被访问的顶点作为新源点, 开始新的搜索过程。3 解决方案及实例通过分析知道, 我们所做的其实是一个带权无向图的 K 条路径深度优先遍历问题, 一般对图进行深度优先搜索遍历的算法所得到的遍历结果是一个顶点的访问序列 , 而不是路径。虽然路径可以用顶点序列表示, 但很重要一点是, 序列中任一相邻两个顶点之间必须存在
12、边, 但一般来说, 得到的序列都无法满足这样的要求, 不过路径遍历可以在深度优先搜索算法的基础上得到, 可以用一个栈保存路径上的顶点, 如果从某一定点出发的遍历不能达到目的地而结束, 则说明该顶点一定不在所求路径上, 应从栈中退出。算法的实现过程如下:第 6期贺同江等: 网络分析方法在 GPS控制网优化设计中的应用87设图 G 由 2个集合 V 和 E 组成, 记为 G = ( V, E ), V 是图中节点 (Vertex )的集合; E 是边的集合。节点与节点之间的连线称为边, 边是无向的称为无向图; 若 v, w 是 2 个节点从 v到 w 的无向边, 记为 ( v, w )。经改进的深
13、度优先遍历实现的算法过程如下:从图 G 中的 O 点出发寻找一个邻接点 (记为 M ) (按边权值最小 )。检查 O 点是否仍存在邻接点未遍历。如存在, 则选择第二个邻接点 (记为 P ), 如不存在则从邻接点开始进行下步搜索。! 比较 O 点与两邻接点 M、P 之间边的权值大小, 按从大到小的顺序进行下一邻接点的搜索 (记为 N )。% 比较 O 点与N、P 两点间边的权值, 按从大到小的顺序进行下一邻接点的搜索 (记为 V )。& 检查 V 点的邻接点 (除 N 或 P 外 )是否已遍历。如无则停止, 如有则继续! , 直至所有点已遍历为止。在只有一辆车的情况下, 这个问题就成了一个路径遍
14、历问题, 即K = 1。以图 2为例, 我们通过改进后的算法可以得到路径遍历的最终结果 1 2 4 2 3 6 5 6 7 8 10 9 (如图 5所示) , 该路径的权重为: 11+ 8 ( 2+ 10+ 10+ 5 ( 2+ 9+ 7+ 14+ 6= 84图 5单组运行下的线路选择Fig. 5The route selection in single team work该路径为我们所求的遍历整个图形最优路径, 达到了距离最短的要求。在不考虑其他约束条件的情况下,我们可以认为, 该路径即为我们所需要的路径。在两辆车同时运送人员的情况下, 即 K = 2时, 仍以图 2为例, 我们通过程序实现
15、, 可得到以下结果:第一条线路: 5 6 7 9 10, 该路径的权重为: 12+ 5+ 9+ 16+ 6= 48第二条线路: 1 2 4 2 3 8, 该路径的权重为: 11+ 8 ( 2+ 10+ 17 = 54在考虑了所有约束条件的情况下, 这两条路径即为所求(如图 6所示 )。图 6两组并行下的线路选择F ig. 6The route selection in two team work4 结论基于深度有限遍历算法的带权无向图路径遍历方法在 GPS控制网优化中的实现, 极大地提高了搜索效率, 节省了大量的人力和物力, 提高了工作效率。同时, 也为这种算法在 G IS中拓展了应用空间。但
16、是, 作者的算法也只能在较简单的网络 (K = 1 和 K = 2)中实现, 在复杂网络 (K 2)中的实现仍有待研究。参考文献: 1 N J N ilsson. Prin cip les of Artificial In telligenceM . T ioga, Palo A lto, 1980. 2 曾文, 徐世文. 地理信息系统中的常规网络分析功能及相关算法 J . 地球科学, 1998, 23( 4 ) . 3 苏运霖. 数据结构与算法 M . 长沙: 湖南工业大学出版社, 1999. 4 玉太, 王燕, 胡志刚. GPS 网的优化设计 J . 山西科技, 2004,( 5) .责任
17、编辑: 栾丽杰 (上接第 76页 )参考文献:平均拟合检核点最大残差为 15. 9 mm。二次曲面拟合结果最好, 可达到三等水准测量的精度要求; 平面拟合结果也能达到三等水准测量的精度要求; 加权平均拟合结果可达到四等水准测量的精度要求。转换结果可以用于工程实践, 同时也表明了所编程序的正确性。4 结论利用M atlab在矩阵计算方面的优良特性 (如矩阵左除、矩阵点除等 ), 可以很方便地实现 GPS高程转换, 免去了用一般测量计算方法中根据误差方程列出法方程再求解的麻烦, 大大提高了计算效率。 1 徐绍铨, 张华海, 杨志强, 等. GPS测量原理及应用 M . 武汉:武汉大学出版社, 2001. 2 张航, 黄攀, 等译. 精通 M ATLAB 6 M . 北京: 清华大学出版社, 2002. 3 邱斌, 朱建军. 基于灰关联分析的 GPS 高程拟合加权平均函数模型权函数优选 J . 测绘信息与工程, 2004, 9 ( 1 ): 13 - 14. 4 胡伍生, 高成发. GPS 测量原理及其应用 M . 北京: 人民交通出版社, 2004.责任编辑: 栾丽杰