A星算法理解_a星算法例题

A星算法理解_a星算法例题A星算法理解1.选择A星算法的原因为了进行路径规划算法是不可回避的:启发式搜索算法是比较常规的一类算法就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的,如:f(n)=g(n)+h(n)。g…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

A星算法理解

1.选择A星算法的原因

为了进行路径规划算法是不可回避的:启发式搜索算法是比较常规的一类算法就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的,如:f(n) = g(n) + h(n) 。g(n)为起点到当前位置的实际路径长度,h(n)为所在位置到终点的最佳路径的估计距离。前面说每次会优先向终点方向进行移动,就是因为估价函数所导致的。h(n)=0时,意味着此时是盲目搜索,当h(n)越复杂,即约束的条件越多,耗费的时间就越多,而减少约束条件,则可能得到的并不是最优路线。在A算法中,估价函数为f(n)=g(n)+h*(n)。这里面的h*(n)的附加条件为h*(n)<=h‘(n),h’(n)为n到目标的直线最短距离,也就说A*算法中挑选的启发函数是最优的,也正是如此,所找到的路径是最短路径。

2.启发函数的选择问题

有时候经过简单的对比,很容易得出曼哈顿距离作为启发函数,搜索效率最高,并得出曼哈顿距离最好的结论。可是在实际情况下,我们不仅要考虑搜索效率,也要考虑最优性,所以大多情况下选择対角距离作为启发函数。

3.算法流程图

在这里插入图片描述

4.算法实现步骤

  1. 启发式函数

    double Manhattan_dist,Euclidean_dist,Diagonal_dist;
    Eigen::Vector3i diff=node2->index-node1->index;
    double dx,dy,dz;
    dx=abs(diff(0));
    dy=abs(diff(1));
    dz=abs(diff(2));
    Manhattan_dist=dx+dy+dz;
    Euclidean_dist=sqrt(diff.dot(diff));
    float dmin = min(dx, min(dy, dz));
    float dmax = max(dx, max(dy, dz));
    float dmid = dx + dy + dz - dmin - dmax;
    Diagonal_dist=(1.732 - 1.414) * dmin + (1.414 - 1) * dmid +  dmax;
    // tie breaker
    hue=Diagonal_dist*1.00001;
    return Euclidean_dist;

  1. 将起始节点放入OPEN表里
startPtr -> gScore = 0;
    startPtr -> fScore = getHeu(startPtr,endPtr);
    //STEP 1: finish the AstarPathFinder::getHeu , which is the heuristic function
    startPtr -> id = 1; 
    startPtr -> coord = start_pt;
    openSet.insert( make_pair(startPtr -> fScore, startPtr) );
  1. 当主循环不为空时
while ( !openSet.empty() )
  1. 将代价值最小的点从open表转移到close表中,并将原表中的点删除
// openSet.begin()->second->cameFrom=currentPtr;
        currentPtr=openSet.begin()->second;//acending order
        //move it to closeset at once
        currentPtr->id=-1;

// closeSet.insert(make_pair(openSet.begin()->first,openSet.begin()->second));
        openSet.erase(openSet.begin());
        GridNodeMap[currentPtr->index[0]][currentPtr->index[1]]
                [currentPtr->index[2]]=currentPtr;

  1. 如果当前点是目标点,路径成功结束。
// if the current node is the goal 
        if( currentPtr->index == goalIdx ){ 
   
            ros::Time time_2 = ros::Time::now();
            terminatePtr = currentPtr;
            ROS_WARN("[A*]{sucess} Time in A* is %f ms, path cost if %f m", (time_2 - time_1).toSec() * 1000.0, currentPtr->gScore * resolution );            
            return;
        }
        //get the succetion
  1. 对扩展节点进行扩展子节点
 *        
        */         
        for(int i = 0; i < (int)neighborPtrSets.size(); i++){ 
   
            /* * * Judge if the neigbors have been expanded please write your code below IMPORTANT NOTE!!! neighborPtrSets[i]->id = -1 : expanded, equal to this node is in close set neighborPtrSets[i]->id = 1 : unexpanded, equal to this node is in open set * */
            neighborPtr=neighborPtrSets[i];


            if(neighborPtr -> id == 0){ 
    //discover a new node, which is not in the closed set and open set
                /* * * STEP 6: As for a new node, do what you need do ,and then put neighbor in open set and record it please write your code below * */
                neighborPtr -> gScore=edgeCostSets[i];
                neighborPtr -> fScore = getHeu(neighborPtr,endPtr)+edgeCostSets[i];
                neighborPtr ->id=1;//open
                neighborPtr->cameFrom=currentPtr;
                openSet.insert( make_pair(neighborPtr -> fScore, neighborPtr) );
                //update map
                GridNodeMap[neighborPtr->index[0]][neighborPtr->index[1]]
                        [neighborPtr->index[2]]=neighborPtr;
                continue;
            }
            else if(neighborPtr -> id ==1){ 
    //this node is in open set and need to judge if it needs to update, the "0" should be deleted when you are coding
                /* * * STEP 7: As for a node in open set, update it , maintain the openset ,and then put neighbor in open set and record it please write your code below * */
                if(neighborPtr->gScore>edgeCostSets[i])
                    neighborPtr->gScore=edgeCostSets[i];
                neighborPtr -> fScore = getHeu(neighborPtr,endPtr)+neighborPtr->gScore;

                continue;
            }
            else if(neighborPtr -> id ==-1){ 
   //this node is in closed set: it is impossible that node in closeset will be suceession
                /* * please write your code below * */
// ROS_ERROR("NOOOO");
                continue;
            }
        }

    }
  1. 由当前点获取路径上的所有点
