精华内容
下载资源
问答
  • a*算法流程图(只是流程图)A*算法是一种在静态路网中求解最短路径最有效的直接搜索方法,也是解决许多其他搜索问题的有效算法。算法中的距离估算值与实际值越接近,扩展的节点数越少, 搜索速度越快。
  • C++版本A*算法基于路网图A*寻路算法算法概述流程图伪代码C++实现 C++版本A*算法基于路网图A*寻路算法算法概述流程图伪代码C++实现 A*寻路算法 算法概述 从起点start到达目标点target并经过点x的估计距离长度表示为...

    A*寻路算法

    算法概述

    1. 从起点start到达目标点target并经过点x的估计距离长度表示为f(x) = g(x) + h(x),该公式是A*算法的核心公式。

    2. g(x)表示实际路网距离,h(x)表示从点x到target的估值,一般用欧式距离或者曼哈顿距离表示。

    3. A*算法通过不断的选择估计距离f(x)最小的节点,逐渐构建最短路径。

    4. 用两个表open表(按照F值从大到小排序,若相等按照G值从大到小排序)和close表来存储选择过程。

    5. 算法搜索过程
      核心

      两个集合:Open,Closed和一个公式:f(n)=g(n)+h(n)。其中Open,Closed都是存储节点的集合,Open存储可到达的节点,Closed存储已经到达的节点;而公式f(n)=g(n)+h(n)则是对节点价值的评估,g(n)代表从起点走到当前节点的成本,也就是走了多少步,h(n)代表从当前节点走到目标节点的距离,即不考虑障碍的情况下,离目标还有多远。至于f(n),则是对g(n)和h(n)的综合评估,我们应该尽量选择步数更少,离目标更近的节点,那么f(n)的值越小越好。

      搜索思路

      开始时,Closed表为空,Open表仅包括起始节点,每次迭代中,A*算法将Open表中具有最小代价之的节点去除进行检查,检查后的节点放入Closed表,如果这个节点不是目标节点,那么考虑该节点的所有相邻节点。对于每个相邻节点按下列规则处理;

      (1)如果相邻节点既不在Open表中,又不在Closed表中,则将它加入Open表中;
      (2)如果相邻节点已经在Open表中,并且新的路径具有更低的代价值,则更新它的信息;
      (3)如果相邻节点已经在Closed表中,那么需要检查新的路径是否具有更低的代价值,如果是,那么将它从Closed表中移出,加入到Open表中,否则忽略。(这里需要检查Closed表是因为要防止由于h(n)计算不准确而导致的误差)

      重复上述步骤,直到到达目标节点。如果在到达目标之前,Open表就已经变空,则意味着在起始位置和目标位置之间没有可达的路径。

    流程图

    引用博客链接: link.

    在这里插入图片描述

    伪代码

    // A* algorithm Pseudo code block
     A*(int start ,int target)
    {
    	Open = [start];
    	Closed = []
    while (Open表非空)
    {
    	从Open中取得一个节点X,并从OPEN表中删除。
    	 if (X是目标节点)
      {
        根据前向father求得路径PATH以及最短路径cost;
        return 路径PATH;
      }
    	Open.pop();
    	Close.push(X);
      for (每一个X的邻节点Y)
      {
    		if (Y不在Open表和Close表中)
      	  {
             	求Y的估价值G并计算FH;
    			并将Y插入Open表中;
    	  }else if (Y在Open表中)
     		{
    				if (Y的估价值小于Open表的估值G)
    				update Open表中的估值;  
    		}  else //Y在Close表中
          {
             if (Y的估值小于CLOSE表的估值G)
           {
    			update Close表中的估值;
    			从Close表中移出节点,并放入Open表中;
    		}
    	}	//end for
    	sort(),按照估价值将Open表中的节点排序;
     }   //end while
    }     //end function
    

    C++实现

    // An highlighted block
    struct Node{
    	int id;
    	double x,y;
    	//int id,x,y;
    	vector<int> adjnodes;
    	vector<int> adjweight;
    	double F = 0.0;
    	double G = 0.0;
    	double H = 0.0;
    	int father;
    	//Constructors
    	Node(): id(-1),x(-1), y(-1){}
    	Node(int a,double b,double c): id(a),x(b), y(c){}
    };
    map<Node>Nodes;
    // return Astar_p2p(int s, int t)
    double Astar(int S,int T){
    	if(S == T) return 0.0; 
    	vector<Node> openlist;
    	vector<Node> closelist;
    	openlist.clear();
    	closelist.clear();
    	Nodes[S].father = -1; 
    	Nodes[S].H = Euclidean_Dist(S,T);
    	Nodes[S].F = Nodes[S].G + Nodes[S].H; 
    	openlist.push_back(Nodes[S]);
    	while(!openlist.empty()){
    		Node current = openlist.back();//min_F node
    		if(current.id == T){
    			return current.F;
    		}
    		openlist.pop_back();
    		closelist.push_back(Nodes[current.id]);
    		vector<int>neighbors;
    		for(int i=0;i<Nodes[current.id].adjnodes.size();i++){
    			neighbors.push_back(Nodes[current.id].adjnodes[i]);
    		}
    		
    		for(int neighbor:neighbors){
    			bool b1 = false,b2 = false;
    			if( !(b1 = in_list(neighbor,openlist))&&!(b2 = in_list(neighbor,closelist))){//not in both
    				Nodes[neighbor].father = current.id;
    				double w = 0.0;
    				for (int i = 0; i < Nodes[current.id].adjnodes.size(); i++) {
                		if(Nodes[current.id].adjnodes[i] == neighbor)
                			w = (double)Nodes[current.id].adjweight[i];
                	}
                	Nodes[neighbor].G = Nodes[current.id].G + w; 
                	Nodes[neighbor].H = Euclidean_Dist(neighbor,T);
                	Nodes[neighbor].F = Nodes[neighbor].G + Nodes[neighbor].H; 
                	openlist.push_back(Nodes[neighbor]);
    			}else if(b1){// in open update G & F
    				double w = 0.0;
    				for (int i = 0; i < Nodes[current.id].adjnodes.size(); i++) {
                		if(Nodes[current.id].adjnodes[i] == neighbor)
                			w = (double)Nodes[current.id].adjweight[i];
                	}
    				double g = w + Nodes[current.id].G;
    				double f = g + Nodes[neighbor].H;			
    				if(g < Nodes[neighbor].G){
    						for(vector<Node>::iterator it = openlist.begin();it!=openlist.end();){
    							if((*it).id == neighbor)
    								it = openlist.erase(it);
    							else
    								++it;
    						}
    					Nodes[neighbor].father = current.id;
    					Nodes[neighbor].F = f;
    					Nodes[neighbor].G = g ;
    					openlist.push_back(Nodes[neighbor]);
    				}
    			}else{//in close if g<G delete and into open
    				double w = 0.0;
    				for (int i = 0; i < Nodes[current.id].adjnodes.size(); i++) {
                		if(Nodes[current.id].adjnodes[i] == neighbor)
                			w = (double)Nodes[current.id].adjweight[i];
                	}
    				double g = w + Nodes[current.id].G;
    				double f = g + Nodes[neighbor].H;			
    				if(g < Nodes[neighbor].G){
    						for(vector<Node>::iterator it = closelist.begin();it!=closelist.end();){
    							if((*it).id == neighbor)
    								it = closelist.erase(it);
    							else
    								++it;
    						}
    					Nodes[neighbor].father = current.id;
    					Nodes[neighbor].F = f;
    					Nodes[neighbor].G = g ;
    					openlist.push_back(Nodes[neighbor]);
    				}
    			}// end else	
    	   }//end for
    		sort(openlist.begin(),openlist.end(),cmp);	
    	}//end while
    } 
    
    展开全文
  • A算法与D算法 1. A* (Informed Search) 1.1 Evaluation Function: f(n)=g(n)+h(n) operating cost function: g(n) Heuristic fucntion: h(n) (相较于Dijkstra 算法 增加了启发式函数 来...1.2 A*算法运行中需要注意

    A算法与D算法

    1. A* (Informed Search)

    1.1

    Evaluation Function: f(n)=g(n)+h(n)
    operating cost function: g(n)
    Heuristic fucntion: h(n)
    (相较于Dijkstra 算法 增加了启发式函数 来确定最优路径)
    可用启发式函数:曼哈顿距离 欧式距离 对角距离

    流程图如下图所示:
    在这里插入图片描述
    Open list: 存储扩展的节点
    close list: 存储已经搜索过的节点

    1.2 A*算法运行中需要注意的问题
    在这里插入图片描述

    • 从root开始, 圆圈内表示该节点启发式函数数值,连线上表示代价函数数值
    • 每一个节点的启发式函数是独立的,不与之前节点启发式函数大小相关
    • 途中节点的代价函数数值总是由root 出发的代价函数总和
    • 每一步搜索时将open list中f(n)最小的节点添加到close list 中,要注意close list中要带上f(n)值进行存储,以便于最终到达goal时判断最优路径
    • close list中出现goal节点即为停止搜索flag

    1.3 A* replanner (用于未知地图情况)

    在这里插入图片描述

    • 流程右半部分为正常A* 流程, 从ROOT出发在已知地图中进行搜索,判断是否到达GOAL
    • 如果没有到达GOAL,则判断是否与一直地图存在差异
    • 若与已知地图存在差异,则更新地图,并使用更新后地图继续搜索
    • 若与已知地图没有差异,说明没有动态障碍物产生,继续按照原地图搜索
    • 知道到达GOAL停止

    2. D*算法 (Stentz 1994)

    2.1 介绍

    • 又称动态A搜索 (Dynamic A Search)
    • 过程中节点间代价函数会发生改变 (replanning online)
    • 等价于A* replanner
    • 使用Dijkstra 进行初始规划,并通过接受实时数据来加快规划速度,针对部分地图区域来实现动态避障
    • 比A* replanner 更高效 (大范围复杂环境扩展中)
    • 用于在第一次逆向搜索获得最优路径并记录节点间关系后,处理动态问题
    • h:到GOAL代价 k:该点最小的h
    • 使用k原因:k用于open list排序,说明此节点之前为最优节点,可在此节点周围进行搜索,加快重新规划的速度

    在这里插入图片描述2.2 步骤

    • 初始阶段,所有节点均为NEW(代表第一次遍历到),h和k值均为到GOAL的距离
    • 从GOAL出发,将GOAL添加到open list中,且它的h=0 k=0 (k值为队列中优先度)
    • 将GOAL pop出open list,扩展到GOAL的相邻节点,因为此时节点均为NEW,所以k=h=到GOAL的距离,将相邻节点推入open list中
    • 不停寻找相邻节点,迭代,推入推出open list
    • !!!若此时遇到节点处为障碍物,此节点h值很高,因为为NEW,所以k=h=high value
    • 当root被扩展后,则搜索结束
    • 根据h的梯度确定最优路径 (方向指向临间节点中k值最小的节点)
    • !!当计划路径上某点被阻碍,因为是反向指针,可以定位到被堵节点的上一节点(D*速度快的原因)
    • 障碍物节点h升高,RISE态,需搜索使得该点的h降低,回复lower state
    • 将该障碍点和临间节点加入open list中,进行搜索,如果无法使该点转为lower态,说明临间通过节点无法成功绕开障碍物,则将该影响扩散
    • 该点的子节点受到影响,h变大,并进行判断
    • 若 k_old<h(x): 该节点x处于raise状态,如果在x周围找到一个临间节点,使得h.y+c(x,y)更小,那就修改x的父节点,重置其h的值(父节点h+节点间距离)。
    • 若k_old=h(x): 该节点x处于lower的状态,并没有受到障碍影响,或者还在第一遍遍历的阶段。
    展开全文
  • 讲解了A*算法流程图和算法框图,并利用A*算法求解N数码难题,很好的体现了人工智能领域的启发式搜索算法思想.
  • 基于A*算法的最优路径搜索实例及程序说明文档。包含基于A*算法的最优路径搜索实例;程序说明文档包含算法设计说明、程序设计说明、类图、流程图
  • A* 算法

    2020-05-14 15:52:12
    A*算法是一种常用的最短路径算法。它的算法流程如下: 1、将地图栅格化,并初始化open_set和close_set。 2、将起始点放入close_set,假如起始点的邻近点既没有在开放列表或封闭列表里面,计算该邻近点的代价函数F = G...

    A*算法是一种常用的最短路径算法。它的算法流程如下:
    1、将地图栅格化,并初始化open_set和close_set。
    2、将起始点放入close_set,假如起始点的邻近点既没有在开放列表或封闭列表里面,计算该邻近点的代价函数F = G + H,并将其加入open_set,记录它的父节点。
    4、判断open_set是否为空,如果没有说明在达到结束点前已经找完了所有可能的路径点,寻路失败,算法结束;否则继续。
    5、访问open_set中代价最小的那个节点,将其从open_set移入close_set。
    6、判断该点是否为结束点,如果是,则寻路成功,算法结束;否则继续2。

    这里的代价函数:F = G + H,G为到起始点的距离,H为启发距离,与到目标点的距离相关。

    参考实现:https://github.com/AtsushiSakai/PythonRobotics/tree/master/PathPlanning/AStar

    """
    
    A* grid planning
    
    author: Atsushi Sakai(@Atsushi_twi)
            Nikos Kanargias (nkana@tee.gr)
    
    See Wikipedia article (https://en.wikipedia.org/wiki/A*_search_algorithm)
    
    """
    
    import math
    
    import matplotlib.pyplot as plt
    
    show_animation = True
    
    
    class AStarPlanner:
    
        def __init__(self, ox, oy, reso, rr):
            """
            Initialize grid map for a star planning
    
            ox: x position list of Obstacles [m]
            oy: y position list of Obstacles [m]
            reso: grid resolution [m]
            rr: robot radius[m]
            """
    
            self.reso = reso
            self.rr = rr
            self.calc_obstacle_map(ox, oy)
            self.motion = self.get_motion_model()
    
        class Node:
            def __init__(self, x, y, cost, pind):
                self.x = x  # index of grid
                self.y = y  # index of grid
                self.cost = cost
                self.pind = pind
    
            def __str__(self):
                return str(self.x) + "," + str(self.y) + "," + str(
                    self.cost) + "," + str(self.pind)
    
        def planning(self, sx, sy, gx, gy):
            """
            A star path search
    
            input:
                sx: start x position [m]
                sy: start y position [m]
                gx: goal x position [m]
                gy: goal y position [m]
    
            output:
                rx: x position list of the final path
                ry: y position list of the final path
            """
    
            nstart = self.Node(self.calc_xyindex(sx, self.minx),
                               self.calc_xyindex(sy, self.miny), 0.0, -1)
            ngoal = self.Node(self.calc_xyindex(gx, self.minx),
                              self.calc_xyindex(gy, self.miny), 0.0, -1)
    
            open_set, closed_set = dict(), dict() ##已搜索和未搜索的两个集合
            open_set[self.calc_grid_index(nstart)] = nstart
    
            while 1:
                if len(open_set) == 0:
                    print("Open set is empty..")
                    break
                ## 寻找代价最小点
                c_id = min(
                    open_set,
                    key=lambda o: open_set[o].cost + self.calc_heuristic(ngoal,
                                                                         open_set[
                                                                             o]))
                current = open_set[c_id]
    
                # show graph
                if show_animation:  # pragma: no cover
                    plt.plot(self.calc_grid_position(current.x, self.minx),
                             self.calc_grid_position(current.y, self.miny), "xc")
                    # for stopping simulation with the esc key.
                    plt.gcf().canvas.mpl_connect('key_release_event',
                                                 lambda event: [exit(
                                                     0) if event.key == 'escape' else None])
                    if len(closed_set.keys()) % 10 == 0:
                        plt.pause(0.001)
    
                if current.x == ngoal.x and current.y == ngoal.y:
                    print("Find goal")
                    ngoal.pind = current.pind
                    ngoal.cost = current.cost
                    break
    
                # Remove the item from the open set
                del open_set[c_id]
    
                # Add it to the closed set
                closed_set[c_id] = current
    
                # expand_grid search grid based on motion model
                for i, _ in enumerate(self.motion):
                    node = self.Node(current.x + self.motion[i][0],
                                     current.y + self.motion[i][1],
                                     current.cost + self.motion[i][2], c_id)
                    n_id = self.calc_grid_index(node)
    
                    # If the node is not safe, do nothing
                    if not self.verify_node(node):
                        continue
    
                    if n_id in closed_set:
                        continue
    
                    if n_id not in open_set:
                        open_set[n_id] = node  # discovered a new node
                    else:
                        if open_set[n_id].cost > node.cost:
                            # This path is the best until now. record it
                            open_set[n_id] = node
    
            rx, ry = self.calc_final_path(ngoal, closed_set)
    
            return rx, ry
    
        def calc_final_path(self, ngoal, closedset):
            # generate final course
            rx, ry = [self.calc_grid_position(ngoal.x, self.minx)], [
                self.calc_grid_position(ngoal.y, self.miny)]
            pind = ngoal.pind
            while pind != -1:
                n = closedset[pind]
                rx.append(self.calc_grid_position(n.x, self.minx))
                ry.append(self.calc_grid_position(n.y, self.miny))
                pind = n.pind
    
            return rx, ry
    
        @staticmethod
        def calc_heuristic(n1, n2):
            w = 1.0  # weight of heuristic 启发权重
            d = w * math.hypot(n1.x - n2.x, n1.y - n2.y)
            return d
    
        def calc_grid_position(self, index, minp):
            """
            calc grid position
    
            :param index:
            :param minp:
            :return:
            """
            pos = index * self.reso + minp
            return pos
    
        def calc_xyindex(self, position, min_pos):
            return round((position - min_pos) / self.reso)
    
        def calc_grid_index(self, node):
            return (node.y - self.miny) * self.xwidth + (node.x - self.minx)
    
        def verify_node(self, node):
            px = self.calc_grid_position(node.x, self.minx)
            py = self.calc_grid_position(node.y, self.miny)
    
            if px < self.minx:
                return False
            elif py < self.miny:
                return False
            elif px >= self.maxx:
                return False
            elif py >= self.maxy:
                return False
    
            # collision check
            if self.obmap[node.x][node.y]:
                return False
    
            return True
    
        def calc_obstacle_map(self, ox, oy):
    
            self.minx = round(min(ox))
            self.miny = round(min(oy))
            self.maxx = round(max(ox))
            self.maxy = round(max(oy))
            print("minx:", self.minx)
            print("miny:", self.miny)
            print("maxx:", self.maxx)
            print("maxy:", self.maxy)
    
            self.xwidth = round((self.maxx - self.minx) / self.reso)
            self.ywidth = round((self.maxy - self.miny) / self.reso)
            print("xwidth:", self.xwidth)
            print("ywidth:", self.ywidth)
    
            # obstacle map generation 生成障碍图
            self.obmap = [[False for i in range(self.ywidth)]
                          for i in range(self.xwidth)]
            for ix in range(self.xwidth):
                x = self.calc_grid_position(ix, self.minx)
                for iy in range(self.ywidth):
                    y = self.calc_grid_position(iy, self.miny)
                    for iox, ioy in zip(ox, oy):
                        d = math.hypot(iox - x, ioy - y)
                        if d <= self.rr:
                            self.obmap[ix][iy] = True
                            break
    
        @staticmethod
        def get_motion_model():
            # dx, dy, cost
            motion = [[1, 0, 1],
                      [0, 1, 1],
                      [-1, 0, 1],
                      [0, -1, 1],
                      [-1, -1, math.sqrt(2)],
                      [-1, 1, math.sqrt(2)],
                      [1, -1, math.sqrt(2)],
                      [1, 1, math.sqrt(2)]]
    
            return motion
    
    
    def main():
        print(__file__ + " start!!")
    
        # start and goal position
        sx = 10.0  # [m] 起点与终点
        sy = 10.0  # [m]
        gx = 50.0  # [m]
        gy = 50.0  # [m]
        grid_size = 2.0  # [m]
        robot_radius = 1.0  # [m]
    
        # set obstacle positions 设置边界
        ox, oy = [], [] 
        for i in range(-10, 60):
            ox.append(i)
            oy.append(-10.0)
        for i in range(-10, 60):
            ox.append(60.0)
            oy.append(i)
        for i in range(-10, 61):
            ox.append(i)
            oy.append(60.0)
        for i in range(-10, 61):
            ox.append(-10.0)
            oy.append(i)
        for i in range(-10, 40):
            ox.append(20.0)
            oy.append(i)
        for i in range(0, 40):
            ox.append(40.0)
            oy.append(60.0 - i)
    
        if show_animation:  # pragma: no cover
            plt.plot(ox, oy, ".k")
            plt.plot(sx, sy, "og")
            plt.plot(gx, gy, "xb")
            plt.grid(True)
            plt.axis("equal")
    
        a_star = AStarPlanner(ox, oy, grid_size, robot_radius)
        rx, ry = a_star.planning(sx, sy, gx, gy)
    
        if show_animation:  # pragma: no cover
            plt.plot(rx, ry, "-r")
            plt.show()
            plt.pause(0.001)
    
    
    if __name__ == '__main__':
        main()
    
    

    在这里插入图片描述

    展开全文
  • A*算法python实践

    2021-01-06 08:57:48
    A*算法简单实践A * 算法简介流程说明确定地图伪代码1、初始化栅格为一个列表2、迭代计算2.1 寻找子节点2.2更新子节点的父节点以及代价信息2.3完整栅格表代码运行结果 A * 算法简介 略。 流程说明 确定地图 s 为起点...

    A * 算法简介

    略。

    流程说明

    确定地图

    s 为起点, e 为终点, # 为可规划路径,O 为障碍物。

     # # # O #
     # # # # #
     s # # O #
     # # # O e
     # # # O #
    

    规定: ↑↓ ←→需要1步与↖↙↗↘ 需要1.4步
    规定:向下为x轴正方向,向右为y轴正方向

    流程

    1、初始化栅格为一个列表

    包含以下内容:

    • [[父节点坐标], [当前点坐标], f, g, h, string ]
    • 如起点s 我们可以定义为 [[3, 1], [3, 1], 5, 0, 5, ‘#’]
      其中代价 f = g + h
      g为已经走过的路径长度
      h为当前点到终点的曼哈顿距离
      则我们可以认定起点的父节点依旧是本身,g = 0(因为未曾出发), h = 1 + 4(x轴距离,y轴距离)

    2、迭代计算

    2.1 寻找子节点

    本算法寻找周围8个方向的子节点,如果该子节点没有父节点且在地图上,则更新其为当前节点的子节点。
    8个方向分别为:

    • wn西北,n北,en东北
    • w西,e东
    • ws西南,s南,es东南
    child = {
                'wn': {'x': 0, 'y': 0, 'f': 0, 'g': 0, 'h': 0}, 
                'n': {'x': 0, 'y': 0, 'f': 0, 'g': 0, 'h': 0},
                'en': {'x': 0, 'y': 0, 'f': 0, 'g': 0, 'h': 0}, 
                'w': {'x': 0, 'y': 0, 'f': 0, 'g': 0, 'h': 0},
                'e': {'x': 0, 'y': 0, 'f': 0, 'g': 0, 'h': 0}, 
                'ws': {'x': 0, 'y': 0, 'f': 0, 'g': 0, 'h': 0},
                's': {'x': 0, 'y': 0, 'f': 0, 'g': 0, 'h': 0}, 
                'es': {'x': 0, 'y': 0, 'f': 0, 'g': 0, 'h': 0}
            }
    

    例如我们有起点

    • [[3, 1], [3, 1], 5, 0, 5, ‘#’]
      对于起点周围的 8 个方向的点进行计算
    child = {
    			'e': {'f': 5, 'g': 1, 'h': 4, 'x': 3, 'y': 2},
    			 'en': {'f': 6.4, 'g': 1.4, 'h': 5, 'x': 2, 'y': 2},
    			 'es': {'f': 4.4, 'g': 1.4, 'h': 3, 'x': 4, 'y': 2},
    			 'n': {'f': 7, 'g': 1, 'h': 6, 'x': 2, 'y': 1},
    			 's': {'f': 5, 'g': 1, 'h': 4, 'x': 4, 'y': 1},
    			 'w': {'f': 8, 'g': 1, 'h': 7, 'x': 3, 'y': -1},
    			 'wn': {'f': 9.4, 'g': 1.4, 'h': 8, 'x': 2, 'y': -1},
    			 'ws': {'f': 7.4, 'g': 1.4, 'h': 6, 'x': 4, 'y': -1}
    		 }
    

    坐标中存在负数我们认为该点不存在,则实际对于起点来说,子节点为:

    child = {
    			'e': {'f': 5, 'g': 1, 'h': 4, 'x': 3, 'y': 2},
    			 'en': {'f': 6.4, 'g': 1.4, 'h': 5, 'x': 2, 'y': 2},
    			 'es': {'f': 4.4, 'g': 1.4, 'h': 3, 'x': 4, 'y': 2},
    			 'n': {'f': 7, 'g': 1, 'h': 6, 'x': 2, 'y': 1},
    			 's': {'f': 5, 'g': 1, 'h': 4, 'x': 4, 'y': 1}
    		 }
    

    2.2更新子节点的父节点以及代价信息

    如果该子节点没有父节点,且可规划(不是障碍物’O’)
    更新子节点的f, g, h,以及父节点坐标。
    以起点为例:

    • [[3, 1], [3, 1], 5, 0, 5, ‘#’]
      可以得到周围5个有效子节点
     # #
     s #
     # #
    
    • [[3, 1], [2, 1], 7, 1, 6, ‘#’],[[3, 1], [2, 2], 6.4, 1.4, 5, ‘#’],
    • [[3, 1], [3, 1], 5, 0, 5, ‘s’],[[3, 1], [3, 2], 5, 1, 4, ‘#’]
    • [[3, 1], [4, 1], 5, 1, 4, ‘#’],[[3, 1], [4, 2], 4.4, 1.4, 3, ‘#’]
    • g值 为父节点的 g + 父节点到当前点的g, h依旧为曼哈顿距离,f = g + h

    2.3 根据子节点中的f值迭代

    • 取得当前点的g值
    • 计算8个方向的坐标与g值
    • 将8个方向的子节点加到open list 中:
    •   如果不在open list也不在close list中,直接添加
      
    •   如果在open list中, 判断该点g值,是open list中的好还是child中的好(g越小越好)
        	如果child比open list中的更好,则更新open list中该点的father,cost
      
    •   如果在close list中,判断该点g值,哪一个好
        	如果child比close list中的更好,则更新close list中该点的father,cost
      
    • 把当前点加到close list中
    • 更新当前点,即选取child中f最小的那个点
    • 直至找到终点(或者搜完整个地图)

    2.4完整栅格表

    [[[[2, 2], [1, 1], 9.8, 2.8, 7, '#'],  [[2, 2], [1, 2], 8.4, 2.4, 6, '#'],  [[2, 2], [1, 3], 7.8, 2.8, 5, '#'],  [[0, 0], [1, 4], 0, 0, 0, 'O'],  [[2, 4], [1, 5], 7.8, 4.8, 3, '#']]
    
     [[[3, 1], [2, 1], 7, 1, 6, '#'],  [[3, 1], [2, 2], 6.4, 1.4, 5, '#'],  [[3, 2], [2, 3], 6.4, 2.4, 4, '#'],  [[3, 3], [2, 4], 6.4, 3.4, 3, '#'],  [[2, 4], [2, 5], 6.4, 4.4, 2, '#']]
     
     [[[3, 1], [3, 1], 5, 0, 5, 's'],  [[3, 1], [3, 2], 5, 1, 4, '#'],  [[3, 2], [3, 3], 5, 2, 3, '#'],  [[0, 0], [3, 4], 0, 0, 0, 'O'],  [[2, 4], [3, 5], 5.8, 4.8, 1, '#']]
     
     [[[3, 1], [4, 1], 5, 1, 4, '#'],  [[3, 1], [4, 2], 4.4, 1.4, 3, '#'],  [[4, 2], [4, 3], 4.4, 2.4, 2, '#'],  [[0, 0], [4, 4], 0, 0, 0, 'O'],  [[0, 0], [4, 5], 0, 0, 0, 'e']]
     
     [[[4, 1], [5, 1], 7, 2, 5, '#'],  [[4, 2], [5, 2], 6.4, 2.4, 4, '#'],  [[4, 2], [5, 3], 5.8, 2.8, 3, '#'],  [[0, 0], [5, 4], 0, 0, 0, 'O'],  [[0, 0], [5, 5], 0, 0, 0, '#']]]
    

    图形逻辑

    1、确定栅格地图

    • 起点为 ‘S’ 终点为’E’, 寻找起点周围的8个方向的子节点。
      • 去除非法节点。
        • 坐标不在地图上的点
        • 子节点处于障碍物上的点
      • 计算每一个节点代价 f = g + h

    在这里插入图片描述
    在这里插入图片描述

    • 取起点的最优子节点
      • 再次寻找8个子节点
        • 重复

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    不想写了

    代码

    代码在git上

    运行结果

    在这里插入图片描述

    展开全文
  • 深度广度优先算法、A*算法深度优先算法(DFS)实现步骤实现代码广度优先算法(BFS)实现步骤实现代码A*算法Dijkstra算法A*算法介绍实现流程实现过程实现代码 深度优先算法(DFS) 深度优先搜索属于算法的一种,是...
  • A*算法原理及例题介绍一、A*算法的基本原理二、A*算法例题介绍三、例题理论分析四、程序流程图五、启发式函数h(n)的定义六、A*搜索过程中的节点信息七、A*算法与A算法、宽度优先的区别 一、A*算法的基本原理 (A-...
  • A*算法求解N数码

    2020-05-09 16:39:26
    2.利用A*算法求解N数码难题,理解求解流程和搜索顺序 3.熟练掌握numpy库的相关函数(单独库,需要使用‘pip install numpy’安装) 实验原理: A*算法是一种启发式搜索算法,其特点在于对估价函数的定义上。对于...
  • 还是选择之前Dijkstra算法使用的那张图,利用A*算法寻找从节点1到节点5的最短路径,在之前的基础上为每个节点增加到目标节点5的估计代价,如中砖红色数字表示。 根据A*算法的思路,open list用于存
  • a*算法解读

    2018-10-27 11:41:30
    A*算法  Dijkstra算法从物体所在的初始点开始,访问中的结点。它迭代检查待检查结点集中的结点,并把和该结点最靠近的尚未检查的结点加入待检查结点集。该结点集从初始结点向外扩展,直到到达目标结点。Dijkstra...
  • 针对传统A*算法搜索速度慢和规划路径不够优化的缺点,引入可扩展节点,对A*算法流程进行改进,以减少时间和空间复杂度,提高搜索效率,并对规划路径进行优化处理,以有效的缩短路径。对存在凹形障碍物的地图,采用...
  • 简单的A*算法,后续考虑更复杂情况,一个C文件即可,VS,linux等都可以直接编译运行。后面首先考虑加上图形化界面(地图可以自己输入确定也考虑下) A*算法原理 这个很简单就不多说了,根据f = g + h。像是欧几里得...
  • 熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。 二、实验原理 A*算法是一种启发式搜索算法,其特点在于对估价函数的定义上。对于一般的启发式搜索,...
  • A*算法在三维地理空间(基于DEM)的python实现项目简介背景知识A* 算法如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个...
  • 基于ROS的A*算法代码学习

    千次阅读 2021-01-07 21:44:52
    基于ROS的A*算法代码学习过程演示ROS包node.hAstar_searcher.h如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表...
  • 人工智能A*算法C实现

    千次阅读 2017-06-20 21:56:20
    对下所示的状态空间A*算法进行搜索: 其中A为起始节点,E为目标节点,各节点的启发值表示在括号内。 二、实验设计(原理分析及流程) A* 是启发式搜索算法。该算法创建两个表:OPEN(类似于回溯算法中的NS...
  • A*算法求解N数码问题(AI实验一)

    千次阅读 2020-05-21 18:48:01
    利用A*算法求解N数码难题,理解求解流程和搜索顺序 熟练掌握numpy库的相关函数 3.实验原理 A*算法是一种启发式搜索算法,其特点在于对估价函数的定义上。对于一般的启发式搜索,总是选择估价函数f值最小的结点...
  • hslogic_A*算法

    千次阅读 2020-09-09 22:06:52
    2.2算法流程图 2.3代码逐句解析 以上的代码是一些参数的设置,其中第6行代码为随机数种子,确定一组随机数的产生。 第8行的代码为设置实际的拓扑结构,分别为单数据流,并行的数据流以及交叉的数据流; 第...
  • A*算法之走出死胡同

    2019-12-12 18:07:53
    A*算法之走出死胡同闲谈基本寻路死胡同情况功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • A*算法求解八数码问题 java实现

    千次阅读 2020-01-27 20:08:00
    A*算法求解八数码问题1.估价函数2.搜索过程3.流程图4.八数码的估计函数设计5.编码实现6.结果 1.估价函数 首先定义估价函数。计算一个节点的估价函数,可以分成两个部分:g(n)已经付出的代价(起始节点到当前节点)...
  • A*算法在运行过程中,也不可避免的用到了穷举(比如取得空白位的移动方式),但由于评价函数的存在使A*算法能够减少许多类似于穷举的工作。因此它只求解了问题的全部状态空间中的部分状态,提高了效率和减少了用于处理...
  • A*算法流程 1) G:=s; //算法开始时搜索只包括初始状态节点 2) OPEN:=(s), CLOSE:=( ); //此时仅有s作为待扩展节点,而CLOSE表为空 3) 若OPEN是空表,则算法以失败结束;//因为此时并未搜索到解答(目标状态),...
  • Unity中利用A*算法实现简单寻路

    千次阅读 2016-09-22 22:31:50
    欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来,用它写博客,将会带来全新...UML序列图和流程图 离线写博客 导入导出Markdown文件 丰富的快捷键 快捷键 加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl
  • A-Star(A*算法

    千次阅读 2019-10-09 17:06:42
    A-Star(A*)算法作为Dijkstra算法的扩展,在寻路和的遍历过程中具有一定的高效性。 【适用范围】静态搜索 【算法流程】A-Star算法中采用的估价函数如下,其中*h(i)的引入可以防止搜索过程中过渡跑偏到很多非常...
  • A* 算法流程 见文件:src/grid_path_searcheer/src/demo_node.cpp 主函数 main 1. int main(int argc, char** argv) 2. { 3. ...... 4. //订阅到地图信息的回调函数 5. _map_sub = nh.subscribe( "map", 6. //订阅到...
  • A* 寻路算法

    千次阅读 2012-01-10 17:30:11
    构造point 类 ...流程: 1 将起点放入开放列表 2 从开放列表中查找F值最低的点 3 检测此点周围的可到地点,并放入开放列表中 4 将此点放入闭合列表,并在开放列表中将其删除 5 如果在开放列表中检
  • astar流程图.rar

    2021-06-13 13:45:47
    a*算法流程图(只是流程图)A*算法是一种在静态路网中求解最短路径最有效的直接搜索方法,也是解决许多其他搜索问题的有效算法。算法中的距离估算值与实际值越接近,扩展的节点数越少, 搜索速度越快。

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 215
精华内容 86
关键字:

A*算法流程图