首页 > 编程语言 >路径分析算法—基于A*算法的路径搜索

路径分析算法—基于A*算法的路径搜索

时间:2024-11-07 14:44:20浏览次数:1  
标签:路径分析 路径 距离 列表 算法 方格 移动

原文链接:路径分析算法—基于A*算法的路径搜索 – 每天进步一点点

A*算法擅长解决静态路径中最短路径问题,而又不同于Dijkstra 算法和Floyd算法,该算法综合了广度优先搜索(Breadth First Search)和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数)。Floyd算法更多地使用场景在于机器人路径规划、游戏路径、卫星路径探寻等领域。

1.应用实例:绕过障碍区到达目的地


某极地探险队在某森林中探险时,遇到一条河流,他们不能直接穿越河流,但是他们知道要达到露营的地方,则需要绕过该河流。因此,他们试图通过利用计算来测绘最终达到目的地的最近行走距离,用示意图简单表示探险队、河流、露营地的关系,如下图所示。

上图中的圆表示探险队,五星表示露营地,中间竖线表示河流,图中的每个方格表示探险队可以移动的位置,也是移动的距离单位。问如何利用计算绕过河流障碍区用最短的路程到达露营地。

2.A*算法与最短距离计算

对于地理环境中的一个固定地面位置,它至少可以被标记为两种状态:可使用区和不可使用区(障碍区),同时可以把该固定位置视为九宫格里面的中心点,如下图所示:

根据上图可以确定该中心点的移动方向包含8个方向,分别是:上、下、左、右、左上、左下、右上、右下。因此,A*算法的寻路流程可以通过如下三个步骤完成。

(1)从中心点开始,把它放入一个待计算的开放列表,开放列表可以理解为一个准备进行路径分析的队列。

(2)寻找中心点周围可达到的方格集,这些方格的状态需要是可以使用的,将这些方格放人到开放列表中,但是将这些方格的来源都标记为中心点。

(3)在开放列表中移除刚刚分析的中心点,将该中心点放入关闭列表中,关闭列表表示后续不再对该表进行可达到路径分析。
通过第(3)步已经完成了开放列表的获取,但是如何从开放列表中选择下一步的移动方格是A*算法思想中最核心的内容。A*算法利用公式/(n)=g(n)+h(n)筛选下一步移动方格,其中,g(n)代表从起初开始的方格移动到当前方格的移动距离;h(n)表示从即将移动到的方格到终点方格的距离,两者相加得到的f(n)即为当前预估的可能路径,这种可能路径中最小的值对应的方格即为当前可以从开放列表中选择的下一步移动方格,选择该方格之后再依次重复上述步骤,直到邻近的方格中存在终点方格(或终点方格进入了开放列表)。
上述步骤中g(n)和h(n)的值获取是A*算法计算的关键值。

g(n)定义的是起点方格到当前方格的距离,距离定义如下图所示:

如上图所示定义从方格的上、下、左、右四个方向移动产生的距离为10;从左上、左下、右上、右下移动产生的距离为15。在实际应用中,每个方向的距离都有可能不同,g(n)则是从起点方格开始通过不断的方位移动累计的距离和。
2.h(n)的计算
A*算法的路径寻找是一种启发式搜索,启发式搜索减少了在路径搜寻过程中可能耗费的时间性能,如从一个方格到另外一个方格的可能距离,如果通过穷举法的确是可以计算出最短距离,但是如果方格过大,则可能导致计算性能严重下降。启发式搜索在于对距离的估算,省去大量不必要的路径计算,其中h(n)即是对当前方格到目的地方格的距离估算。

曼哈顿距离算法能够较好地用于计算h(n),在所有的平面方格中,可以用二维数据表示每个方格的二维坐标,通过曼哈顿距离算法可以计算出距离值,通常也会对距离值进行扩倍。例如,上下左右邻近的方格通过曼哈顿距离计算出的距离值是1,而上下左右移动的实际产生距离是10,因此将曼哈顿距离乘以系数10(也有可能是其他系数值)得到h(n)。值得注意的是h(n)的计算只是一个估算过程,并不代表着绝对的路径,但是估计若是越接近真实值,则算法计算的性能越好,在真实的应用场景中,估算过程还会更加复杂。

