精华内容
下载资源
问答
  • A*算法原理

    万次阅读 2018-08-31 22:05:48
    A算法是启发式算法重要的一种,主要是用于在两点之间选择一个最优路径,而A的实现也是通过一个估值函数 F=G+H G表示该点到起始点位所需要的代价 H表示该点到终点的曼哈顿距离。 F就是G和H的总和,而最优路径也...

    A*简介

    A算法是启发式算法重要的一种,主要是用于在两点之间选择一个最优路径,而A的实现也是通过一个估值函数

    F=G+H

    • G表示该点到起始点位所需要的代价
    • H表示该点到终点的曼哈顿距离。
    • F就是G和H的总和,而最优路径也就是选择最小的F值,进行下一步移动(后边会做详细介绍)

    曼哈顿距离

                             

                                                                          Paste_Image.png

    上图中这个熊到树叶的曼哈顿距离就是蓝色线所表示的距离,这其中不考虑障碍物,假如上图每一个方格长度为1,那么此时的熊的曼哈顿距离就为9.
    起点(X1,Y1),终点(X2,Y2),H=|X2-X1|+|Y2-Y1|
    我们也可以通过几何坐标点来算出曼哈顿距离,还是以上图为例,左下角为(0,0)点,熊的位置为(1,4),树叶的位置为(7,1),那么H=|7-1|+|1-4|=9。

    OPEN ,CLOSE列表

    还是以上图为例,比如刚开始熊位置我们会加入到CLOSE列表中,而熊四周它可以移动到的点位我们会加入到OPEN列表中,并对熊四周的8个节点进行F=G+H这样的估值运算,然后在这8个节点中选中一个F值为最小的节点,然后把再把这个节点从OPEN列表中删除,加入到Close列表中,从接着在对这个节点的四周8个节点进行一个估值运算,再接着依次运算,这样说大家可能不是太理解,我会在下边做详细解释。

    A*算法实例

                             

                                                                                    Paste_Image.png

     

    从起点到终点,我们通过A星算法来找出最优路径

                                                                    

                                                                                     Paste_Image.png

    我们把每一个方格的长度定义为1,那从起始点到5位置的代价就是1,到3的代价为1.41,定义好了我们接着看上图,接着运算

                               

                                                                                     Paste_Image.png

    第一步我们会把起始点四周的点加入OPEN列表中然后进行一个估值运算,运算结果如上图,这其中大家看到一个小箭头都指向了起点,这个箭头就是指向父节点,而open列表的G值都是根据这个进行计算的,意思就是我从上一个父节点运行到此处时所需要的总代价,如果指向不一样可能G值就不一样,上图中我们经过计算发现1点F值是7.41是最小的,那我们就选中这个点,并把1点从OPEN列表中删除,加入到CLOSE列表中,但是我们在往下运算的时候发现1点的四周,2点,3点和起始点这三个要怎么处理,首先起始点已经加入到了CLOSE,他就不需要再进行这种运算,这就是CLOSE列表的作用,而2点和3点我们也可以对他进行运算,2点的运算,我们从1移动到2点的时候,他需要的代价也就是G值会变成2.41,而H值是不会变的F=2.41+7=9.41,这个值我们发现大于原来的的F值,那我们就不能对他进行改变(把父节点指向1,把F值改为9.41,因为我们一直追求的是F值最小化),3点也同理。

                               

                                                                                      Paste_Image.png

     

    在对1点四周进行运算后整个OPEN列表中有两个点2点和3点的F值都是7.41,此时我们系统就可能随机选择一个点然后进行下一步运算,现在我们选中的是3点,然后对3点的四周进行运算,结果是四周的OPEN点位如果把父节点指向3点值时F值都比原来的大,所以不发生改变。我们在看整个OPEN列表中,也就2点的7.41值是最小的,那我们就选中2点接着运算。

                                

                                                                                      Paste_Image.png

     

    我们在上一部运算中选中的是1点,上图没有把2点加入OPEN列表,因为有障碍物的阻挡从1点他移动不到2点,所以没有把2点加入到OPEN列表中,整个OPEN列表中3的F=8是最小的,我们就选中3,我们对3点四周进行运算是我们发现4点经过计算G=1+1=2,F=2+6=8所以此时4点要进行改变,F变为8并把箭头指向3点(就是把4点的父节点变为3),如下图

                                

                                                                                      Paste_Image.png

    我们就按照这种方法一直进行运算,最后 的运算结果如下图

                                

                                                                                        Paste_Image.png

     

    而我们通过目标点位根据箭头(父节点),一步一步向前寻找最后我们发现了一条指向起点的路径,这个就是我们所需要的最优路径。 如下图的白色选中区域

                                

                                                                                         Paste_Image.png

    但是我们还要注意几点

    • 在实际情况下有些地方是陆地,有些地方是沼泽,经过同样距离的陆地和沼泽时我们付出的代价不一样,此时我们在计算G值的时候就要考虑进去。
    • 有的时候我们寻找出来的路径可能不只一条,但是这两条路径的代价肯定是一样的,我们会随机选择一条。如下图

                                                            

                                                                                        Paste_Image.png

     

    最优路径有2个

    • 1-2-3-4-5-6
    • 1-2-3-4-5-7

    A*算法总结(Summary of the A* Method)

    Ok ,现在你已经看完了整个的介绍,现在我们把所有步骤放在一起:

    1.         把起点加入 open list (优先级队列)。

    2.         重复如下过程:

    a.         遍历 open list ,查找 F 值最小的节点,把它作为当前要处理的节点。

    b.         把这个节点移到 close list 。

    c.         对当前方格的 8 个相邻方格的每一个方格?

    ◆     如果它是不可抵达的或者它在 close list 中,忽略它。否则,做如下操作。

    ◆     如果它不在 open list 中,把它加入 open list ,并且把当前方格设置为它的父亲,记录该方格的 F , G 和 H 值。

    ◆     如果它已经在 open list 中,检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好,用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样,把它的父亲设置为当前方格,并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话,改变后你可能需要重新排序。

    d.         停止,当你

    ◆     把终点加入到了 open list 中,此时路径已经找到了,或者

    ◆     查找终点失败,并且 open list 是空的,此时没有路径。

    3.         保存路径。从终点开始,每个方格沿着父节点移动直至起点,这就是你的路径。


    转自 人工智能 A*算法原理

    展开全文
  • A*算法原理概述

    万次阅读 多人点赞 2019-05-06 19:57:27
    这里是目录路径规划A*算法原理路线规划理论概述Dijkstra算法最佳优先搜索算法A*算法理论概述 路径规划A*算法原理 路线规划理论概述 移动一个物体直观上很容易的,但是物品的路线规划是复杂的。如下图3-1所示,物体...

    路径规划A*算法原理

    路线规划理论概述

    移动一个物体直观上很容易的,但是物品的路线规划是复杂的。如下图3-1所示,物体最初位于地图的底端,并尝试向顶部移动。物在扫描的区域中,没有任何东西显示物体不能向上移动,因此它持续向上移动。在靠近顶部时,它探测到一个障碍物然后改变移动方向。然后它沿着U形障碍物找到它的红色的路径。但是,路径规划将会扫描一个更大的区域(淡蓝色阴影部分),但是它能做到不让物体避开凹形障碍物,找到一条更短的路径(蓝色线)。
    在这里插入图片描述
    图3-1 物体规划前路线示意图
    不带路径规划的运动可以在很多种情形下工作,同时可以扩展到更多的情形,但是路径规划是一种更常用的解决方法,路径规划可以提前作出路线规划,避免最后时刻发现问题。因此,研究人员提出路径搜索算法,用于规避上图的凹形障碍,示意图如下:
    在这里插入图片描述
    图3-2 路径规划路线示意图

    Dijkstra算法

    Dijkstra算法思想是从物体所在的初始点开始,遍历地图中的节点,迭代检查所有待检查节点集中的节点,并把和该节点最靠近的尚未检查的节点加入待检查节点集。该节点集从初始节点向外扩展,直到到达目标节点。Dijkstra算法保证能找到一条从初始点到目标点的最短路径,只要所有的边都有一个非负的代价值。在下图中,粉色的节点是初始节点,蓝色的节点是目标点,而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的,因而形成探测过程的边境:
    在这里插入图片描述
    图3-3 Dijkstra算法搜索示意图

    最佳优先搜索算法

    最佳优先搜索(BFS)算法评估任意节点到目标点的代价。与选择离初始节点最近的节点不同的是,它选择离目标最近的节点。最佳优先搜索算法不能保证找到一条最短路径。但是,较之Dijkstra算法,最佳优先搜索算法速度较快,因为它用了一个启发式函数快速地导向目标节点。例如,如果目标位于出发点的南方,BFS将趋向于导向南方的路径。在下面的图中,越黄的节点代表越高的启发式值(移动到目标的代价高),而越黑的节点代表越低的启发式值(移动到目标的代价低)。与Dijkstra 算法相比,BFS运行速度得更快。
    在这里插入图片描述
    图3-4 最佳优先搜索(BFS)算法搜索示意图
    然而,这两个例子都仅仅是最简单的情况——地图中没有障碍物,最短路径是直线的。现在我们来考虑前边描述的凹型障碍物。Dijkstra算法运行得较慢,但确实能保证找到一条最短路径:
    在这里插入图片描述
    图3-5 最佳优先搜索(BFS)算法障碍物规避示意图
     另一方面,BFS运行得较快,但是它找到的路径明显不是一条好的路径,如下图所示。最佳优先搜索的缺点在于算法本身是基于贪心策略的,它试图向目标移动尽管这不是正确的路径。由于它仅仅考虑到达目标的代价,而忽略了当前已花费的代价,于是尽管路径变得很长,它仍然继续走下去。
    在这里插入图片描述
    图3-6 最佳优先搜索(BFS)算法失败路径示意图

    A*算法理论概述

    A是路径搜索中最受欢迎的选择,因为它相当灵活,并且能用于多种多样的情形之中。和其它的图搜索算法一样,A算法潜在地搜索图中一个很大的区域。和Dijkstra一样,A能用于搜索最短路径。和BFS一样,A能用启发式函数,在简单的情况中,它和最佳搜索算法一样快。
    在凹型障碍物的例子中,A找到一条和Dijkstra算法一样好的路径:
    在这里插入图片描述
    图3-7 凹型障碍物A
    算法路径
    算法中的估价函数值代表从起始节点到当前节点的代价实际值,可能是距离或时间等指标的实际度量值,而值代表从当前节点到目标节点的代价估计值。当规定了地图节点之间的垂直、水平以及对角线代价后,在计算沿特定路径从起点到某一栅格节点的值时,可以依照路径的方向增加代价和求解。值可以用不同的方法估算,在网格地图中主要有曼哈顿距离、对角线距离和欧几里得距离三种,具体如下:
    (1)曼哈顿距离
    当机器人小车在地图中的运动方向只有正南、正北方向或者正东、正西方向时,可以选择曼哈顿距离作为估价函数。
    在这里插入图片描述
    图3-8 曼哈顿距离示意图

    曼哈顿距离为两节点之间y轴方向(南北方向)上距离加上在x轴方向(东西方向)上距离,则启发式函数为:
    在这里插入图片描述
    假定直线行走一个网格的曼哈顿距离为D表示,则启发式函数为:在这里插入图片描述
    其中,c代表当前节点,goal代表目标节点。
    (2)对角线距离
    当机器人小车在地图中除了正南正北方向外,还允许对角运动时,此时可以选择对角线距离作为新的估价函数。
    在这里插入图片描述
    图3-9 对角线距离示意图
    两节点之间的对角线距离为当前节点与目标点在南北方向和东西方向上距离的最大值,即:
    在这里插入图片描述

    假定机器人小车直线行走和对角行走的代价都为对角线距离D,则启发式函数为:
    在这里插入图片描述
    其中,c代表当前节点,goal代表目标节点。

    如果对角线运动的代价不是D,而是D2=sqrt(2) * D,因此计算h_diagonal(n),即沿着斜线可以移动的步数,h_straight(n),即曼哈顿距离,然后合并这两项,让所有的斜线步都乘以D2,剩下的所有直线步(注意这里是曼哈顿距离的步数减去2倍的斜线步数)都乘以D。
    在这里插入图片描述
    则对角线的启发函数可以更新为:
    在这里插入图片描述

    (3)欧几里何距离
    如果机器人小车在地图中可以沿着任意角度移动,而不仅仅是网格方向或对角线方向时,则应该选择欧几里得距离,也称为直线距离。两点之间的直线距离为:
    在这里插入图片描述

    假设直线行走和对角线行走的代价都为,则启发式函数为:
    在这里插入图片描述

    因为欧几里得距离比曼哈顿距离和对角线距离都短,使用欧几里何距离仍可以得到最短路径,不过A*算法将运行得更久一些。

    参考:
    http://theory.stanford.edu/~amitp/GameProgramming/
    http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths

    展开全文
  • 算法只要懂原理了,代码都是小问题,先看下面理论,尤其是红色标注的(要源码请留下邮箱,有测试用例,直接运行即可) A*算法 百度上的解释: A*[1] (A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法...
    算法只要懂原理了,代码都是小问题,先看下面理论,尤其是红色标注的(要源码请留下邮箱,有测试用例,直接运行即可
    A*算法
    百度上的解释:
    A*[1] (A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。
    公式表示为: f(n)=g(n)+h(n),
    其中 f(n) 是从初始点经由节点n到目标点的估价函数,
    g(n) 是在状态空间中从初始节点到n节点的实际代价,
    h(n) 是从n到目标节点最佳路径的估计代价。
    保证找到最短路径(最优解的)条件,关键在于估价函数f(n)的选取:
    估价值h(n)<= n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离,那么搜索将严格沿着最短路径进行, 此时的搜索效率是最高的。
    如果 估价值>实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。

    1.2 Dijkstra算法与最佳优先搜索


      Dijkstra算法从物体所在的初始点开始,访问图中的结点。它迭代检查待检查结点集中的结点,并把和该结点最靠近的尚未检查的结点加入待检查结点集。该结点集从初始结点向外扩展,直到到达目标结点。Dijkstra算法保证能找到一条从初始点到目标点的最短路径,只要所有的边都有一个非负的代价值。(我说“最短路径”是因为经常会出现许多差不多短的路径。)在下图中,粉红色的结点是初始结点,蓝色的是目标点,而类菱形的有色区域(注:原文是teal areas)则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的,因而形成探测过程(exploration)的边境(frontier):

    下图相同颜色的格子代表起点到达这些格子的代价是一样的,颜色越浅代表到达目标所需要的代价越大,Dijkstra算法均衡的向四面八方扩张,被扩张的每一个格子都会记住它前一个消耗最少的那个格子,直到扩张区域包含目标点


      最佳优先搜索(BFS)算法按照类似的流程运行,不同的是它能够评估(称为启发式的)任意结点到目标点的代价。与选择离初始结点最近的结点不同的是,它选择离目标最近的结点。BFS不能保证找到一条最短路径。然而,它比Dijkstra算法快的多,因为它用了一个启发式函数(heuristic function)快速地导向目标结点。例如,如果目标位于出发点的南方,BFS将趋向于导向南方的路径。在下面的图中,越黄的结点代表越高的启发式值(移动到目标的代价高),而越黑的结点代表越低的启发式值(移动到目标的代价低)。这表明了与Dijkstra 算法相比,BFS运行得更快。

    贪心算法:颜色相同的格子代表这些格子在理想状态下(没有障碍物的情况下)直线到达目标点的代价是一样的,从起点不停的像终点扩张,扩张的时候会记住前一个最小理想代价的格子如果碰到障碍物它会重新选择新的理想代价最少的那一个格子直到到达目标格子



      然而,这两个例子都仅仅是最简单的情况——地图中没有障碍物,最短路径是直线的。现在我们来考虑前边描述的凹型障碍物。Dijkstra算法运行得较慢,但确实能保证找到一条最短路径:


      另一方面,BFS运行得较快,但是它找到的路径明显不是一条好的路径:


      问题在于BFS是基于贪心策略的,它试图向目标移动尽管这不是正确的路径。由于它仅仅考虑到达目标的代价,而忽略了当前已花费的代价,于是尽管路径变得很长,它仍然继续走下去。

      结合两者的优点不是更好吗?1968年发明的A*算法就是把启发式方法(heuristic approaches)如BFS,和常规方法如Dijsktra算法结合在一起的算法。有点不同的是,类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而,尽管A*基于无法保证最佳解的启发式方法,A*却能保证找到一条最短路径。

    1.3 A*算法

      我将集中讨论A*算法。A*是路径搜索中最受欢迎的选择,因为它相当灵活,并且能用于多种多样的情形之中。

      和其它的图搜索算法一样,A*潜在地搜索图中一个很大的区域。和Dijkstra一样,A*能用于搜索最短路径。和BFS一样,A*能用启发式函数(注:原文为heuristic)引导它自己。在简单的情况中,它和BFS一样快。


      在凹型障碍物的例子中,A*找到一条和Dijkstra算法一样好的路径:


      成功的秘决在于,它把Dijkstra算法(靠近初始点的结点)和BFS算法(靠近目标点的结点)的信息块结合起来。在讨论A*的标准术语中,g(n)表示从初始结点到任意结点n的代价,h(n)表示从结点n到目标点的启发式评估代价(heuristic estimated cost)。在上图中,yellow(h)表示远离目标的结点而teal(g)表示远离初始点的结点。当从初始点向目标点移动时,A*权衡这两者。每次进行主循环时,它检查f(n)最小的结点n,其中f(n) = g(n) + h(n)

    A*算法:起点不停的向周围总代价(总代价=实际代价+估计代价;实际代价=起点到该点最小代价;估计代价=该点到终点的在理想代价,相当于没有障碍物的,有各种函数,我们自己选择)最小的格子不停扩张,每个格子都会记住前一个格子,前一个格子一般它周围总代价最小的可以使用的(当然不包括障碍物)格子,直到扩散的目标节点
    如下图,绿色代表起始点,黑色代表障碍物,红色代表终点,起点可以向前后左右斜着总共8个方向扩张,平移和上下移动一格消耗代价为10,斜着移动一格消耗代价14

    第一次扩散,如果是像四周8个方向扩散,我为了简化图外面都算障碍物 总共扫描了5个格子,加入openMap,openMap表示可以移动到的格子的集合,closeMap表示已经移动过的格子。
    上移动一格的信息如下:
    坐标(1,1)上一坐标:(1,2)
    实际代价:g(n)=向上一格=1*10=10
    曼哈顿距离:h(n)=D * (abs(n.x-goal.x) + abs(n.y-goal.y))
    估计代价:h(n)=终点坐标跟该点坐标的曼哈顿距离=(4,2)跟(1,1)的曼哈顿距离=(|4-1|+|2-1|)*10=40;
    总估价:f(n)=g(n)+h(n)=10+40=50

    按这样可以分别算出总代价: 50,44,34,44,50
    比较大小,44最小,所以向左移动一格到(2,2),并把(2,2)关闭起来加入closeMap并从openMap移除出去,再有(2,2)四周点扩散,发现
    (3,3)没加入openMap,然后把(3,3)加入openMap,在迭代openMap里面的元素看哪个最小
    发现(2,1),(2,3)总估价都是一样44,随机选一个,我选了(2,1)并加入closeMap,并移除出openMap
    每一个格子都会记住它上一个格子,上一个格子是它格子周围中到达这个格子花费世界代价最小的那一个
    所以坐标(3,3)的上一个格子是(2,2)而不是(2,3);
    坐标(2,3)的上一个格子是(1,2)而不是(2,2);
    按这样的方式不断的扩散,直到扩散到终点(4,2);
    然后不停的迭代终点的上一个是哪个格子,在迭代上一个的上一个
    最终获取最佳路径(1,2)->(2,2)->(3,3)->(4,2)

    最终获取最佳路径(1,2)->(2,2)->(3,3)->(4,2)

    加了个功能:如果终点在障碍物里面它会找到离终点最近距离的那一点


    图二

    代码结构

    package astar;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    
    /**
     * 
     * @author hjn
     * @version 1.0 2015-03-11
     * 
     */
    public class AStar implements IMove {
    
        public static final int MOVE_TETN = 10;
        public static final int MOVE_SIDE = 14;
        public static final int LENGHT = 10;
        /* 打开的列表 */
        Map<String, Point> openMap = new HashMap<String, Point>();
        /* 关闭的列表 */
        Map<String, Point> closeMap = new HashMap<String, Point>();
        /* 障碍物 */
        Set<Point> barrier;
        /* 起点 */
        Point startPoint;
        /* 终点 */
        Point endPoint;
        /* 当前使用节点 */
        Point currentPoint;
        /* 循环次数,为了防止目标不可到达 */
        int num = 0;
        
        Point lastPoint;
    
        /**
         * 获取点1到点1的最佳路径
         */
        @Override
        public Point move(int x1, int y1, int x2, int y2, Set<Point> barrier) {
            num = 0;
            this.lastPoint=new Point(x2,y2);
            this.barrier = barrier;
            this.startPoint = new Point(x1, y1);
            Point endPoint=new Point(x2,y2);
            this.endPoint = this.getNearPoint(endPoint,endPoint);
            this.closeMap.put(startPoint.getKey(), startPoint);
            this.currentPoint = this.startPoint;
            this.toOpen(x1, y1);
            return endPoint;
        }
    
        
    
        /**
         * 求亮点间的估算代价,性能由高到低 启发函数一(曼哈顿距离): (Math.abs(x1 - x2) + Math.abs(y1 - y2)) *
         * 单位长度 启发函数二(平方的欧几里得距离):((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 -y1))*
         * 单位长度 启发函数三(欧几里得距离):(int) Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) *
         * (y2 -y1))* 单位长度 启发函数四(对角线距离):Math.max(Math.abs(x1 - x2), Math.abs(y1 -
         * y2)) * 单位长度 不用启发函数:0
         * 
         * @param x1
         *            点1x轴
         * @param y1
         *            点1y轴
         * @param x2
         *            点2x轴
         * @param y2
         *            点2y轴
         * @return
         */
        private int getGuessLength(int x1, int y1, int x2, int y2) {
            //return ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 -y1))* AStar.LENGHT;
            return (Math.abs(x1 - x2) + Math.abs(y1 - y2)) * AStar.LENGHT;
            // return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2)) * AStar.LENGHT;
            // return 0;
        }
    
        /**
         * 把该节点相邻点加入打开的列表
         * 
         * @param x
         * @param y
         */
        private void toOpen(int x, int y) {
            this.addOpenPoint(new Point(x - 1, y), AStar.MOVE_TETN);
            this.addOpenPoint(new Point(x + 1, y), AStar.MOVE_TETN);
            this.addOpenPoint(new Point(x, y - 1), AStar.MOVE_TETN);
            this.addOpenPoint(new Point(x, y + 1), AStar.MOVE_TETN);
            this.addOpenPoint(new Point(x - 1, y - 1), AStar.MOVE_SIDE);
            this.addOpenPoint(new Point(x - 1, y + 1), AStar.MOVE_SIDE);
            this.addOpenPoint(new Point(x + 1, y - 1), AStar.MOVE_SIDE);
            this.addOpenPoint(new Point(x + 1, y + 1), AStar.MOVE_SIDE);
            num++;
            if (num <= 4000) {
                this.toClose(x, y);
            }
    
        }
    
        /**
         * 把该节点相邻点加入关闭的列表
         * 
         * @param x
         * @param y
         */
        private void toClose(int x, int y) {
            List<Point> list = new ArrayList<Point>(openMap.values());
            Collections.sort(list, new Comparator<Point>() {
                @Override
                public int compare(Point o1, Point o2) {
                    if (o1.fTotal > o2.fTotal) {
                        return 1;
                    } else if (o1.fTotal < o2.fTotal) {
                        return -1;
                    } else {
                        return 0;
                    }
                }
            });
            if (list.size() > 0) {
                this.currentPoint = list.get(0);
                closeMap.put(this.currentPoint.getKey(), this.currentPoint);
                openMap.remove(this.currentPoint.getKey());
                if (!currentPoint.equals(endPoint)) {
                    this.toOpen(this.currentPoint.x, this.currentPoint.y);
                } else {
                        endPoint = this.currentPoint;
                }
            }
        }
    
        /**
         * 添加开放的点
         * 
         * @param point
         *            点
         * @param gCost
         *            当前点到该点的消耗
         * @return
         */
        private void addOpenPoint(Point point, int gCost) {
            if (point.x < 0 || point.y < 0) {
                return;
            }
            String key = point.getKey();
            if (!barrier.contains(point) && !point.equals(this.currentPoint)) {
                int hEstimate = this.getGuessLength(point.x, point.y,
                        this.endPoint.x, this.endPoint.y);
                int totalGCost = this.currentPoint.gCost + gCost;
                int fTotal = totalGCost + hEstimate;
                if (!closeMap.containsKey(key)) {
                    point.hEstimate = hEstimate;
                    point.gCost = totalGCost;
                    point.fTotal = fTotal;
                    Point oldPoint = openMap.get(key);
                    if (oldPoint != null) {
                        if (oldPoint.gCost > totalGCost) {
                            oldPoint.fTotal = fTotal;
                            oldPoint.prev = this.currentPoint;
                            openMap.put(key, oldPoint);
                        }
                    } else {
                        point.prev = this.currentPoint;
                        openMap.put(key, point);
                    }
                } else {
                    Point oldPoint = closeMap.get(key);
                    if (oldPoint != null) {
                        if ((oldPoint.gCost + gCost) < this.currentPoint.gCost) {
                            if (this.currentPoint.prev != oldPoint) {
                                this.currentPoint.fTotal = oldPoint.fTotal + gCost;
                                this.currentPoint.gCost = oldPoint.gCost + gCost;
                                this.currentPoint.prev = oldPoint;
                            }
                        }
                    }
                }
            }
        }
        
        
    
        Map<String, Point> nearOutMap;
    
        public Point getNearPoint(Point point,Point point2) {
            if(this.barrier.contains(point)){
                nearOutMap = new HashMap<String, Point>();
                this.endPoint=point;
                this.toNearPoint(point,point2);
                List<Point> nearList = new ArrayList<Point>(nearOutMap.values());
                Collections.sort(nearList, new Comparator<Point>() {
                    @Override
                    public int compare(Point o1, Point o2) {
                        if (o1.gCost > o2.gCost) {
                            return 1;
                        } else if (o1.gCost < o2.gCost) {
                            return -1;
                        } else {
                            return 0;
                        }
                    }
                });
                this.openMap=new HashMap<String,Point>();
                this.closeMap=new HashMap<String,Point>();
                if (nearList.size() > 0) {
                    return nearList.get(0);
                }else{
                    return point;
                }
            }else{
                return point;
            }
            
        }
    
        public void toNearPoint(Point point,Point point2) {
            int x = point.x;
            int y = point.y;
            this.addNearOpenPoint(new Point(x - 1, y),point2);
            this.addNearOpenPoint(new Point(x + 1, y),point2);
            this.addNearOpenPoint(new Point(x, y - 1),point2);
            this.addNearOpenPoint(new Point(x, y + 1),point2);
            this.addNearOpenPoint(new Point(x - 1, y - 1),point2);
            this.addNearOpenPoint(new Point(x - 1, y + 1),point2);
            this.addNearOpenPoint(new Point(x + 1, y - 1),point2);
            this.addNearOpenPoint(new Point(x + 1, y + 1),point2);
            if(this.nearOutMap.size()==0){
                List<Point> list = new ArrayList<Point>(openMap.values());
                Collections.sort(list, new Comparator<Point>() {
                    @Override
                    public int compare(Point o1, Point o2) {
                        int l1 = o1.gCost;
                        int l2 = o2.gCost;
                        if (l1 > l2) {
                            return 1;
                        } else if (l1 < l2) {
                            return -1;
                        } else {
                            return 0;
                        }
                    }
                });
                if (list.size() > 0) {
                    Point p = list.get(0);
                    this.closeMap.put(p.getKey(), p);
                    this.openMap.remove(p.getKey());
                    this.toNearPoint(list.get(0),point2);
                }
            }
        }
    
        private void addNearOpenPoint(Point point,Point point2) {
            String key = point.getKey();
            int gCost = this.getGuessLength(point.x, point.y, point2.x,
                    point2.y);
            point.gCost = gCost;
            if (this.barrier.contains(point)) {
                if (!this.openMap.containsKey(key)
                        && !this.closeMap.containsKey(key)) {
                    this.openMap.put(key, point);
                }
            } else {
                this.nearOutMap.put(key, point);
            }
    
        }
    
        public Map<String, Point> getOpenMap() {
            return openMap;
        }
    
        public void setOpenMap(Map<String, Point> openMap) {
            this.openMap = openMap;
        }
    
        public Map<String, Point> getCloseMap() {
            return closeMap;
        }
    
        public void setCloseMap(Map<String, Point> closeMap) {
            this.closeMap = closeMap;
        }
    
        public Set<Point> getBarrier() {
            return barrier;
        }
    
        public void setBarrier(Set<Point> barrier) {
            this.barrier = barrier;
        }
    
        public Point getEndPoint() {
            return endPoint;
        }
    
        public void setEndPoint(Point endPoint) {
            this.endPoint = endPoint;
        }
    
        public Point getStartPoint() {
            return startPoint;
        }
    
        public void setStartPoint(Point startPoint) {
            this.startPoint = startPoint;
        }
    
    }
    
    
    


    package astar;
    
    import java.util.Set;
    
    /**
     * 
     * @author hjn
     * @version 1.0 2015-3-11
     *
     */
    public interface IMove {
    	/**
    	 * 求点1到点2的合适路线
    	 * @param x1 点1x坐标
    	 * @param y1 点1y坐标
    	 * @param x2 点2x坐标
    	 * @param y2 点2y坐标
    	 * @param barrier 有顺序的路线列表
    	 * @return
    	 */
    	Point move(int x1,int y1,int x2,int y2,Set<Point> barrier);
        
    }
    
    package astar;
    
    public class Point {
    	int x;
    	int y;
    	int gCost;
    	int hEstimate;
    	int fTotal;
        Point prev;
        int level=1;
        
        public String getKey(){
        	return x+"_"+y;
        }
    	public Point(int x, int y) {
    		super();
    		this.x = x;
    		this.y = y;
    	}
    
    	
    	public Point(int x, int y, int gCost) {
    		super();
    		this.x = x;
    		this.y = y;
    		this.gCost = gCost;
    	}
    
    
    	@Override
    	public int hashCode() {
    		final int prime = 31;
    		int result = 1;
    		result = prime * result + x;
    		result = prime * result + y;
    		return result;
    	}
    
    	@Override
    	public boolean equals(Object obj) {
    		if (this == obj)
    			return true;
    		if (obj == null)
    			return false;
    		if (getClass() != obj.getClass())
    			return false;
    		Point other = (Point) obj;
    		if (x != other.x)
    			return false;
    		if (y != other.y)
    			return false;
    		return true;
    	}
    
    }
    

    package astar;
    
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Set;
    
    import org.junit.Test;
    
    public class TestPoint {
    	@Test
    	public void test2() {
    		AStar aStar = new AStar();
    		Set<Point> barrier = new HashSet<Point>();
    /*		for (int j = 30; j > 15; j--) {
    			for (int i = 20; i < 50; i++) {
    				barrier.add(new Point(j, i));
    
    			}
    		}*/
    
    	for (int j = 30; j > 15; j--) {
    			barrier.add(new Point(j, 20));
    		}
    	/*	
    		for (int j = 30; j > 15; j--) {
    			barrier.add(new Point(j, 50));
    		}
    		*/
    		for (int i = 20; i < 50; i++) {
    			barrier.add(new Point(30, i));
    		}
    		
    		for (int i = 20; i < 55; i++) {
    			barrier.add(new Point(15, i));
    		}
    		long start = System.currentTimeMillis();
    		for (int i = 0; i < 1; i++) {
    			aStar = new AStar();
    			aStar.move(10, 25, 28, 40, barrier);
    		}
    		long end = System.currentTimeMillis();
    		System.out.println(end - start);
    		Set<Point> set = new HashSet<Point>();
    		Point endPoint = aStar.getEndPoint();
    		Point startPoint = aStar.getStartPoint();
    		Map<String, Point> openMap = aStar.getOpenMap();
    		Map<String, Point> closeMap = aStar.getCloseMap();
    		set = TestPoint.get(endPoint, set);
    		/**
    		 * 显示最佳路径
    		 */
    		System.out.println(aStar.getEndPoint().getKey());
    		for (int i = 0; i < 70; i++) {
    			for (int j = 0; j < 70; j++) {
    				Point p = new Point(j, i);
    				if (p.equals(aStar.getEndPoint())) {
    					System.out.print("o");
    				} else if (p.equals(startPoint)) {
    					System.out.print("^");
    				} else {
    					if (set.contains(p)) {
    						System.out.print("@");
    					} else if (barrier.contains(p)) {
    						System.out.print("#");
    					} else {
    						System.out.print("*");
    					}
    
    				}
    				System.out.print(" ");
    			}
    			System.out.println();
    		}
    
    		System.out.println("--------------------------------------------------------------------------------------------------------");
    		/**
    		 * 扫描的范围
    		 */
    		for (int i = 0; i < 70; i++) {
    			for (int j = 0; j < 70; j++) {
    				Point p = new Point(j, i);
    				if (p.equals(endPoint)) {
    					System.out.print("o");
    				} else if (p.equals(startPoint)) {
    					System.out.print("^");
    				} else {
    					if (openMap.containsKey(p.getKey())) {
    						System.out.print("%");
    					} else if (closeMap.containsKey(p.getKey())) {
    						System.out.print("@");
    					} else if (barrier.contains(p)) {
    						System.out.print("#");
    					} else {
    						System.out.print("*");
    					}
    
    				}
    				System.out.print(" ");
    			}
    			System.out.println();
    		}
    
    	}
    
    	public static Set<Point> get(Point p, Set<Point> set) {
    		if (p != null) {
    			set.add(p);
    		}
    		Point pp = p.prev;
    		if (pp != null) {
    			TestPoint.get(pp, set);
    		} else {
    			return set;
    		}
    		return set;
    	}
    }
    




    展开全文
  • 之前有介绍A算法的代码注释和提供了MATLAB版的源码下载,这次主要是讲解A算法的基本组成和运行机制,相信能为刚开始学习路径规划的同学们提供到一点帮助。...A算法原理 A算法是一种高效的启发式搜索算法,在

    之前有介绍A* 算法的代码注释和提供了MATLAB版的源码下载,这次主要是讲解A* 算法的基本组成和运行机制,相信能为刚开始学习路径规划的同学们提供到一点帮助。
    声明:这篇博客是基于我个人对A*算法的理解基础上写出来的,与原作者或者现在的主流思想有没有出入现在尚未知晓,如果文中有哪些地方书写或者描述有错误,可以在评论区打出来,大家一起交流学习,共同进步,感谢!

    原创作品,转载请注明出处。

    概述
    1968年,一篇名为《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》的文章出版,里面提出了A* 算法,并且使得A* 算法在接下来的几十年中飞速发展,并且广泛应用在导航、迷宫求解、游戏寻路、机器人路径规划等应用中。
    A* 算法原理
    A* 算法是一种高效的启发式搜索算法,在二维的栅格地图上寻路效果好,它通过估算节点的代价评估函数值并作为节点的综合优先级,当选择下一个需要遍历的节点时,再选取综合优先级最高的节点,逐步地找到最优路径。A* 算法可以快速的找到代价值最小,路程最短的路径,但是随着栅格精度的提高和地图尺寸的扩大,对无用节点的重复搜索评估会导致 A* 算法搜索时间呈指数级增长。
    简单的说就是在一个栅格地图中,通过不断计算当前点与目标点的代价值来选择下一步应该怎么走。这个代价值主要是有两部分组成。
    A* 算法的组成
    代价计算公式:F(n)=G(n)+H(n)
    其中, F(n) 是从初始状态经由状态n到目标状态的代价估计,
    G(n) 是在状态空间中从初始状态到状态n的实际代价,
    H(n) 是从状态n到目标状态的最佳路径的估计代价。
    此处用栅格地图中的路径规划问题作为例子讲解。
    讲解可以参照视频。
    以移动机器人的移动为例,假设栅格的大小为10*10(不考虑单位问题),假设移动机器人当前所在的位置坐标为[4,2],要前往目标点[1,5]处。

    在这里插入图片描述
    第一步,对当前位置周围的八个相邻栅格进行代价值计算,计算公式为F(n)=G(n)+H(n);
    上下左右移动是一个栅格的距离,为10,对角线移动的话就是根号200了,此处取近似值14。
    G(n)的值为起始点到某一个栅格的最短行进距离,具体可以在下面图解中详细体会。
    H(n)的计算方法一般有三种;
    1:曼哈顿距离;
    2:欧几里得距离;
    3:切比雪夫距离;
    此处采用的是曼哈顿距离进行展示,其计算公式为:
    H(n)=(abs(x1 - x2) + abs(y1 - y2))* 10(栅格宽度)
    懂得了计算公式之后就可以计算出当前栅格周围八个邻域的栅格的代价值分别是多少了。在这里插入图片描述
    随后就在这八个栅格中选择代价值F(n)最小的一个栅格作为下一步前进的目标栅格,此处显然是[3,3],移动机器人移动到[3,3]处后同理再对周围八个相邻栅格进行代价值计算,选取代价值最低的栅格作为下一个前进的栅格,依次往复,直到到达目标位置为止。
    在这里插入图片描述
    注意此时的G(n)值变化的规律,这是A*算法的关键之一!
    在这里插入图片描述
    找到目标点!注意此时图中有3个栅格的总代价值为48,但是只对一个栅格进行了八邻域计算,原因是圈起来的两个栅格是后面才搜索计算到的,与此同时出现了代价值为42的栅格,因此也就舍弃了这两个代价值为48的栅格,请读者必须理解好这一点,这对后续的编程帮助非常大。

    这就是A*算法的寻路原理,值得注意的是,当寻路方向上有障碍物时,会出现同时有多个最小代价值栅格出现的情况,此时应当注意这些栅格都应该被作为当前栅格然后去计算相应邻域栅格的代价值大小。
    如下图:
    第一步:
    在这里插入图片描述
    第二步:
    在这里插入图片描述

    第三步:
    在这里插入图片描述
    栅格[2,3]的八邻域内除去障碍物部分,发现[2,2]栅格的代价值最小,与此同时[4,3]栅格处的代价值也为50,因此下一次搜索栅格时应当把这两个位置的栅格都考虑进去。
    在这里插入图片描述
    跟上一张图片一样,出现了多个代价值为64的栅格,每个都应该搜索其相应的八个邻域,但是由于我的栅格地图画小了,所以就不展示出来了,大家明白意思就好了。
    在这里插入图片描述
    这样就搜索到了目标点。在这里插入图片描述
    然后就可以在在搜索过的所有栅格内找出一条最短路径了!这条路径是局部最优的,但是不一定是全局最优。

    由于篇幅原因,A*算法的编程思路就留到下一篇博客进行介绍了,欢迎大家关注我!

    创作不易,如果这篇文章有帮助到您的地方,欢迎点赞、关注、一键三连,感谢支持!

    相关文章:
    A* 算法的MATLAB源码下载。
    A* 算法的MATLAB源码讲解。
    原创作品,转载请注明出处。

    展开全文
  • A*算法路径的评价公式为F=G+H 其中H为某个已达格子到目的地的估算距离,估算的方法有很多种,比如: 1、曼哈顿距离:即两点水平距离加上竖直距离。比如(x1,y1)到(x2,y2)的曼哈顿距离就是|x2-x1|+|y2-y1|。 2...
  • A*算法的基本原理

    千次阅读 2018-12-11 19:47:38
    A*算法的基本原理 用图的形式表现地图 这里说到的图是graph,而不是map,图(graph)是由一系列的节点和连接节点的边来描述的一种模型.我们使用graph来描述代价地图的时候,只需要把地图中的位置转化为graph中的节点,用...
  • 背景:项目需要接触此算法,以下是一些自学成果,如有不足之处,欢迎指出...​A*算法的详细原理之寻路原理 A*算法的详细原理之结束条件 A*算法的寻路详细步骤 A*算法的举例说明 A*算法的伪代码 A*算法的定义伪...
  • A*算法

    万次阅读 2018-08-21 10:07:28
    二、算法原理 A*算法的原理是设计一个代价估计函数: 其中评估函数 F(n)是从起始节点通过节点 n 的到达目标节点的最小代价路径的估计值,函数 G(n)是从起始节点到 n 节点的已走过路径的实际代价,函数H(n)是...
  • A*算法原理和实现

    千次阅读 2014-12-14 06:48:12
    A*算法是一种启发式搜索算法,就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,对位置的估价是...
  • A算法是一种经典的路径搜索算法,A算法的原理初学者可以去网上搜索算法原理详解,讲得很好 链接:http://www.gamedev.net/reference/articles/article2003.asp 算法牛人或者进阶者,可能只是忘了算法的一些关键点,...
  • A*算法的C#实现

    千次阅读 2018-09-01 21:04:55
     本文的主要内容是讲述A *寻路算法的基本原理,实现步骤以及对应的C#代码,适合读者用于学习A *算法或 使用此代码提供的接口完成游戏中的寻路功能。  详细的A *算法原理,请参照:https://blog.csdn.net/d...
  • A*算法的路径动态规划问题

    千次阅读 2018-08-25 14:08:01
    A算法是一种启发式搜索算法,启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。   1&gt; A*算法...
  • A*算法详解(讲的一级棒 )

    万次阅读 多人点赞 2018-08-23 16:03:28
    虽然掌握了 A* 算法的人认为它容易,但是对于初学者来说, A* 算法还是很复杂的。 搜索区域(The Search Area) 我们假设某人要从 A 点移动到 B 点,但是这两点之间被一堵墙隔开。如图 1 ,绿色是 A ,红色是 B ,...
  • 机器人路径规划_A*算法

    万次阅读 2015-12-17 16:27:41
    机器人路径规划_A*算法 原理 基本思想是:把初始点到达该节点的代价g(n)和从该节点到目标节点的代价h(n)结合起来对节点进行评价: f(n)=g(n)+h(n) 其中:g(n)表示从起始节点到节点n的路径代价 h(n)表示从...
  • A*算法理解(unity C#)

    千次阅读 2018-10-19 17:54:56
    这里只谈A*算法的实现,不谈A算法的优化* 这里的工程是unity版本的,当然理解A*算法是通用的 这里先放上A*算法的unity工程(unity2017.3.1) Github工程 0X01 A*算法基本概念 启发式搜索: 启发式搜索就是在...
  • 终身规划A*算法(LPA*):Lifelong Planning A*

    千次阅读 多人点赞 2018-12-21 21:49:06
    终身规划A*算法(LPA*):Lifelong Planning A*1.描述2.父代节点与子代节点3.起始距离估计4.优先队列5.节点状态及扩展6.初始化运行7.最短路径搜索8.伪代码9.性质10.符号表示11.算法示例推演12.总结13.对公式的进一步...
  • A*算法-路径规划

    万次阅读 热门讨论 2017-08-02 22:31:03
    照着A*算法原理自己用代码实现了下,虽然基本的功能都实现了,不过在实际运用上还有很多可以改善的地方,趁着刚学会A*算法整理下自己的思路。借用热心分享知识的网友图片大致讲解下A*算法的实现过程。 其中绿色...
  • 使用A*算法求最短路径

    千次阅读 2019-09-21 16:13:16
    图论中最短路径的求解之A*算法实现 代码链接 利用A*算法找到从A城市到B城市的最短路径,以及代价,其中A *算法中的h也就是从当前点到目标点的距离已经给出。程序要有通用性,即其中城市A、B可以为下图中任意的两...
  • A*算法详解

    千次阅读 2016-08-09 15:11:49
    第一部分:A*算法简介  写这篇文章的初衷是应一个网友的要求,当然我也发现现在有关人工智能的中文站点实在太少,我在这里 抛砖引玉,希望大家都来热心的参与。   还是说正题,我先拿A*算法开刀,是因为A*在...
  • 路径规划算法A*算法 - 附代码

    千次阅读 2020-10-09 16:50:19
    路径规划算法A*算法 - 附代码 原理部分请参见他人博客(个人认为讲得比较透彻): https://blog.csdn.net/hitwhylz/article/details/23089415 https://www.cnblogs.com/zhoug2020/p/3468167.html Matlab代码 该...
  • A*算法简介

    千次阅读 2014-01-07 23:35:35
    A*算法简介  写这篇文章的初衷是应一个网友的要求,当然我也发现现在有关人工智能的中文站点实在太少,我在这里 抛砖引玉,希望大家都来热心的参与。   还是说正题,我先拿A*算法开刀,是因为A*在游戏中有它很...
  • 广度优先算法、最佳优先算法A*算法寻路程序一个用三种算法寻路的程序,版本VS2015,截图如下:广度优先算法(迷宫为自绘):最佳优先算法A*算法寻路程序:下载链接:...
  • C#实现A*算法

    千次阅读 2018-03-26 23:40:49
    理解A*寻路算法具体过程 这两天研究了下 A* 寻路算法, 主要学习了这篇文章, 但这篇翻译得不是很好, 我花了很久才看明白文章中的各种指代. 特写此篇博客用来总结, 并写了寻路算法的代码, 觉得有用的同学可以看看. ...
  • A*算法实现路径规划matlab(上)

    千次阅读 2020-04-12 14:33:21
    目录A*算法简介1.1 作用与特点1.2 A*算法的基本思想与数学函数模型:1.2.1基本思想1.2.2数学函数模型1.2.3 A*算法算法步骤 A*算法简介 1.1 作用与特点 A* 算法是启发式搜索型的路径规划算法,是一种尽可能基于现有...
  • A*(A星)算法学习资料

    千次阅读 2016-11-22 21:20:57
    A*算法原理_面向初学者 A*算法原理图文详解 A*算法-java代码实现 堪称最好的A*算法
  • 这里写自定义目录标题移动机器人路径规划算法介绍及A*算法详解路径规划算法总结各种算法比较A*算法详解 移动机器人路径规划算法介绍及A*算法详解 随着人工智能的兴起,移动机器人逐渐走入了更多人的视线,ML和DL为...
  • 路径规划(二)、A*算法

    千次阅读 2019-04-12 16:09:17
    路径规划(二)、A*算法(转) 原文章链接
  • 最短路经算法简介(Dijkstra算法A*算法,D*算法)

    万次阅读 多人点赞 2013-01-21 16:30:22
    据 Drew 所知最短路经算法现在重要的应用有计算机网络路由算法,机器人探路,交通路线导航,人工智能,游戏设计等等。美国火星探测器核心的寻路...主要有Dijkstra算法A*(A Star)算法。   动态路径最短路是外界

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 459,378
精华内容 183,751
关键字:

a*算法原理