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

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

带限制条件的最短路径算法与实现

给出了在GIS环境下带限制条件的单源最短路径算法,该算法是基于二叉堆优先级队列及邻接表的Dijkstra算法.根据用户给出的起始节点和目标节点以及避开节点列和必经节点列,在建立的搜索图中用Java语言实现分段查找最短路径.     

基于 STL下最优路径组件设计与应用

最优路径分析源于最短路径的扩展,它是GIS中最基本的网络分析,由此引申出针对诸如物流运输、交通规划、流量分析、公交换乘、GPS导航等实际问题提供一套完善的解决方案,Dijkstra算法是目前公认的较好的最短路径算法。借助于STL(标准模版库)优秀的运算性能以及高效的内存管理机制,引入邻接点、邻接边结构来表达图,将权重作为启发搜索的触动器,从而完成对最优路径的自动判断与提取。     

限制搜索区域的距离最短路径规划算法

提出一种时间复杂度为O(n)的限制搜索区域距离最短路径规划算法(n为路网节点数).算法设计的基础是,经典Dijkstra算法搜索时的无方向性及实际城市道路网络特有的空间分布特性.算法实现采用邻接表数据结构和限制搜索区域的搜索机制,即利用实际城市道路网络的空间分布特性,合理限制算法的搜索区域.结合路径规划算法在实时车辆导航系统中的实际应用,给出了该算法的应用实例,实验结果表明,该算法能将路网中任意两点间的最短路径解算时间控制在3 s以内.     

最短路径的改进与实现

最短路径分析是GIS最基本的网络分析功能。Dijkstra算法是目前公认的较好的最短路径算法。文中从节约存储空间,提高运算速度出发,在Dijkstra算法基础上,提出邻接结点算法,并给出算法的面向对象的实现方法。     

Dijkstra改进算法在车辆导航系统中的应用与仿真

车辆导航系统的最基本功能是最短路径的搜索,车载导航是单源单目标的最短路径算法的重要应用之一.传统的Dijkstra算法是一种典型的单源最短路径算法,因为实际系统的实时要求,有必要改进Dijkstra算法.基于对时间和空间复杂度的分析,提出一种新型的Dijkstra改进算法,具有高效性.其改进分3个方面:采用邻接表作为道路网络拓扑的存储结构;利用二叉堆实现优先队列;根据节点的分布情况将搜索过程分为几个阶段,引入了动态限制搜索区域机制.最后在实际道路网络中的测试及仿真结果表明了改进算法的可行性和优越性.     

移动机器人路径规划算法的研究

路径规划技术作为机器人研究领域中的一个重要分支,是依据某些优化准则,在其工作空间中找到一条从起始状态到目标状态的最优无碰路径.本文针对机器人路径规划技术进行了深入地研究,阐述了机器人路径规划问题的三个子问题等内容,讨论了传统路径规划方法 和基于智能算法的路径规划方法 .本文运用传统Dijkstra算法的贪心策略,针对静态环境下移动机器人路径规划的寻路径子问题,提出了一种改进的Dijkstra路径规划算法.该算法借助具有"先进先出"特点的队列,采用广度优先遍历二维网络结点.该算法在选择邻接结点进行遍历的时候,采用的禁忌策略是禁止访问已经访问的结点,以及被标识为障碍物的结点.实验及分析表明,该算法能准确并快速地寻找到最优路径,且时间复杂度为O(4*n).     

考虑信号交叉口转向类型的最优路径规划算法

针对现有最优路径规划算法没有充分考虑不同转向类型的车辆在信号交叉口处的等待时间,导致算出的最优路径实际效果不佳等问题,提出了一种考虑信号交叉口转向类型的最优路径规划算法.首先,根据不同的转向类型构建了信号交叉口等待时间模型;然后,提出了一种改进的星型表,对路网中邻接路段之间的转向类型与相应参数进行表达和存储优化;在此基础上,提出了考虑信号交叉口转向类型的拓展A*算法(CMTA*算法),并进行了算例验证.结果表明,相比于传统算法和考虑信号交叉口等待时间的CWTSISP算法,CMTA*算法所计算出的最优路径时间费用更低,并且运算效率更高.     

超图的最短路径算法

从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法.     

基于转向限制的改进双向启发式最短路径算法

