基于改进A^(*)算法的路径规划研究

研究了A^(*)算法在二、三维模型路径规划中的优化方法。通过实时阈值法和惩罚因子法减少开放列表中不必要的搜索空间和冗余路径;采用自定义优先级队列、二叉堆法和哈希表替代传统A^(*)算法中的处理方式;在对二维地图的研究中,采用局部A^(*)算法避免大面积搜索。实验结果表明,经过改进的A^(*)算法显著提高了搜索和路径规划速度,减少了计算时间和内存消耗,验证了该算法的可行性和有效性。

基于分层图的最短路径选择问题研究

路径选择问题是图论中的经典问题之一,为解决在特定约束条件下路径选择问题最短路的求取,文章采用了分层图的思想来对路径选择问题进行建模,将原图拓展为多个连接情况相同的图层,提出了一种基于分层图的最短路算法,并分别从算法思想、算法执行过程、时间复杂度等方面与传统求解方法进行比较。实验结果表明分层图最短路算法具有较低的时间复杂度与较好的性能。

基于GIS优化Dijkstra算法在物流中心选址中的研究

基于传统的Dijkstra算法,提出了一种采用二叉堆结构和网络边存储模型的优化Dijkstra算法。实验结果表明:优化后的算法是切实有效的,将其应用到物流中心选址中得到了较满意的选址方案。

基于配对堆改进的Dijkstra算法

在GIS网络分析系统中,Dijkstra算法是求解最短路径的经典算法。为了进一步提高求解最短路径的效率和节省系统的内存空间,提出了使用一种新式的数据结构——配对堆,以便通过实现可降级的优先队列来改进Dijkstra算法,然后通过研究配对堆的基本操作,给出了使用配对堆结构实现Dijkstra算法的方法和流程,并分析了其算法复杂度。该算法在VegaGIS系统中实现,取得到了较好的效果。

一种基于分层图的改进SPFA算法

针对数据结构课程教学中顶点数受限的最短路径问题,提出一种基于图分层的改进SPFA算法——K_SPFA。借鉴图分层思想,将原图拓展为层数与顶点限制数相等的图层,将原图中的边拓展成图层间的边。利用2个同步循环的FIFO队列和贪心策略,对SPFA算法的数据存储结构和最短路径更新操作进行改进,从而实现原图中顶点数受限的最短路径寻找。实验结果表明,K_SPFA具有较低的平均时间复杂度。

基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法

在深入分析传统Ｄｉｊｋｓｔｒａ算法的基础上，提出了利用基于ｋ 叉堆的优先级队列对算法进行改进的思想，并对３ 种可合并堆进行了比较，从理论上证明了四叉堆在ｋ 叉堆中的最优性，设计了基于四叉堆优先级队列及逆邻接表、顾及路段方向阻抗的改进型Ｄｉｊｋｓｔｒａ最短路径算法，将Ｄｉｊｋｓｔｒａ 算法复杂度降为Ｏ（ｎｌｏｇｎ）。针对ＧＩＳ－Ｔ应用系统的动态特征，提出了Ｄｉｊｋｓｔｒａ 算法的逆序计算方法，通过构造逆序最短路径树。

一种基于Dijkstra的最短路径算法

介绍了Dijkstra算法,在详细分析了该算法的实现方法以及其缺点的基础上,提出一种基于Dijkstra算法的优化算法-优先队列算法,在搜索最小的节点时,该算法的时间复杂度大大降低,具有较好适用性.

基于动态规划思想求解关键路径的算法

关键路径通常是在拓扑排序的基础上求得的。提出了一种利用图的广度优先搜索与动态规划算法相结合求解关键路径的新算法,该算法采用图的邻接表结构形式,不需要进行拓扑排序,较传统的算法具有较高的效率,同时具有较高的健壮性。

一种基于双端队列的交通网络最短路径Pallottino优化算法

最短路径算法是计算机科学与地理信息科学领域的研究热点,而标号算法则是最短路径算法中的重要一族。长期以来,对于最短路径的算法实现,绝大多数都是围绕以D ijkstra算法为核心的标号设定算法来展开,而对标号改正算法的研究与应用却非常少见。为了对交通网络最短路径进行更有效、更快速的计算,通过对标号改正算法思想的深入分析,针对其中最具代表性的Pallottino算法,从存储结构和运行结构两方面进行了算法的优化改进,同时分析了该算法的时间复杂度和空间复杂度,并利用实际的大规模城市交通网络进行了效率测试。结果显示,与目前公认最优的标号设定算法中基于逼近桶结构的D ijkstra算法相比,该改进的标号改正Pallottino算法具有更好的适用性和更高的运行效率,因此在交通网络最短路径分析应用中具有很高的应用价值。

