通风网络含有单向回路时的通路算法

所谓单向回路就是风路风流方向相同的回路。网络中存在单向回路，也就是说存在着循环风。通路是图论中的一个重要概念，在通风网络中也有着广泛的用途。在介绍无单向回路的通风网络的通路数和通路矩阵计算方法的基础上，提出了含有单向回路的通风网络的通路的矩阵算法的不适用性问题。论述了通过修改搜索策略，利用深度优先搜索法确定通路矩阵的算法，该法既适用于有单向回路时的通风网络，也适用于无单向回路的情况，而且复杂性要比矩阵算法小得多。     

基于遗传算法的通风网络平衡图绘制编码

为了研究应用独立通路法绘制通风网络平衡图时存在矩形块被切割的问题,采用基于节点排序的二进制编码及整数编码的混合遗传编码方法,表示矿井通风网络拓扑关系的变化情况。结果表明:应用遗传混合编码方法,不但可以清晰明了的表达矿井通风网络节点出边拓扑关系的变化,并且按照这样的编码,将染色体串解码为所代表搜索到的独立通路,可以表示出寻找独立通路的不同顺序。该编码方法,为研究矿井通风网络平衡图绘制的矩形块切割问题,提供有效的方法。     

基于调风效率与通风阻力的封闭型网络利弊分析

提出了“封闭性网络”的概念,分析了封闭型网络的形成原因及其合理性;与含自由风路的风网对照,说明了封闭型网络可导致矿井出现附加阻力、增加矿井总阻力的弊端.基于最长路算法原理,说明了附加阻力的计算方法.实现了以确定自由分支和加边法找独立回路为内容的封闭型网络解除方法.以某矿通风系统优化为例说明了封闭型网络的具体表现与相关方法的优越之处.     

节点分层法求解通风网络中的所有通路

针对目前通风网络所有通路搜索算法效率较低的问题,提出节点分层法.通过节点分层和层间分支拼接求解所有通路,避免了频繁的后退操作,提高了算法效率.根据节点分层法和现有通路搜索方法开发了算法效率测试软件,并对不同规模的通风网络进行所有通路搜索效率对比测试.研究结果表明:节点分层法搜索效率随着网络规模增大而提高;对于1 010条分支的通风网络,节点分层法较深度优先搜索法提高41.59%.该方法适合大规模通风网络所有通路的快速求解.     

引入方向因子的最小回路、最大回路搜索算法

提出了最小回路、最大回路和方向因子的概念，基于方向因子构造了最小回路、最大回路搜索算法。算法依据图论知识，建立改进后的无向图邻接矩阵，根据节点坐标确定搜索始点，将搜索边失量化，结合节点坐标求解邻接边的方向因子，按方向因子的大小可以快速确定搜索边，形成了无向图中最小回路、最大回路搜索算法。该算法每搜索一次都可以确定一条搜索边，通过生成退化图减小下一次搜索的搜索范围，提高了搜索速度，反映出较小的时间复杂度。根据该算法编制了相应的算法程序，成功解决了建筑工程量计算中的外墙壁和房间划分问题。     

位势法在交通优化问题中的应用

研究了单源多汇交通优化问题及其重要性质,提出了单源多汇交通优化问题的位势法,该算法以关于费用的最短路程为初始势,以非零流的最小费用流为初始流;用标号法找可行的增广链,在标号过程中若某点不满足平衡要求则由到达该点的可行的增广链增广最小费用流的流量;以弧割为工具,计算最小费用流的势的最大调整量,并修改最小费用流的势.算例证明了算法的正确性和复杂性及算法的有效性.     

通风网络中通路总数确定方法的改进

在目前通风网络中通常总数确定方法的基础上，利用图论和集合论的知识，进行了深入研究，提出了计算复杂度较小的行向量法，当网络较小时，这种方法适于手动计算，利于课堂教学；当网络较大时，可大大降低计算机运算时的计算复杂度，利于科学研究，针对现有方法不合适计算多源多汇型网络通路总数的不足，行向量通过加虚分支和虚节点给出了多源多汇型网络通路总数的计算解决方案，对于理论研究及程序设计有重要意义。     

通风网络解算初始风量确定方法

矿井通风网络解算前,各分支风量的初值直接影向网络解算的速度和迭代是否收敛.分析了影响通风网络各分支风量分配的3个因素:网络拓扑结构、矿井总风量和分支本身的风阻;提出了确定通风网络解算初始风量的新思路,把通风网络的独立通路当作并联通风路线,利用矿井总风量和通路风阻计算各通路的风量,再分到每个分支中.通过一个网络图示例说明了使用该思路提出的方法,给出了通风网络解算初值与网络解算真值的误差,除角联分支外都不超过20％.     

网络最大流模型算法及其实现

针对网络最大流的计算问题，提出了一种网络最大流计算模型的实现方法,具体作法是灵活运用栈和结构数组以实现算法功能．首先创建邻接表，其结构包含边的方向、容量、流量等信息.然后根据邻接表采用标号法寻找增广链，在寻找过程中采用深度优先遍历和广度优先遍历的方法把点存入栈中，并用一数组保存所经过的路径．直至找出最大流及各边的流量.     

矿井通风网络风量调节分支的优化选择

为实现矿井通风网络风量的优化调节,依据通风网络理论,利用灵敏度方法初步选取调节分支,采取分风优化中的通路法,根据不同的调节区域对初选调节分支进一步筛选,使优选出的调节分支既方便调节又具有经济优势.结果表明,优选出的调节分支进行风量调节时更具针对性,同时可以指导矿井日常通风管理及巷道布置;并通过实例分析,验证了该风量调节分支优化选取方法的有效性.     

最短路径子图

在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.     

求解无环K短路径的Dijkstra算法