针对考虑转向限制的单源点单汇点最短路径问题,根据动态对偶图思想,建立道路交通网络对偶图,提出了基于存储对偶图节点的双邻接表存储地图数据;改进传统的A*算法,提出了基于可搜索无限邻域的双向启发式算法。该算法选用基于OSP的地图作为实验数据进行路径规划,并运用于基于SLAM算法的车型机器人上进行实验。结果表明该算法可在栅格地图上找到符合实际交通规则的更优可行路径,效率也可满足路径规划要求。     

公交线路查询算法的设计与实现

以图的赋权邻接矩阵为切入点,建立了以换乘次数最小为首要目标,途径站点数最小为第二目标的公交出行最优路径模型;同时,回避了最短路径算法时间复杂度大的缺点,以最短路径矩阵为数据系统,提出了解决公交查询的通用高效算法;最后,通过公交查询系统实例证实了其可行性和有效性.     

具有不可靠链路的通信网最佳可靠路由的确定

研究了对给定拓扑结构的通信网在假定节点完全可靠而边存在随机破坏的情况下,通过计算点对间的路由概率确定最佳可靠路由的两种算法———邻接矩阵算法和动态路由算法－ 邻接矩阵算法通过构造网络的邻接矩阵及一些相关矩阵,利用深度优先搜索的方法找到点对间的所有路由,进而计算各路由的概率并由此确定最佳可靠路由－ 动态路由算法则给出了在链路失效后,按照最短路径原则由失效链路的起始点重新构造最佳可靠路由的方法－ 图１,参５－     

货运调度系统中的一个最短距离算法

本文结合具体的公路交通图,采用图的节点压缩法和分块技术,实现了货运调度系统中一个求交通图上任意两点间的最短距离的优化算法。     

基于关节空间与工作空间协同的6R点焊机器人路径规划方法

为实现6R点焊机器人动态性能优、焊接路径短的规划目标,提出在关节空间采用5次多项式规划其转角运动,以确保机器人从任一焊点到相邻焊点时的动态特性;基于组合数学原理,枚举点焊机器人工作时遍历所有焊点的可能路径集合,结合关节空间与工作空间映射关系和各可能路径长度动态积分的数值计算,给出最优焊接路径排列顺序。最后通过算例对该规划方法进行了验证。     

路和圈幂图的邻点可区别E-全染色

以一个简单图G为基础,连接G的任意最短路长为k的2个顶点就可得到基础图G的k-幂图,研究了路的k-幂图和圈的2-幂图的邻点可区别E-全染色问题,并结合该类幂图的结构性质,运用构造法、反证法和穷举分类染色技术给出了其邻点可区别E-全色数,为确定图的各类染色问题提供了有效的借鉴.     

最短路问题在运输网络中的应用

最短路问题是在图的基础上衍生出来的,也是网络优化中的一个基本问题,许多选择优化问题都可以转化为最短路问题来求解。本文重在研究公路网络运输中的最短路问题。     

几类图的均匀邻点可区别全染色

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G（V,E）为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|－|Vj∪Ej||≤1（i≠j）,其中,Vi∪Ei={v|f（v）=i}∪{e|f（e）=i},记C（i）=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat（G）=min{k|G存在k－均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

基于时间依赖网络的危险品运输路径选择研究

为合理选择危险品运输路径,降低危险品运输事故的发生概率,以危险品运输路径选择问题为研究对象,对运输网络的时变特性进行分析,提出了动态路阻运输路径的思想。考虑到危险品运输不一定满足时间依赖网络FIFO特性,因此本文建立了包括时间阻抗、费用阻抗和风险阻抗在内的综合阻抗最小的危险品运输路线模型,采用综合阻抗最小化与时间依赖非FIFO网络最短路径综合算法对模型优化求解。给出的算例表明,不同时间段内的最优路径会发生变化,验证了该模型方法的可行性。     

路,圈的倍图的染色问题

通过分类讨论、归纳探究,在图的点边集合与色集合间构造了一种一一对应关系.通过这种新关系,研究了路和圈的倍图的邻强边染色以及路的倍图的均匀邻强边染色,得到相应的色数,并给出了具体的染色方案     

基于Mapinfo的最短路径混合搜索算法

在迪杰斯特拉(Dijkstra)算法的基础上,针对有较多节点和道路的大网络在求解最短路径时计算时间慢、扩展节点多的缺点,采用基于局部最优方向和A*算法的混合算法,利用局部最优方向法的结果,对A*算法的启发函数加以改造,可以减少扩展的节点数量,快速的找到一条最短路径.通过实验仿真证实了该算法的快速有效性.