精华内容
下载资源
问答
  • 路径搜索算法在游戏中非常常见,特别是在 RPG、SLG 中经常用到。在这些游戏中,通过鼠标指定行走目的地,人物或者NPC就会自动行走到目标地点,这就是通过路径搜索或者称为寻路算法来实现的。通俗地说,就是在一张...
  • 假设地图中存在起点和终点,路径搜索算法可以用于搜索起点到终点的路径。在机器人路径规划,或者游戏中都需要用到路径搜索算法。本文介绍一种经典的 A* 算法,和 Dijkstra 算法相比,A* 采用启发式的搜索策略,能够...

    假设地图中存在起点和终点,路径搜索算法可以用于搜索起点到终点的路径。在机器人路径规划,或者游戏中都需要用到路径搜索算法。本文介绍一种经典的 A* 算法,和 Dijkstra 算法相比,A* 采用启发式的搜索策略,能够更快地搜索出最短路径。

    1.前言

    a13a92acd97c7f5c6eb3ef8690df6b64.png

    图中的起点和终点

    给定一个包含起点 (白色圆点) 和终点 (黑色圆点) 的图,有很多条路径可以从起点到达终点,但是很多不是最短路径。如上图所示,黑色虚线为最短路径,红色虚线不是。

    Dijkstra 算法是其中一种求解起点到终点最短路径的算法,在用于无权重图时,Dijkstra 算法就是宽度优先 (BFS) 的方法。A* 对 Dijkstra 进行了优化,引入启发式的搜索策略,可以更快地搜索出最短路径。

    2.Dijkstra算法

    假设起点是 s,终点是 e,Dijkstra 算法的主要包括下面的流程。

    • 步骤一:用一个集合 F 保存已经访问过的节点,初始时 F 只包含起点 s。用一个数组 D 保存起点 s 到其余所有节点的最短路径。在开始时,D 的数值用下面的公式计算。
    3eda84e0047bfd768a944ec61f79b4b3.png

    初始距离数组 D

    • 步骤二:找到一个不在 F 中,并且 D[u] 最小的节点 u。D[u] 就是起点 s 到节点 u 的最短距离,把 u 加入 F。
    • 步骤三:用节点 u 更新数组 D 中的最短距离,如下面的公式。
    10e25071819e0a705b9e8d3701d7fda6.png

    更新距离数组 D

    • 步骤四:如果 F 中已经包含终点 e,则最短路径已找到,否则继续执行步骤二。

    Dijkstra 算法可以用于有权重 (即节点之间的距离是不同的) 和无权重 (节点间距离一样) 的图,如果用于无权重的图,Dijkstra 算法就是 BFS 算法。

    下图展示了用 Dijkstra 算法搜索无权重图最短路径的过程,橙色表示算法搜索过的区域,颜色由浅到深,表示搜索的深度 (先后顺序)。浅橙色表示最先搜索到的节点,而深橙色表示最后搜索到的节点。

    e11ae78abcfac49dcd60e37f118aa817.png

    Dijkstra 算法搜索过程

    3.A* 算法

    A* 算法加入了启发式的搜索策略,在搜索时间上通常优于 Dijkstra 算法。A* 使用了一个估计值 F 代表某一个节点到终点的估计距离,计算公式如下:

    6e2a8128a0eb476ffcbb279ec0faee30.png

    A* 算法估计值 F 计算公式

    另外 A* 包含两个列表,open list 和 close list,open list 保存了等待探索的节点,而 close list 表示已经探索过的节点。

    A* 算法的流程如下:

    • 步骤一:把起点 s 放入到 open list 里面。
    • 步骤二:检查 open list,如果终点 e 在 open list 里面,则路径搜索完成。如果 open list 为空,则说明不存在路径。
    • 步骤三:在 open list 里面选择估计值 F 最小的节点 u,作为当前节点,然后加入 close list 里面。
    • 步骤四:取得所有节点 u 可以直接到达的节点 v,然后更新 open list。更新规则:如果 v 在 close list 里,则不处理;如果 v 不在 open list 里面,则把 v 加入 open list,其对应 F 值为 G(u)+distance(u,v)+H(v);如果 v 在 open list 里面,则检查 v 是否有更小的 F 值 (如果有更小 F 值,就更新 v 的 F 值);
    • 重复步骤二到步骤四,直到终止。

    下面是 A* 搜索最短路径的示例,每一个节点中左边的数字表示 G(n) 即真实距离,右边的数字表示 H(n) 即启发函数计算的距离。F 值就是 G(n)+H(n),在下面的例子中 H(n) 用曼哈顿距离计算 (在下面的例子中等于没有障碍物时,n 到终点 e 的最短距离)。

    a0fc698d6cb8f6bf1d408420a296c918.png

    A* 算法的例子

    4.A* 启发函数的选择与区别

    如果不设置启发函数,则 A* 就是 Dijkstra 算法,这时可以找到最短路径。

    如果启发函数 H(n) 的值一定小于等于 n 到终点的实际距离,则 A* 可以保证找到最短路径。

    如果 H(n) 的值等于 n 到终点的实际距离,则 A* 会直接找到最短路径,而不用扩展搜索额外的节点,此时运行是最快的。

    如果 H(n) 的值有可能大于 n 到终点的实际距离,则 A* 算法不一定可以找到最短路径,但是运行速度会比较快。

    5.参考文献

    Amit’s A* Pages 地址: http://theory.stanford.edu/~amitp/GameProgramming/

    展开全文
  • 先用数组记录地图,可走值为0 ,不可为1;如下 int mg[12][12] = { {1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,1,0,0,1,0,0,0,0,0,1}, {1,1,1,0,1,1,0,0,0,0,0,1}, {1,0,1,0,0,0,0,0,0,0,0,1}, {1,0,0,1,0,0,1,0,0,1,0,...

    在这里插入图片描述
    一 数据结构
    先用数组记录地图,可走值为0 ,不可为1;如下

    int mg[12][12] =
    {
     {1,1,1,1,1,1,1,1,1,1,1,1},
     {1,1,1,0,0,1,0,0,0,0,0,1},
     {1,1,1,0,1,1,0,0,0,0,0,1}, 
     {1,0,1,0,0,0,0,0,0,0,0,1},
     {1,0,0,1,0,0,1,0,0,1,0,1},
     {1,0,0,1,1,0,0,1,0,0,0,1},
     {1,0,1,0,0,0,0,1,1,1,1,1},
     {1,1,0,1,0,1,0,0,0,0,1,1},
     {1,0,1,1,0,1,0,0,1,0,0,1},
     {1,0,1,0,0,0,0,0,0,1,0,1},
     {1,1,0,0,1,0,0,1,1,0,0,1},
     {1,1,1,1,1,1,1,1,1,1,1,1}
    };//数组存贮地图,四周加一道围墙
    
    

    用队列解决此迷宫问题,使用一个顺序队列qu保存走过的方块,队列的结构如下

    
    
    typedef struct
    {
    	int i, j;
    	int pre;
    }Box;//方块类型
    
    typedef struct
    {
    	Box data[100];
    	int front, rear;
    }QuTape;
    
    
    

    顺序队列出列时不会真正删除出队元素,就可以利用他们输出路径;
    二 设计算法
    搜索从(xi,yi),到(xe,ye)的路径过程,将(xi,yi)入队,在qu不为空的时候循环(出对一次,这个出队方块为当前方块,qu.Front为此方块在队列中的下标位置,如果是出口就输出路径,如果不是找4个方位中能走的插入队列qu中,pre设置为上一方块在qu的下标值,将相邻mg置为-1,避免来回搜索。)
    在qu为空的时候 不存在;
    所以算法为

    bool mgpath(int xi, int yi, int xe, int ye)//搜索路径为(xi,yi)到(xe,ye)
    {
    	int i, j, find = 0, di;
    	QuTape qu;//定义顺序队列
    	qu.front = qu.rear = -1;
    	qu.rear++;
    	qu.data[qu.rear].i = xi;
    	qu.data[qu.rear].j = yi;//(xi,yi进队)
    	qu.data[qu.rear].pre = -1;
    	mg[xi][yi] = -1;//赋值-1以免来回搜索
    	while (qu.front != qu.rear && !find)//队列不为空且未找到路径时 循环
    	{
    		qu.front++;
    		i = qu.data[qu.front].i;
    		j = qu.data[qu.front].j;
    		if (i == xe && j == ye)
    		{
    			find = 1;
    			print(qu, qu.front);
    			return true;
    		}
    		for (di = 0; di < 4; di++)
    		{
    			switch (di)
    			{
    			case 0:i = qu.data[qu.front].i - 1; j = qu.data[qu.front].j; break;
    			case 1:i = qu.data[qu.front].i; j = qu.data[qu.front].j + 1; break;
    			case 2:i = qu.data[qu.front].i + 1; j = qu.data[qu.front].j; break;
    			case 3:i = qu.data[qu.front].i; j = qu.data[qu.front].j - 1; break;
    			default:
    				break;
    			}
    			if (mg[i][j] == 0)
    			{
    				qu.rear++;
    				qu.data[qu.rear].i = i; qu.data[qu.rear].j = j;
    				qu.data[qu.rear].pre = qu.front;
    				mg[i][j] = -1;
    			}
    		}
    	}
    	return false;
    
    }
    
    void print(QuTape qu, int front)
    {
    	int k = front, j, ns = 0;
    	cout << endl;
    	do//反向找到最短路径,将该路径上的方块的pre成员设置成-1
    	
    	{
    		j = k;
    		k = qu.data[k].pre;
    		qu.data[j].pre = -1;
    	} while (k != 0);
    	cout << "迷宫路径如下:我的可爱鬼:\n";
    	k = 0;
    	while (k < 100)//正向搜索到pre为-1的方块,即构成正向的路径
    	{
    		if (qu.data[k].pre == -1)
    		{
    			ns++;
    			cout << "(" << qu.data[k].i << "," << qu.data[k].j << ")";
    			if (ns % 5 == 0)//每输出五个后换一行
    				cout << endl;
    		}
    		k++;
    	}
    	cout << endl;
    
    
    
    }
    

    三 设计求解程序
    设计这个调用算法
    int main()
    {
    if (!mgpath(10, 2, 4, 10))
    cout << “无解”;
    }
    四结果
    在这里插入图片描述
    我们试一下吧起点设置为这个点
    在这里插入图片描述
    将数据改为(10,2,3,9);
    在这里插入图片描述
    看到算法准确性很好在这里插入图片描述,第一问,第二问太简单不做解释

    展开全文
  • 假如用一个数组int Map[][]表示地图地图中0 表示可走,1表示障碍,0 的位置只能向上下左右方向走,那么怎么判断两个不同位置之间是否存在可行的路径呢(如果不把存在的路径搜索出来,并且不使用递归算法找出联通...
  • 针对车载导航系统和交通监控系统中的最优路径这一关键技术,研究了矢量电子地图数据结构及其用它表示的真实道路网络的特点。探讨了基于电子地图最优路径求解的启发式代价树搜索算法,并提出了不同情形下的求解策略。
  • A*是一个比较经典的启发式寻路算法,是基于dijkstra算法,但是加入了启发函数,使路径搜索效率更高。实现起来很简单。不过要做到通用性高,比如支持各种不同类型的地图,甚至不仅仅是地图,而是个图结构如解决拼图...

    于图搜索的方法主要包括Dijstra方法,A算法,JPS算法,A算法是Dijstra算法的拓展,JPS算法是A*算法的拓展。

    • A*是一个比较经典的启发式寻路算法,是基于dijkstra算法,但是加入了启发函数,使路径搜索效率更高。实现起来很简单。不过要做到通用性高,比如支持各种不同类型的地图,甚至不仅仅是地图,而是个图结构如解决拼图游戏N-puzzle会用到的,就需要多花点心思。用C++实现的话,可以使用模板来适应不同的需要。也可以使用类继承。 由于A*算法无法消除对称性的问题,所以可以加入tie breaker消除对称性
    • JPS算法有一套规则去打破搜索过程中的的“对称性”,速度与效率较高,但是,JPS仅仅适用于网格地图。

    下面为A*算法的流程图:
    在这里插入图片描述

    1. 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表。
    2. 寻找起点A周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为A。
    3. 从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格。
    4. 检查它所有相邻并且可以到达 (障碍物和 “关闭列表” 的方格都不考虑) 的方格。如果某个相邻方格已经在 “开启列表” 里了, 检查如果用新的路径到达G值是否会更低一些, 如果新的G值更低, 那就把它的 “父方格” 改为目前选中的方格,然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的). 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做。
      就这样, 从 “开启列表” 找出 F 值最小的, 将它从 “开启列表” 中移掉, 添加到 “关闭列表”,再继续找出它周围可以到达的方块, 如此循环下去…
    展开全文
  • 搜索法依靠已知的环境地图以及地图中的障碍物信息构造从起点到终点的路径,包括深度优先和广度优先两个方向。 Dijkasta算法算法使用了广度优先搜索,解决赋权有向图或无向图的单源最短路径问题,算法最终得到一...

    运动规划

    运动规划(Motion Planning)包括路径规划(Path
    Planning)和轨迹规划(Trajectory Planning),通常情况下先进行路径规划,再进行轨迹规划。路径规划和轨迹规划的定义如下:

    • 路径规划只考虑静态障碍环境生成的路径,属于空间路径
    • 轨迹规划考虑了移动机器人本身的运动能力和中途可能的动态障碍,生成一段时间内的动作序列,在路径规划的基础上加入了时间信息,属于时空路径。

    路径规划包括基于图搜索的路径规划算法和基于采样的路径规划算法,下面主要介绍基于图搜索的路径规划算法

    基于图搜索的路径规划算法

    图搜索法依靠已知的环境地图以及地图中的障碍物信息构造从起点到终点的路径,包括深度优先和广度优先两个方向。

    1.Dijkasta算法

    该算法使用了广度优先搜索,解决赋权有向图或无向图的单源最短路径问题,算法最终得到一个最短路径树。

    算法思路
    将地图抽象为Graph数据结构,实际应用场景中,地图各个路径代表的Graph的边的权重不同,例如将距离长的边权重低、拥堵的权重低。算法采用贪心策略,声明了一个数组保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T。

    • 算法开始时,原点s的路径权重设置为0(dis[s]=0),对于顶点s可以直接到达的边(s,m),权重设置为dis[m]=w,同时把其他s不能直接到达的顶点路径长度设置为无穷大。
    • 初始时集合T只有顶点s,然后从dis数组选择最小值,该值为原点s到该值对应顶点的最短路径,并且将该点加入到T中,此时完成一个顶点。
    • 接下来,查看新加入的顶点是否可以到达其他顶点并且查看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,则替换这些顶点在dis中的值。
    • 然后,从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

    代码示意,求如下图的最短路径,起始点为1:
    在这里插入图片描述
    程序输入为邻接矩阵,上图的邻接矩阵为:
    在这里插入图片描述

    def startwith(start: int, mgraph: list) -> list:
        """
        start-为出发点的索引,从0开始
        mgraph-邻接矩阵
        return 列表,每个元素值为start到对应下标点的最短距离
        """
        #passed表示已经过的点,存放已经确定最短距离的点
        passed = [start]
        #nopass存放还不确定最短距离的点
        nopass = [x for x in range(len(mgraph)) if x != start]
        dis = mgraph[start]
        
        while len(nopass):
            idx = nopass[0]
            for i in nopass:
                if dis[i] < dis[idx]: idx = i
    
            nopass.remove(idx)
            passed.append(idx)
    
            for i in nopass:
                if dis[idx] + mgraph[idx][i] < dis[i]: 
                    dis[i] = dis[idx] + mgraph[idx][i]
        return dis
     
     if __name__ == "__main__":
        inf = 10086
        mgraph = [[0, 1, 12, inf, inf, inf],
                  [inf, 0, 9, 3, inf, inf],
                  [inf, inf, 0, inf, 5, inf],
                  [inf, inf, 4, 0, 13, 15],
                  [inf, inf, inf ,inf, 0, 4],
                  [inf, inf, inf, inf ,inf, 0]]
    
        dis = startwith(0, mgraph)
    

    运行程序最终得到结果[0,1,8,4,13,17],分别为起始点1到节点1,2,3,4,5,6的最短路径。

    2. A*算法

    A*算法核心为估价函数的设计,f(n)=g(n)+h(n)f(n)=g(n)+h(n),其中g(n)g(n)为耗散函数,表示从起始点到节点n的实际代价;h(n)h(n)为启发函数,表示节点n到目标节点ngoaln_{goal}的估计代价,f(n)f(n)
    表示起始节点经由节点n到目标节点的估计代价。

    g(n)g(n)可以定义为移动代价与代价因子的乘积;h(n)h(n)的一个计算方式是曼哈顿距离,以栅格地图为例,可以表示为当前方格到目标方格的水平距离+当前方格到起始点的垂直距离。正因为可以通过预估h(n)h(n)降低走弯路的可能性,因此A被称为启发式算法。当h(n)=0h(n)=0时,A算法即为Dijksatra算法。

    • 算法定义一个开放列表,用于记录所有可考虑选择的格子;定义一个封闭列表,用于记录所有不再考虑的格子;
    • a 当开始点记录为P
    • b 将当前点P放入封闭列表
    • c 搜寻点P所有临近点,加入某临近点既没有在开放列表或封闭列表里面,计算出该邻近点的F值,并设置父节点为P,然后将其放入开放列表;
    • d 判断开放列表是否已经空了,如果没有说明在达到结束点前已经找完了所有可能的路径点,寻路失败,算法结束;否则继续
    • e 从开放列表拿出的一个F值最小的点,作为驯鹿路径的下一步
    • f 判断该点是否为结束点,如果是寻路成功,算法结束;否则继续;
    • g 将该点设为当前点P,跳回步骤c

    基于栅格实现了A*算法演示,算法参考地址:
    Astar

    3. Hybrid A*

    Hybrid A Star与A Star相比,需要考虑物体的实际运动约束,但继承了A Star的思想,比如open表和close表,还有g(n)g(n)h(n)h(n),但花费定义比AStar定义复杂。例如g(n)g(n),AStar仅定义了走过的距离,Hybrid AStar中考虑了很多其他因素,比如转向角的改变、是否倒车、车辆行驶方向是否改变等。Hybrid主要特点如下:

    • 考虑物体的实际运动方向约束,不像AStar假定所有相邻节点都可以顺利专一
    • AStar物体总是出现栅格中心,Hybrid AStar不一定
    • Hybrid AStar为连续路径,使用了Reeds-Shepp曲线进行了路线规划
    • 启发函数h(n)h(n)不同于AStar中的欧式距离,选择由AStar所得的到达终点的花费作为Hybrid AStar的预期花费

    4. JPS算法

    JPS是对A*算法的改进。

    A*算法在扩展节点时会把节点的所有邻居考虑进去,导致open表中含有大量节点,搜索效率变慢。
    JPS满足以下需求:

    • 无遮挡条件下存在很多等价路径,在起点到终点仅仅取一个路径,该路径外的其他节点不放入open表中
    • 直线方向上中途的点不放入open表,仅放入每段直线子路径的起点和终点
      在这里插入图片描述
      如图所示,JPS搜索到的节点为跳跃性的,这些节点为需要改变行走方向的关键节点,成为Jump Point。
      JPS算法中包含强迫邻居和跳点两个概念,解释如下:

    4.1强迫邻居

    对于栅格地图中的某个节点x,共有8个邻居节点,假设其中存在障碍,且x的父节点p经过x到达n比不经过x到达n的任意路径的代价小,成为n为x的强迫邻居。如图所示,黑色为障碍物,红圈为强迫邻居。
    在这里插入图片描述

    4.2跳点

    当节点满足一下三个条件之一时,为跳点:

    • 当前节点为起点或终点
    • 当前节点至少有一个强迫邻居
    • 父节点在斜方向,当前节点的水平或垂直方向上有节点满足前两个条件。
      在这里插入图片描述
      如图所示,黄色节点的父节点在斜方向,右方向发现一个蓝色跳点,因此黄色节点应为跳点。(对于水平或垂直方向,(1,1)对应的水平方向为(1,0),垂直方向为(0,1)。

    4.3 JPS寻路算法

    JPS步骤如下:

    • 在open表中取一个权值最低的节点,开始搜索(与A*相同)
    • 搜索时,先进性直线搜索(此时为跳跃搜索,沿着直线方向一直搜下去,直到搜到跳点或者障碍),然后再斜向搜索(只搜索一步),如果期间某个方向搜索到跳点或者碰到障碍物,当前方向完成搜索,搜到跳点则加入open表
    • 若斜方向未完成搜索,斜方向前进一步,重复上述过程
    • 若所有方向均已完成搜索,当前节点搜索完毕,将其从open表中移除,加入close表
    • 重复取open表权值最低的节点进行搜索,直到open表为空或者找到终点
      JPS

    5. JPS+

    JPS+算法与JPS算法相比,增加了预处理过程,从而使寻路更加快速。

    5.1预处理

    首先对地图的每个节点进行跳点判断,找到所有主要跳点,然后对每个节点进行直线可达性判断并进行记录。当满足可达性时,记录好跳点的直线距离和斜向距离,剩余各个方向如果不可到达记为0或者负距离。此时,每个格子8个方向均记录。

    (0距离表示对应方向移动一步就会碰到障碍,-n表示移动n+1步会碰到障碍)

    5.2 JPS+过程

    1. 得到预处理后的数据
    2. 对于某个搜索方向,对于正数距离n,直接将n步远的节点作为跳点加入openlist
    3. 对于对于0距离,不在该方向进行搜索
    4. 对于负数距离-n,直接将n步远的节点进行一次跳点判断

    6.D*算法

    AA^*算法类似,DD^*算法通过维护一个Open表对场景中的路径节点进行搜索,但DD^*不是从起始点开始搜索,而是以目标点为起始,通过将目标点置于Open表中开始搜索,直到机器人当前的位置节点由队列中出队。

    D*算法中每个节点被称为state,共分为new、open和closed三类,最开始state标记为new,加入open表中置为open,从open表中移走后被置为closed。

    6.1符号描述

    • 当前节点为X
    • 终点为G
    • b(X)=Yb(X)=Y为后向指针,即Y为X的下一个节点
    • c(X,Y)表示X到Y的花费
    • h(G,X)为DD^*的估计函数
    • AA^*不同的是DD^*包含了一个key函数,表示最小的h值,当更新过当前节点后,如当前节点为new,令key=h;若当前节点为open,k为当前k和最新的h的最小值;若当前节点为closed,取当前h和最新的h的最小值,该值表示当前节点在全图环境中到达g点的最小代价。

    6.2 算法思想

    DD^*包括两部分,process-state和modify-cost。DD^*算法的特点是反向搜索,从目标点开始搜索过程,并可以在动态环境中进行寻路。

    首次搜索时,使用Dijkstra进行搜索,直到搜索到起点,搜索结束后,搜索过的节点的state置为closed,每个节点的k=h,其父节点为邻域中k值最小的那个。此时,出现动态变化时我们可以利用计算的图尽快修改路径。

    当规划路径的点遇到了障碍,DD^*将会对其进行处理,否则仍按照规划的路径到达。遇到障碍时,即当前点的父节点为障碍,修改其h值并将其放入open表,但其k值仍然不变,此时k=min(k,newh)k=min(k, new_h),该点会被优先取出并扩散展开。

    Process-State
    扩散过程需要使用process-state(节点处理函数),当扩散到某个节点后,计算后的h值不必其上次的k值小,该点结束对外扩散,伪代码如下:

    1:X=Min-State() #取所有节点中k值最小的
    2if X=Null then return -1 #如果open表为空,结束
    3:K_old=Get-Kmin();Delete(X) #得该点k值,并将该点弹出Openlist队列
    
    4if K_old<h(x),  then- #比较该点h值与K值,(h值上升状态)
    5: 		for each neighbor Y of X: #遍历X的邻域节点Y
    6: 			if h(Y)<= K_old and h(x)>h(y)+c(x,y)  #Y的不处于上升状态,且用其更新x后,h的h值更小
    7: 				b(x)= Y; h(x)=h(y)+c(x,y)  #更新x的父节点及其h值
    
    8: if K_old=h(x) then  #比较该点h值与K值,(h值未变化状态)
    9: 		for each neighbor Y of X: #遍历邻域节点Y
    10: 		if t(Y)= New or  #Y的state为new添加到Openlist并处理
    11: 		(b(Y)= X and h(Y)!=h(x)+c(x,y)or #Y是X的子节点,并且其h值不需要改变
    12: 		(b(Y)= X and h(Y)>h(x)+c(x,y))then #Y不是X的子节点,并且其h值可以变得更小
    13: 		 b(Y)= X; insert(Y,h(x)+c(x,y)#将X作为Y的父节点,修改其h值,并将Y点添加到Openlist中
    
    14else #比较该点h值与K值,(h值下降状态),即k_old>h(x)
    15: 	for each neighbor Y of X: #遍历邻域节点Y
    16: 		if t(Y)= New or #Y是首次添加到Openlist并处理
    17: 			(b(Y)= X and h(Y)!=h(x)+c(x,y))then #Y是X的子节点,并且其h值不需要改变
    18: 				b(Y)= X; insert(Y,h(x)+c(x,y)#将X作为Y的父节点,修改其h值,并将Y点添加到Openlist中
    19: 		else
    20: 			if((b(Y)= X and h(Y)>h(x)+c(x,y))then #Y不是X的子节点,并且其h值可以变得更小
    21: 			insert(X,h(x)#修改X的h值,并将其点添加到Openlist中
    22: 			else
    23: 				if((b(Y)= X and h(Y)>h(x)+c(x,y) and #Y不是X的子节点,并且其h值可以变得更小
    24: 				t(Y)= Closed and h(Y)>K_old then -#Y不在Openlist中,且h值处于上升状态
    25: 				insert(Y,h(Y)-#修改Y的h值,并将其点添加到Openlist中
    25: return Get-Kmin() #返回该点k值
    

    Modify-cost
    该函数为两个节点之间的距离处理函数

    L1:c(X,X)=cval #重置两节点间距离
    L2:if t(X)=Closed then insert(X,h(x)) #X不在Openlist中,则修改其h值,并添加到Openlist
    L3:return Get-Kmin() #返回X点k值
    

    对于上述程序的理解
    process-state用于计算到目标G的最优路径,首先从open表中选取k值最小的节点并将其移除,对该点进行分类,遍历其邻域,查看是否需要修改父节点、h值以及添加到open表中,分类大致如下:

    a)当kold<h(x)k_{old}<h(x)时,说明该点受到了障碍的影响,导致h值升高,遍历其邻域的点y,若y点的h值没有上升,并且x的h值能够通过该点变得更小,则修改x的父节点为y,重置其h值;
    b)当kold=h(x)k_{old}=h(x)时,处于第一遍遍历的阶段,或者该节点并没有受到障碍的影响,遍历其邻域的点y。
    若y是第一次被遍历到,或者y的父节点时x,但h(y)和h(x)+c(x,y)的值不想当,由于kold=h(x)k_{old}=h(x),表明h(y)被更改而h(x)还没有变;或者y的父节点不是X,但让X成为y的父节点将拥有更小的h(y)值。发生上述情况需要根据x的h值调整y的h值,并将x作为y的父节点,将y添加到open表中。
    c) 当kold>h(x)k_{old}>h(x)时,说明节点收到影响,遍历其领域的点y

    • 若y为第一次遍历到的点,或者或者x是y的父节点,但是h(y)和h(x)+c(x,y)值却不等,这说明h(x)被更改了,但是h(y)还没有变,上述情况应该应该根据x的h值调整y的h值,并将x作为y的父节点,并将y添加到open表中;
    • 如果y的父节点不是X,但是让X成为其父节点将拥有更小的h(y)值,上述情况应该应该调整x的h值,并将x添加到open表中;
    • 如果y的父节点不是X,但是让Y成为X父节点,X将拥有更小的h(x)值,并且y被已经被open表移除,且h(y)值在上升(即y受到影响),上述情况应该应该调整y的h值,并将y添加到open表中。

    算法参考地址:
    Dstar

    参考文献
    [1] https://zhuanlan.zhihu.com/p/51099376
    [2] https://www.cnblogs.com/KillerAery/p/9231511.html
    [3] https://www.cnblogs.com/KillerAery/archive/2020/06/17/12242445.html
    [4] https://blog.csdn.net/qq_36458461/article/details/106106254

    展开全文
  • 在上一篇基于postGIS的室内地图最短路径算法二中,在路径搜索中加入了楼层分析的概念。在使用过程中会产生一个问题就是,只给出了路网上的线,没有给出起点、终点到路网的连线,用户体验很差。 在这里加入了起点...
  • 常用的地图导航和路径规划算法

    万次阅读 2018-12-06 19:27:31
    作者:李传学 ...明确一点,基本的图搜索算法dijkstra是无法满足互联网地图检索实时响应这种性能要求,所以各家公司都有各自的预处理方法:分层或者预计算。具体采用何种方式,这取决于采取的加速算法相...
  • 广度优先搜索算法在Unity网格地图中实现最短路径内容学习取自于[B站BeaverJoeUP主](https://www.bilibili.com/video/BV1X54y1D7Z4?t=3445) 内容学习取自于B站BeaverJoeUP主 最终效果展示图 鼠标点击方块 然后球向...
  • 1 # 版本2,2018—04—092 # 所有节点的g值并没有初始化为无穷大3 # 当两个子节点的f值一样时,程序选择最先搜索到的一个作为父节点加入closed4 # 对相同数值的不同对待,导致不同版本的A*算法找到等长的不同路径5 #...
  • 作者:邬杨明1 import numpy2 from pylab import *34 # 定义一个含有障碍物的20×20的栅格地图5 # 10表示可通行点6 # 0表示障碍物7 # 7表示起点8 # 5表示终点9 map_grid = numpy.full((20, 20), int(10), dtype=...
  • RRT路径规划算法

    千次阅读 2019-08-29 21:43:42
    RRT路径规划算法地图RRT算法原理路径平滑处理总结 RRT(Rapidly-Exploring Random Tree)算法是一种基于采样的路径规划算法,常用于移动机器人路径规划,适合解决高维空间和复杂约束下的路径规划问题。基本思想是以...
  • 路径搜索是复杂的。为什么涉及到路径搜索就产生麻烦了?考虑以下情况:image物体(unit)最初位于地图的底端并且尝试向顶部移动。物体扫描的区域中(粉红色部分)没有任何东西显示它不能向上移动,因此它持续向上移动...
  • 常见的其他搜索算法,IA*(迭代A*),内存限定A*,分层路网A*(将高速路网构建成一个新的路网), D*(针对不确定环境下的动态路径算法,来与机器人路径选择)    3.3 路径规划算法分析与设计导航终端动态规划...
  • 提出一种用于矿井环境中人员及其他活动目标位置跟踪的定位算法,分析了...详细描述了基于路径搜索的定位算法的实现。采用ZigBee技术构建本算法的实现平台,实验结果表明:算法定位准确、运算量小,适合矿井下的大规模部署。
  • 1 # 版本2,2018—04—09 ... 4 # 对相同数值的不同对待,导致不同版本的A*算法找到等长的不同路径 5 # 最后closed表中的节点很多,如何找出最优的一条路径 6 # 撞墙之后产生较多的节点会加入closed...
  • 蚁群算法路径搜索初探

    千次阅读 2018-05-18 17:03:47
    最近任务需要,学习路径搜索,先是看了A*算法,然后自己又研究了下蚁群算法。 我是在三维网格地图中实现的路径搜索,用的点而不是边来标记信息素的,主要是觉得边要麻烦一些,感兴趣的可以自己实现边标记信息素。...
  • 深度搜索算法查找最短路径

    千次阅读 2019-02-27 11:05:04
    从图中可以得到一个5*5的二维矩阵,利用深度搜索算法,求出最短路径。从最后的运行结果,可以直观的看出搜索的过程 代码实现如下: #include "pch.h" #include &lt;stdio.h&gt; #include &...
  • 利用python及pygame模块建立复杂地图,验证加入初始引力势场和陷阱搜索的改进Q-learning算法路径规划效果。仿真实验表明,改进算法能在较少的迭代次数后,快速有效地到达目标位置,且路径较优。
  • 作者:邬杨明 1 import numpy ... 4 # 定义一个含有障碍物的20×20的栅格地图 5 # 10表示可通行点 6 # 0表示障碍物 7 # 7表示起点 8 # 5表示终点 9 map_grid = numpy.full((20, 20), int(10), dtype=n...
  • 地图上有很多个城市,已知各城市之间距离(或者是所需时间,后面都用距离了),一般问题无外乎就是以下几个: 从某城市到其余所有城市的最短距离【单源最短路径】 所有城市之间相互的最短距离【任意两点最短路径】 ...
  • 用 matlab 仿真A*路径规划算法,有子函数可修改。解压后运行a_star.m即可。生成迷宫中的最短的路径,以及路径搜索的过程。
  • 研究了基于A*算法的适合人步行行走的山地环境下三维地图最优路径规划算法及实现. 本文考虑了三维山地无路网信息覆盖的条件较差环境, 对A*算法进行改进, 并利用三维地形DEM数据计算出一条相对平缓且长度 较短的三维...
  • 在由栅格法构建的环境地图中,利用A*算法进行路径搜索时存在搜索范围广、搜索速度慢、路径曲折等问题.针对栅格地图及具有四向移动机器人的特点,从搜索方向、启发函数构建、机器人加减速以及转向成本等几个方面对A*...
  • Astar A*算法 最短路径算法

    千次阅读 2018-12-10 20:23:31
    通常情况下,迷宫寻路算法可以使用深度优先或者广度优先算法,但是由于效率的原因,不会直接使用这些算法,在路径搜索算法中最常见的就是A*寻路算法。使用A*算法的魅力之处在于它不仅能找到地图中从A到B的一条路径,...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 361
精华内容 144
热门标签
关键字:

地图路径搜索算法