两种改进的最优路径规划算法

在对经典Dijkstra算法和A*算法分析的基础上对它们分别进行了改进.在经典Dijkstra算法中,针对当前不相连节点间路径长度为无穷大这一特点,首先对两个节点是否相连进行判断;若发现两个节点并不相连时,则舍去相应计算,从而减小计算量.针对A*算法在实际应用中搜索效率低的缺点,将经典A*算法搜索出的原始最优路径中的节点依次进行封堵后,再按照经典A*算法搜索出相应的新最优路径,最后再将原始最优路径与这些新最优路径进行对比,以便确定最终的最优路径.仿真研究表明:改进的Dijkstra算法可以减少大量的无关节点计算,提高运算的效率;改进的A*算法则可以提高搜索到最优路径的成功率.     

识别业务流程中活动环的新方法:字符串可达矩阵

可达矩阵只能表达两个节点之间的可以达到的关系,环的识别需通过对矩阵的观察进行,当矩阵阶数较高时会相应增加环的识别难度.在可达矩阵的基础上提出了一种寻找不合理活动环的新方法字符串可达矩阵.该方法将字符串引入到可达矩阵中,从而可以在矩阵中显示出活动环及活动路径.详细描述了该方法所涉及的定义及运算规则,最后用实例解释了该方法的计算步骤、以及如何快速地找到了活动环及活动路径,为业务流程再造提供了一种新的解决方案.     

Dijkstra算法在权矩阵上的实现

Dijkstra算法是求解最短路问题的有效算法,一般都是在图上进行直接标号,文章探讨了直接在权矩阵上使用该算法求出最短路径及其长度的方法。     

一种基于网络编码的Ad Hoc网络多路径源选路由算法

根据Ad Hoc网络的特性,提出了一个基于网络编码的多路径源选路由算法.算法借鉴了COPE的思想,实现上通过在中间节点缓存短路径,对具有编码机会的中间节点进行标注,从而获得具有最大编码机会的多条路径.由于网络编码可以减少数据传输的次数,因此可以有效地提高信道的利用率.NS2环境下的仿真表明,新算法能够有效地平衡网络负载,提高网络的吞吐量.     

环状给水管网节点流量算法

文章从环状管网的两个基本关系矩阵环-节点矩阵和环-管段矩阵入手,分析了节点所连总体管段号与它们之间的内在联系,找出所有与各节点相连管段的总体管段号,生成节点-管段矩阵。与管长矩阵结合求出该节点流量所需的计算管长,考虑供水规模和各大集中用水户,应用沿线分配流量的原则,编制出求解各节点流量的主程序,从而避免了繁琐的手工计算,提高了工作效率。     

一类混合迭代算法在约束预测控制中的应用

为了改进多变量约束预测控制的滚动优化算法,对路径跟踪法和粒子群算法进行了理论研究,提出了一种将路径跟踪法和粒子群算法相结合的混合迭代算法,并用该混合算法对最具代表性的动态矩阵控制进行了滚动优化.仿真结果表明:对由于参数选择引起矩阵奇异时,路径跟踪法无法求出最优解,而基于混合迭代算法的优化算法可以得到最优解.采用路径跟踪法和粒子群算法相结合的混合迭代算法对多变量约束预测控制进行滚动优化,保证了优化算法的快速性和可行性.     

城市轨道交通网络时变路径搜索算法

为求解时变路径搜索问题,设计并实现了城市轨道交通大规模网络条件下的时变k短路径搜索算法.算法可分为两部分:首先基于深度优先的边删除法搜索网络的静态k短路径,然后将静态k短路径按照列车到发时刻进行扩展并排序获得时变k短路径.将算法应用于北京地铁网络路径搜索实例中,通过与既有算法对比,证明本文算法具有较优的效率,并能够获取基于列车时刻表的有效的时变k短路径集,为城市轨道交通网络路径搜索和管理提供辅助技术支持.     

有效监测时间和范围的一氧化碳传感器优化布置

为确定易自燃煤矿一氧化碳传感器的合理数量和位置,采用Dijkstra算法,求得任意两个节点间的最短路径,建立了邻接节点路径矩阵和邻接节点时间矩阵.规定一个有效监测时间,把邻接节点时间矩阵化为有效监测矩阵,从而得到各节点的有效监测分支集合.利用极小边支配集原理提出了最少全覆盖布点法,给出了一氧化碳传感器的优化布置方案.研究结果表明:有效监测时间不同,布点的数量、位置以及分支覆盖度也不同.     

公共交通系统最佳路径算法

