论文部分内容阅读
由于我国的能源组织结构具有“富煤、缺油、少气”的特点,所以在未来相当长的一段时期内煤炭仍将作为一种主要能源在我国的国民经济中发挥着重要的作用。由于煤炭赋存条件的特殊性,决定了大部分的煤炭开采都属于井工开采。相比较于地面环境而言,井下环境更加复杂,更加恶劣,发生灾变时,情况更加混乱。因此为了避免各种人员伤亡和财产损失事故的发生,需要政府、煤矿管理层、矿工、社会舆论力量的共同配合协作来实现。但是由于某些天灾人祸,矿井事故有时候会不可避免的发生,在这种情况下,人员逃生和救援受伤人员就成为了矿山应急救援工作的重中之重。然而衡量应急救援工作成功与否的主要标志是能否在规定的时间内完成人员的逃生与救援,也就是能否在与时间的赛跑中获胜。这就需要人员在逃生和救援时,尽量沿着最短路径进行逃生,就可以节省很多宝贵的时间。这就是本文所选择课题的意义。在综合和参考国内外最优路径相关研究成果的基础之上,本文对最优路径的概念和求取办法以及相关程序设计都进行了基础性的探讨。本文首先阐述了最优路径和K则最优路径的概念,明确了最优路径并不是传统意义上的几何距离最短,而是在参考了多个影响因素下的当量长度最短。然后介绍了求取最优路径的各种方法,主要详细介绍了经典Dijkstra算法的基本原理以及计算步骤,分析了经典Dijkstra算法的优缺点,针对其存在的搜索方向的盲目性和效率低的缺点,提出了扇形优化、直线优化和节点优化的各种改进算法。同时简要介绍了其他多种计算最优路径的算法,包括蚁群算法、Floyd算法等等。对于K则最优路径而言,目前没有特别完善的算法,但是常用的算法有去边算法,也就是先利用经典Dijkstra算法计算出任意两点之间的最优路径,然后依次删除最优路径中的任一边,重新计算比较得到K则最优路径,这种算法有一定的优势,只需要反复运用Dijkstra算法即可,但是这种算法求得的是近似最优路径。本文还重点介绍了求取K则最优路径的邻近点算法、稀疏矩阵算法、双向搜索算法等,并对各种算法都用小实例加以诠释,分析其利弊。相比较而言,双向搜索算法的思路更清晰,也最简单,就是两次Dijkstra算法而已。它的主要思路是:分别以灾变地点和安全地点为起始点,向外扩展,直到某一个节点被两边扩展的路径都永久标记,也就是成为了连接点,这时候从灾变地点到连接点的最优路径加上从连接点到安全地点的最优路径就是所求得的最优路径,然后继续两边搜索,就可以依次得到第二优路径、第三优路径等等。后来针对本文所涉及到的VB程序设计语言给予了简单的介绍。之后根据华盛矿的具体巷道参数和通风网络图,并用Dijkstra算法和K则最优路径的双向搜索算法为基础,分别设计了求取最优路径和K则最优路径以及多个安全出口的最优路径的运行界面,并通过实际节点验证了其正确性与可操作性。最后对本课题研究所存在的问题与不足以及对未来的展望做了简单的陈述。