对多个标号的求解K短路径的Dijkstra改进算法进行完善,引入两个前驱节点矩阵pre和Kpre,通过这两个矩阵可以求出起始点到当前节点的当前路径,并判断这条路径是否有环,从而在寻找K短路的过程中避免了环的出现,完善后的算法可以求出前K短无环路径,该算法仅需要较少的额外计算量,所以仍然保持了算法的多项式复杂性.然后在不同规模的网络上对完善后的算法进行数值试验,验证了算法的正确性和有效性.     

双代号单目标网络图线路数量的计算方法

基于对双代号单目标网络图线路数量影响因素的研究,阐明了节点和箭线是组成线路的基本要素,关联节点的箭线在网络图进展方向上形成线路分支的数量多少,是影响网络图线路数量的决定因素,提出了网络图箭线的线路值的新概念和计算线路值的公式,从而解决了计算网图线路数量的线路值法和图上计算法。     

基于网络编码的共享链路路径保护机制

网络编码(network coding,NC)方法能够有效地提高路径保护技术的保护效率.但目前提出的基于网络编码的保护机制要求工作路径链路分离,限制了保护机制的性能和应用范围.为此提出一种基于网络编码的有共享链路的路径保护机制(shared-link network coding path protection,SNCPP).该机制将共享链路的端节点加入到保护路径源目的节点集中,采用改进的ASTAR算法建立经过节点集中所有节点的最短保护路径,并利用网络编码实现对有共享链路的路径进行保护.仿真表明所提出的机制在工作路径出现共享链路故障的情况下,能够对网络提供保护,并提高了保护效率.     

k-不相交路径的容错拓扑控制算法

针对无线传感器网络中拓扑控制算法优化目标单一的问题,提出一种既能优化网络能量效率,又能保证网络容错性的k-不相交路径的容错拓扑控制算法.首先,构建传感器节点到sink节点的k条不相交路径,通过增加冗余链路以提高网络的容错性;其次,选择路径能耗、路径中节点功率的标准差及路径跳数检测路径质量;最后,建立多目标规划,并利用智能优化算法对其进行求解,根据k值的不同对路径进行择优选择以达到降低网络能耗并延长网络寿命的目的.仿真实验结果表明,由该算法构造的网络拓扑能有效降低网络能耗,延长网络寿命并提高网络的容错性.     

道路网络中门到门包含重复节点的最优路径算法

设计了具有交通约束的受限路网中,基于兴趣点(POI)的门到门包含重复节点的寻路算法。该算法首先利用距离最短准则建立POI和路网间的临时拓扑关系,然后根据受限路网中最优路径的结构特征,构造包含驶入路段的节点进行寻路拓展,以此为基础进行标记设定广度优先搜索,即可获得门到门包含重复节点的最优路径。在道路密度较大的北京市路网中的试验结果表明,该算法能够根据交通约束规划出实用的最优路径,对于长度约60km路径的计算平均耗时在3s左右,可以满足车辆导航应用的实时性要求。     

能量感知多路径负载均衡路由算法

针对移动自组织网络的网络拥塞问题,基于能量感知技术并结合负载均衡和拥塞控制方法,提出了一种能量感知多路径负载均衡路由算法。该算法利用能量感知选择满足条件的节点作为路由节点,建立多条连接源节点和目的节点的有效路径;同时分析路径的跳数、节点缓冲区的占用情况,从有效路径中选出用于传输的最优路径;然后对最优路径上的节点和路径的负载情况进行建模分析,当节点能量、节点负载、路径负载到达设定的阀值,就将最优路径上的流量分流到其它路径。利用NS2仿真软件,在不同的场景下对该算法以及QMRB、SMORT进行仿真测试。仿真结果显示:提出的算法与其它路由算法相比将网络性能提升了近20%,起到了均衡负载的作用,能有效地解决网络拥塞问题。     

道路网络中门到门包含重复节点的最优路径算法

设计了用于包含交通约束的受限路网中基于兴趣点(PO I)的门到门包含重复节点的寻路算法。首先利用距离最短准则建立PO I和路网间的临时拓扑关系,然后根据受限路网中最优路径的结构特征,构造包含驶入路段的节点进行寻路拓展,以此为基础进行标记设定广度优先搜索,即可获得门到门包含重复节点的最优路径。在道路密度较大的北京市路网中的试验结果表明,该算法能够根据交通约束规划出实用的最优路径,对于长度约60 km路径的计算平均耗时在3 s左右,可以满足车辆导航应用的实时性要求。     

基于邻接矩阵的网络流量检测点选取算法研究

为对网络流量进行有效检测,考虑网络节点的流守恒,把网络流量检测点选取问题抽象为无向图的弱顶点覆盖问题.基于图论中邻接矩阵的概念,在满足对任意顶点度数大于2的假设条件下,提出一个求解弱顶点覆盖问题的近似算法.通过将求解弱顶点覆盖集中点与边的关系转化为点与点的关系,降低了矩阵计算复杂度.仿真实验表明,与现有算法相比,新算法能够选取出更小的弱顶点覆盖集,部署更少的网络流量检测点,减轻了由网络流量数据收集造成的额外负担.     

基于协同进化和并行计算的船舶管路布置方法

为解决船舶管路协同布置问题,提出一种适合求解多管路或分支管路协同布置的算法框架.通过为每条管路或分支生成对应的进化种群,将管路间的协同布置转换为种群间的协同进化.基于提出的路径连接点概念,生成管路接口间的候选路径种群,并对种群进行交叉、变异操作.使用A~*算法作为寻路算子,提高了生成路径的质量,同时保证了路径的有效性.为了提高运算效率,引入并行计算策略对算法框架和A~*算法进行改进.最后,两个仿真实例验证了所提出方法的可行性和有效性.