在分析城市道路网络最短路径算法(SP算法)和公交网络的特点的基础上,提出公共交通系统最佳路径算法.首先引入直达矩阵(T矩阵)和最小换乘矩阵(Q矩阵),讨论公交网络节点间换乘问题,得出最少换乘算法.利用Q矩阵确定节点间最少换乘次数,评价公交网络方便可达性.其次结合最少换乘算法,对最短路径算法(Dijkstra算法)进行改进.在标号过程中,利用Q矩阵对待检验T标号点进行筛选,减少T标号计算量,得到一条综合考虑路径长度和换乘的最佳路径.最后用一个简单的算例进行验算,说明该算法适用于一般公交网络,特别是换乘代价较高的公交网络.     

基于最短路径相似度的复杂网社团识别算法

基于最短路径的思想,定义新的节点相似度,利用谱平分算法来识别复杂网络的社团结构.首先根据节点间最短路径的思想计算改进的共享最近邻(SNN)相似度,将其标准化后求出标准化矩阵的特征值及特征向量,然后根据网络选取一定数目的第一非平凡特征向量作为聚类样本,利用FCM算法可识别网络的社团.实验结果表明,该算法对于社团结构不明显的网络划分效果很好.     

一种求解交通网络中最短路径问题的人工蜂群算法

用人工蜂群算法解决寻找时间依赖网络中两点之间的最短路径问题, 针对时间依赖网络中先入先出网络的特性, 改进原算法中的路径选择策略, 以优化生成的个体质量. 该算法使用的策略为每个个体（即每条路径）添加一张散列表, 用于记录搜索路径时遇到的路段, 通过查找该表可发现当前个体的更优解. 实验结果表明, 该改进方法能有效提升算法最终解的质量, 并极大缩短运行时间.     

一种改进的基于云环境的蚁群优化算法

在研究标准蚁群优化算法的基础上,提出一种旨在改善网络路由的蚁群优化算法以应用于云环境下多元化复杂的网络结构环境.新算法在原有蚁群算法智能寻优的基础上,加入网络节点在网审查机制,实时判断网络节点是否在网,选择最优解路径.仿真实验表明,改进算法能有效地改善因为网络节点在网情况的多变性而造成的部分路径失效的情况,进而缓解网络拥塞.     

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

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

最短路径子图

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

复杂网络的优化模型及最短路径求解

对大型复杂网络提出网络分级的思想，根据网络分级的情况定义网络结点的数据结构，然后使用改进的Dijkstra算法和最小生成树算法来计算网络中任意两结点之间的最短路径．     

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

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

用独立通路法确定矿井通风网络的极值流

确定矿井通风网络极值流的常用算法有Ford-Fulkcrson法、Edmonds-Karp法和Dinic法。所谓独立通路就是采用深度优先搜索法在找通路的过程中，后面的通路至少要含有一条前面的通路所不含有的分支。独立通路法确定网络的极值流，就是利用找独立通路的思想来找增广路，找增广路时每次至少有一个分支达到饱和。从网络的源点开始进行寻边，找分支的可增广量为量大的出边，将该出边的末节点作为新的寻边始节点，继续找可增广量最大的出边，该搜索过程一直到所寻找的分支的末节点为网络的汇点为止，一条增广路即一条通路确定完毕，将该通路中分支的最小增广量作为通路的增广量对通路的各分支进行增广。增广后至少有一条分支达到饱和，删除饱和分支，用导出的网络继续找新的增广路并增广。     

一种改进的基于树路径匹配的网页结构相似度算法

提出一种改进的基于树路径匹配的网页结构相似度算法, 该算法定义了树路径的序列相似度和位置相似度, 找出网页的树路径集合, 通过网页间的最佳树路径匹配计算结构相似度. 实验结果表明, 用改进后的算法计算网页结构相似度比传统树路径匹配方法更符合实际, 更合理有效.     

递相祖述复先谁——李退溪所捍卫的朱子义利说

根据传统快速搜索随机树算法(rapidly random-exploring trees,简称RRT)搜索速度快、所需时间短,但随机性大以及约束不足等特点,建立了直道和弯道的期望路径模型,采用高斯分布描述随机采样点,并引入启发式搜索机制,改进RRT算法.与原算法仿真对比,结果表明：改进算法所规划的路径质量显著提高,规划时间缩短一倍.同时,在Prescan软件中搭建直道和弯道仿真场景,跟随规划路径,结果表明：改进后RRT算法所得路径具有很好的跟随效果,且侧向加速度在车辆稳定性要求范围内,说明采用改进后的RRT算法进行汽车局部路径规划可行实用.