标签:路径分析,路径,距离,列表,算法,方格,移动
From: https://www.cnblogs.com/longkui-site/p/18532218

相关文章

  • HintonLeCunBengio:AI算法的奠基者
    深度学习、神经网络、卷积神经网络、循环神经网络、GeoffreyHinton、YannLeCun、YoshuaBengio1.背景介绍人工智能(AI)的蓬勃发展,离不开深度学习的革命性突破。深度学习,作为机器学习的一个分支,通过构建多层神经网络来模拟人类大脑的学习机制,取得了令人瞩目的成就。而推......
  • 深入理解PPO算法:从原理到实现
    目录1.引言2.PPO算法的背景3.PPO算法的核心思想4.PPO算法的实现步骤 4.1PPO代码实现 4.2代码说明5.为什么PPO效果如此出色? 5.1PPO的优势函数与GAE 5.2PPO的变体:PPO-Clip和PPO-KL6.PPO算法的应用场景7.总结1.引言        在强化学习领域,PPO(P......
  • 【KMP算法】
    目录BF算法KMP算法BF算法F算法,即暴力(BruteForce)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后......
  • α-shape算法曲面重建
    目录1原理介绍α-shape的基础概念数学公式推导2.1外接圆半径2.2根据α参数筛选三角形2.3构建α-shape2.4参数调整与优化3α-shape的构建步骤4示例代码        取点云的凹边界是计算几何中的一个经典问题。凹边界与凸边界不同,它能捕捉到数据的细......
  • Java深度优先搜索(DFS)算法实现
    标题:Java深度优先搜索(DFS)算法实现引言:深度优先搜索(Depth-FirstSearch,DFS)是一种常用的图遍历算法,它通过递归地遍历图中的每个顶点,来寻找特定的路径或解决某些问题。本篇博客将介绍如何用Java语言实现深度优先搜索算法。算法思想:深度优先搜索算法的基本思想是先访问一个......
  • c++ Kruskal 最小生成树 (MST) 算法(Kruskal’s Minimum Spanning Tree (MST) Algorith
            对于加权、连通、无向图,最小生成树(MST)或最小权重生成树是权重小于或等于其他所有生成树权重的生成树。Kruskal算法简介:        在这里,我们将讨论Kruskal算法来查找给定加权图的MST。         在Kruskal算法中,按升序对给定图的所有......
  • 常考的排序算法
    冒泡排序#include<iostream>#include<string>usingnamespacestd;//voidShellsort(intA[],intn)//{//   intd,i,j;//   for(d=n/2;d>=1;d=d/2)//   {//      for(i=d+1;i<=n;i++)//      {//     ......
  • JavaScript Kruskal 最小生成树 (MST) 算法(Kruskal’s Minimum Spanning Tree (MST) A
             对于加权、连通、无向图,最小生成树(MST)或最小权重生成树是权重小于或等于其他所有生成树权重的生成树。Kruskal算法简介:        在这里,我们将讨论Kruskal算法来查找给定加权图的MST。         在Kruskal算法中,按升序对给定图的所......
  • 基于springboot框架在线生鲜商城推荐系统 java实现个性化生鲜/农产品购物商城推荐网站
    基于springboot框架在线生鲜商城推荐系统java实现个性化生鲜/农产品购物商城推荐网站爬虫、数据分析、排行榜基于协同过滤算法推荐、基于流行度热点推荐、平均加权混合推荐机器学习、大数据、深度学习OnlineShopRecommendEx一、项目简介1、开发工具和使用技术IDEA,jdk......
  • 基于ACO蚁群优化的VRPSD问题求解matlab仿真,输出规划路径结果和满载率
    1.程序功能描述基于ACO蚁群优化的VRPSD问题求解matlab仿真,输出ACO优化的收敛曲线,规划路径结果和每一条路径的满载率。2.测试软件版本以及运行结果展示MATLAB2022a版本运行 3.核心程序%搜索fori=1:Iterationiis_best=0;forj=1:Npop......