while(terminatePtr!=nullptr)
    { 
   
        gridPath.push_back(terminatePtr);
        terminatePtr=terminatePtr->cameFrom;
        if(gridPath.size()>100)
        { 
   
            ROS_ERROR("dead loop!!");
            break;
        }
    }
    for (auto ptr: gridPath)
        path.push_back(ptr->coord);
        
    reverse(path.begin(),path.end());

    return path;

一个具有注脚的文本。1


  1. 注脚的解释
    小白一枚 ↩︎

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/185132.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 串口调试助手fx2n_安信可串口调试助手

    串口调试助手fx2n_安信可串口调试助手安信可串口调试助手是由安信可官方出品的一款非常好用的串口调试工具,利用安信可串口调试助手可以实现电脑和模块之间的串口通信,非常方便,有需要可以下载使用。相关软件软件大小版本说明下载地址安信可串口调试助手是由安信可官方出品的一款非常好用的串口调试工具,利用安信可串口调试助手可以实现电脑和模块之间的串口通信,非常方便,有需要可以下载使用。功能介绍ESP8266的串口调试助手,下载即用,可以实现电脑和模…

  • 宽带上行下行测试软件,上行网速(电信300m宽带上行下行)「建议收藏」

    宽带上行下行测试软件,上行网速(电信300m宽带上行下行)「建议收藏」1、你应该是搞反了,现在的光钎宽带,最高就是100m;2、号称“100m”的宽带,可以这样解释:下行带宽是100m,上行带宽是4m;3、下行带宽就是你从网上下载文件的.宽带上行抄下行是指一般宽带或者光纤上网方式的上行与下行速率,上行就是从电脑上传的速度,下行就是从网络上的主机下载速度,一般下行速率比较高!电信宽带上下.上传速度是怎么算的?看了下答案,说的都是下载速度,迅雷里有个上传速度.抄1M宽…

    2022年10月23日
  • SqlBulkCopy 来自数据源的 String 类型的给定值不能转换为指定目标列的类型 bit「建议收藏」

    SqlBulkCopy 来自数据源的 String 类型的给定值不能转换为指定目标列的类型 bit「建议收藏」使用SqlBulkCopy批量插入,可以快速对大批量的数量插入,性能非常好在使用时出现“来自数据源的String类型的给定值不能转换为指定目标列的类型bit”异常为DataTable与要插入的数据表字段位置不一样所至DataTable与要插入的数据表要字段名,位置,数据类型都一至才可示例,使用使用SqlBulkCopy插入多个表publicbo…

  • administrator改名字_win10改了用户名无法登录

    administrator改名字_win10改了用户名无法登录网友求助:xp用administrator_XP系统修改administrator的用户名_xpadministrator问题不想添加多一个用户的办法?????????????????最佳答案说实话没有看懂题主的要求。我只能从你题面对描述,即将高级管理员帐户“Administrator”改变成其他名字来解答。要想将WindowsXP中要将默认的系统用户名改变成其他名称是可以实现的,但是需要调用“组…

    2022年10月14日
  • Eclipse plugin插件开发 NoClassDefFoundError

    Eclipse plugin插件开发 NoClassDefFoundError

  • jvm最全详解-05-JVM调优工具详解及调优实战[通俗易懂]

    jvm最全详解-05-JVM调优工具详解及调优实战[通俗易懂]jvm最全详解-05-JVM调优工具详解及调优实战前置启动程序事先启动一个web应用程序,用jps查看其进程id,接着用各种jdk自带命令优化应用Jmap此命令可以用来查看内存信息,实例个数以及占用内存大小jmap-histo14660#查看历史生成的实例jmap-histo:live14660#查看当前存活的实例,执行过程中可能会触发一次fullgc打开log.txt,文件内容如下:num:序号 instances:实例数量 b..

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号