基于多目标遗传算法的灾后可靠路径选择

为了尽快运出灾民、运进物资,灾后需要选择最短的运输路径;考虑到灾害对道路的损毁,安全的路径是道路选择中的重要因素,基于灾后道路的损毁状况,采用3种方法定义道路可靠性,以最小化路径长度、最大化路径可靠性为目标建立双目标优化模型,采用多目标遗传算法求解.分别求得3种情形下的解,开展2个目标的Pareto分析;分析交叉概率和变异概率对结果的影响:交叉概率增大,覆盖范围波动式变化,理想积波动式下降;变异概率增大,覆盖范围波动式变化,理想积缓慢增长后逐渐下降.采用遗传算法能够有效地解决最短和最可靠路径的搜索问题.

Dijkstra算法程序的优化与实现

在分析传统Dijkstra算法的基础上,提出该算法实现方法存在的缺点,继而提出一种基于Dijkstra算法的优化算法-优先队列算法,在搜索最小的节点时,该算法的时间复杂度大大降低,具有较好适用性.

交通问路系统中最短路径的新算法

研究交通线路中的最短路径算法 ,应用图论中的广度优先搜索思想 ,给出优先队列的进出队方式 ,提供一种有效的最短路径的新算法 .该算法简洁、运算速度快、效果好 ,并在实际应用中取得了证明 .

智能交通通信同心游程路由算法

智能交通是必须建立在信息量极大的实时无线通信的基础上的,光靠设备的添加与升级,通信速度是跟不上交通发展的步伐的,并且设备的费用也不低[6]。所以,如何在已有的网络设备的基础上,研究信息传输路线,来提高信息传输速度,是一个很现实的难题。本路由算法是以交通管理中心为中心,通过最短路径算法与本游程算法结合,算出一个信息从交通管理中心出发,遍历所有交通管理分站的路径,并且算法充分考虑多种条件的限制下,如何算出最好的路由方案。

单源最短路径问题的改进算法

探讨了单源最短路径问题算法所能达到的时间复杂性的下界 ,提出了时间复杂性为O(tn+m)和O(nlogt+m)的改进算法 ,其中n =|V|,m =|E|,t为从优先队列中抽取最小结点的次数 ,我们主要用Fibonacci堆和拓扑排序的思想方法。

自动化仓库巷道网络AGV货区遍历优化——设计基于优先权遗传算法实现

针对自动化仓库、自动化车间及自动化码头等自动化局部物流存储系统仓库巷道网络中AGV(自动化导引车)对仓库货区遍历作业的路径优化问题,以搜索遍历所有货区的最短路径为目标,建立混合整数线性规划模型,并设计基于优先权的遗传算法求解。通过Matlab仿真实验分析比较算子性能,验证算法的有效性。

求解最短路问题的改进禁忌搜索算法

最短路问题(Short-Path Problem)以其广泛的应用场景一直是热点问题,目前已有Dijkstra等基本算法可以求得问题的最优解,但当网络节点较多时,表现出耗时较长、求解困难等问题。禁忌搜索算法是基于邻域搜索的智能优化算法,适合解决大型组合优化问题。在给出基于顶点优先权最短路径问题的基础上,建立数学优化模型,并设计禁忌搜索算法的步骤和算法关键技术,最后以顶点数为30的网络验证该算法的有效性。结果表明:该算法能求得本算例的最优解且计算时间比Dijkstra短。

应用于战术边缘网络的随机森林路由算法

战术边缘网络几乎很难保证端到端的链路,只能利用节点的移动性和存储能力来实现通信。现有的路由协议中大多只关注某一特定的路由因素(如相遇概率)且中继节点只能被动接受消息,很难适应机动性强的战术边缘网络。提出了一种动态的基于随机森林算法的路由算法(routing algorithm based Random Forest,RAbRF),中继节点能根据系统网络的各种因素对所要转发的消息基于随机森林算法进行排序,从而选择最偏向的消息进行存储转发。RAbRF算法与基于概率的路由算法进行了仿真对比,结果表明,提出的算法能够有效改善消息传递成功率,传输时延。

基于优先队列的时变网络最短路径算法

提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。