正在加载图片...
第7期 高蕊等：基于MapObject的矿井火灾动态最佳救灾路线数学模型和算法 ·707, 间巷道的实际长度；lm为i、j节点间巷道中第m个 数 局部通行障碍物当量长度值，1≤m≤n;n为i、j节 2.2 Dijkstra算法 点间巷道中局部通行障碍物的个数. 设图G=(V,E),图中每条边具有非负长度， 从图论角度来看，井下错综复杂的巷道实际上 有一个特异顶点u称为源，假定(u,v)是E中的 是一个连接的网络图，巷道为图的边，巷道之间的交 边，cu,是边的长度，如果把顶点集合V划分为两 点抽象成图的点的集合，组成网络图的顶点；在无向 个集合S和T,S中所包含的顶点到u的距离己经 网络图上赋予救灾路线选择的影响因素，以巷道当 确定，T中所包含的顶点到的距离尚未确定.同 量长度作为边的长度，把整个井下巷道网络布局转 时，把源顶点u到T中顶点x的距离d,x定义为从 化为图的拓扑优化问题，优化目标是使从救灾基地 “出发，经过S中的顶点，但不经过T中其他顶点， 到受灾地点路线的当量长度最短，作为图论的经典 而直接到达T中的顶点x的最短路径的长度，则 问题，最短路径问题的定义是在一个赋权图的两个 Dijkstra算法的思想方法如下：开始时，S={u}, 顶点之间找出一条具有最小权值的路径.可用于解 T=V一{u}.对T中的所有顶点x,如果u到x存 决矿井灾害时期最佳救灾路线的选择问题， 在边，置d,x=cu,x;否则置du,x=o,然后，对T 2基于VEpObject的矿井火灾救灾路线算法的 中的所有顶点x,寻找du,x最小的顶点t,即： 研究 du,t=mini du,xx∈T} (6) 则d,就是顶点t到顶点u的最短距离.同时，顶 在许多地理信息系统开发平台中，都提供了最 点t也是集合T中的所有顶点中距离u最近的顶 短路径的函数或方法，比如说MapEngin,Supermap, 点，把顶点t从T中删去，把它并入S.然后，对T 但是，这些函数或方法都进行了封装，并且是解决不 中与t相邻接的所有顶点x,用下式更新d,x的值： 含权的最短路[]，如果要解决含权巷道的最短路， du.xmini du.x,du,c.x (7) 或者在排除某一条或几条巷道（具有超过人体耐受 继续上面的步骤，一直到T为空. 极限的高温烟流)之后的最短路，就需要在最短路中 增加一些附加条件，并且附加条件可修改， 由此，如果令p(x)是从顶点u到顶点x的最 短路径中x的前一顶点，那么，Dijkstra算法可以用 MapObject是美国环境系统研究所(ESRI)开发 的一种地理信息系统控件，其优点是可以嵌入到其 下面的步骤来描述]： 他软件中.Ma即Object采用面向对象编程，对电子地 (1)置S=iu},T=V-{uf. 图进行分层管理，每层对应一个数据库文件，层间进 (2)对Hx∈T,若(u,x)∈E,则d,x=cu,x, 行分目标、分物体管理，最终将电子地图上的物体对 p(x)=u;否则du,x=oo,p(x)=一1. 应到数据库中相应的字段上[]， (3)寻找t∈T,使得d,=min du,xx∈T, 2.1传统最短路径算法 则du,就是t到u的距离 传统的最短路径算法主要有Floyd算法和 (4)S=SU1t},T=T-{t}. Dijkstra算法等，其中Floyd算法是用于计算所有点 (5)若T=0,算法结束；否则，转步骤(6). 对点之间的最短路径.Dijkstra算法用于计算一个 (6)对与t相邻接的所有顶点x,如果d,.≤ 源节点到其他节点的最短代价路径，有较高的应用 du,t十c,x,直接转步骤(3)；否则，令du,x=du,t十 价值.Cherkassky于1993年在SUN Spare-10工作 c,xp(x)=t,转步骤(3) 站上对17种最短路径算法进行了测试，实验证明没 2.3 Dijkstra算法改进及在MlapObject中实现 有哪一种算法能够适应所有类型的网络.1996年 在选择矿井火灾救灾路线时，需要对Dijkstra Zhan和Noon使用实际交通网络测试了Cherkassky 算法进行改进并且编程实现，在弄清楚Dijkstra算 测试的17种算法中的15种，测试结果表明：计算一 法的基本思想和算法步骤后，编程实现显得比较容 点到所有其他点的最短路径最快的算法是Dijkstra 易，结合矿井救灾的实际情况，在以下几个方面对 算法，对于非负带权图而言，Dijkstra单源最短路径 Dijkstra算法进行改进[9l5] 算法(single-source shortest paths,SSSP)的时间复 (I)根据Dijkstra算法流程，顶点集V的大小 杂度为O(m十lgn),而多源的最短路径算法 将直接影响算法的速度.步骤(2)一(5)是一个循环 (all-pairsshortestpaths,APSP)的时间复杂度为 比较的过程，如果没有经过任何处理，则要选择一个 O(mn十n1gn),m为边的条数，n为节点的个 权值最小的节点将需要扫描V中所有的节点，这无间巷道的实际长度；lijm为 i、j 节点间巷道中第 m 个 局部通行障碍物当量长度值1≤ m≤ n；n 为 i、j 节 点间巷道中局部通行障碍物的个数． 从图论角度来看井下错综复杂的巷道实际上 是一个连接的网络图巷道为图的边巷道之间的交 点抽象成图的点的集合组成网络图的顶点；在无向 网络图上赋予救灾路线选择的影响因素以巷道当 量长度作为边的长度把整个井下巷道网络布局转 化为图的拓扑优化问题优化目标是使从救灾基地 到受灾地点路线的当量长度最短．作为图论的经典 问题最短路径问题的定义是在一个赋权图的两个 顶点之间找出一条具有最小权值的路径．可用于解 决矿井灾害时期最佳救灾路线的选择问题． 2 基于 MapObject 的矿井火灾救灾路线算法的 研究 在许多地理信息系统开发平台中都提供了最 短路径的函数或方法比如说 MapEngin、Supermap． 但是这些函数或方法都进行了封装并且是解决不 含权的最短路［5］．如果要解决含权巷道的最短路 或者在排除某一条或几条巷道（具有超过人体耐受 极限的高温烟流）之后的最短路就需要在最短路中 增加一些附加条件并且附加条件可修改． MapObject 是美国环境系统研究所（ESRI）开发 的一种地理信息系统控件其优点是可以嵌入到其 他软件中．MapObject 采用面向对象编程对电子地 图进行分层管理每层对应一个数据库文件层间进 行分目标、分物体管理最终将电子地图上的物体对 应到数据库中相应的字段上［6］． 2∙1 传统最短路径算法 传统的最短路径算法主要有 Floyd 算法和 Dijkstra算法等其中 Floyd 算法是用于计算所有点 对点之间的最短路径．Dijkstra 算法用于计算一个 源节点到其他节点的最短代价路径有较高的应用 价值．Cherkassky 于1993年在 SUN Sparc—10工作 站上对17种最短路径算法进行了测试实验证明没 有哪一种算法能够适应所有类型的网络．1996年 Zhan 和 Noon 使用实际交通网络测试了 Cherkassky 测试的17种算法中的15种测试结果表明：计算一 点到所有其他点的最短路径最快的算法是 Dijkstra 算法．对于非负带权图而言Dijkstra 单源最短路径 算法（single-source shortest pathsSSSP）的时间复 杂度 为 O（ m＋ nlg n）而 多 源 的 最 短 路 径 算 法 （al-l pairsshortestpathsAPSP ） 的 时 间 复 杂 度 为 O（ mn＋ n 2lg n）m 为边的条数n 为节点的个 数［7］． 2∙2 Dijkstra 算法 设图 G＝（ V E）图中每条边具有非负长度 有一个特异顶点 u 称为源．假定（ uv ）是 E 中的 边cuv 是边的长度．如果把顶点集合 V 划分为两 个集合 S 和 TS 中所包含的顶点到 u 的距离已经 确定T 中所包含的顶点到 u 的距离尚未确定．同 时把源顶点 u 到 T 中顶点 x 的距离 dux定义为从 u 出发经过 S 中的顶点但不经过 T 中其他顶点 而直接到达 T 中的顶点 x 的最短路径的长度则 Dijkstra 算法的思想方法如下：开始时S ＝｛u｝ T＝ V —｛u｝．对 T 中的所有顶点 x如果 u 到 x 存 在边置 dux＝cux；否则置 dux＝∞．然后对 T 中的所有顶点 x寻找 dux最小的顶点 t即： dut＝min｛dux｜x∈ T｝ （6） 则 dut就是顶点 t 到顶点 u 的最短距离．同时顶 点 t 也是集合 T 中的所有顶点中距离 u 最近的顶 点．把顶点 t 从 T 中删去把它并入 S．然后对 T 中与 t 相邻接的所有顶点 x用下式更新 dux的值： dux＝min｛duxdut＋ctx｝ （7） 继续上面的步骤一直到 T 为空． 由此如果令 p （ x）是从顶点 u 到顶点 x 的最 短路径中 x 的前一顶点那么Dijkstra 算法可以用 下面的步骤来描述［8］： （1） 置 S＝｛u｝T＝ V —｛u｝． （2） 对∀ x∈ T若（ ux）∈ E则 dux＝ cux p（ x）＝ u；否则 dux＝∞p（ x）＝—1． （3） 寻找 t∈ T使得 dut＝min｛dux｜x∈ T｝ 则 dut就是 t 到 u 的距离． （4） S＝S∪｛t｝T＝ T—｛t｝． （5） 若 T＝∅算法结束；否则转步骤（6）． （6） 对与 t 相邻接的所有顶点 x如果 dux ≤ dut＋ctx直接转步骤（3）；否则令 dux ＝ dut＋ ctxp（ x）＝t转步骤（3）． 2∙3 Dijkstra 算法改进及在 MapObject 中实现 在选择矿井火灾救灾路线时需要对 Dijkstra 算法进行改进并且编程实现．在弄清楚 Dijkstra 算 法的基本思想和算法步骤后编程实现显得比较容 易．结合矿井救灾的实际情况在以下几个方面对 Dijkstra 算法进行改进［9—15］． （1） 根据 Dijkstra 算法流程顶点集 V 的大小 将直接影响算法的速度．步骤（2）～（5）是一个循环 比较的过程如果没有经过任何处理则要选择一个 权值最小的节点将需要扫描 V 中所有的节点这无 第7期 高 蕊等： 基于 MapObject 的矿井火灾动态最佳救灾路线数学模型和算法 ·707·