智联网汽车技术 课件 6.5启发式搜索算法

启发式搜索算法项目三汽车决策控制系统任务6路径规划系统主讲人：杨时川智能网联汽车技术课程导入没有导航仪，要怎么找到路的呢?盲目搜索，找到路的速度会很慢，而且很容易走远路或者走错路事先规划，对周围路况有所了解，大幅度提高搜索效率，搜索最佳路线学习目标学会解释启发式搜索算法的思路、原理和具体算法01能应用到汽车路径规划中去02学习任务用生动形象的例子帮助理解启发式搜索算法01与小智一起设计一个汽车路径规划的启发式搜索算法02激活旧知路径规划算法有哪些类型吗？迪杰斯特拉算法一种比较经典的最短路径算法通过为每个路径设置权重，逐步遍历找到最短路径A*算法借鉴Dijkstra算法的思想利用启发式函数优化了搜索过程探索新知盲目搜索通常效率较低，时间和空间计算开销大启发式搜索利用问题的启发信息来指导搜索，从而达到降低搜索空间复杂度和问题复杂度的效果探索新知启发式算法思路：由日常生活中发现规律，寻找适合的方法启发而来的，能够得到近似的理想解，大大提高了搜索效率。探索新知定义即有信息搜索(InformedSearch)利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的。启发式搜索(HeuristicallySearch)探索新知定义在智能汽车状态空间中的搜索，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标坐标。探索新知原理和算法基本思想

将状态空间通过确定的方式离散成一个图，然后利用各种启发式搜索算法搜索可行解甚至是最优解，这类算法具有解析完备性，甚至是解析最优性。探索新知原理和算法利用当前与问题有关的信息作为启发式信息，这些信息是能够提升查找效率以及减少查找次数的。keyword探索新知原理和算法估价函数h(x)：对当前状态x的一个估计，表示x状态到目标状态的距离。起始状态到x状态所花的代价为g(x)：含义从起点到x位置花的步数在最短路径中，g(x)是到x点的权值，h(x)是x点到目标结点的最短路或直线距离探索新知原理和算法根据搜索依据函数的不同代价一致搜索UniformCostSearchorDijkstrasearch贪心搜索GreedySearchA*搜索A*Search探索新知原理和算法代价一致搜索具有完备性，能找到最优解，但效率太低1F(x)=g(x)：按照花了多少代价去搜索，从离得近的层开始搜索，一层一层搜2dijkstra算法：依据每条边的代价开始选择搜索方向探索新知原理和算法贪心搜索F(x)=h(x)：贪婪优先搜索，每次都是向最靠近目标的状态靠近。不具有完备性，不一定能找到解探索新知原理和算法A*搜索A*算法：对A算法进行了修改，证明了当估价函数满足一定条件，算法一定能找到最优解，估价函数满足一定条件的算法称为A*算法。限制条件F(x)=g(x)+h(x)代价函数g(x)>0h(x)的值不大于x到目标的实际代价h*(x)即定义的h(x)是可纳的，是乐观的探索新知原理和算法A*搜索吸取Dijkstra算法中的当前代价，为每个边长设置权值，不停计算每个顶点到起始顶点的距离，以获得最短路线。吸取贪婪最佳优先搜索算法中不断向目标前进优势，并持续计算每个顶点到目标顶点的距离，以引导搜索队列不断向目标逼近，从而搜索更少的顶点，保持寻路的最优解。探索新知启发式搜索算法总结启发式算法与最短路径问题通常用于资讯充份的搜寻算法（最好优先贪婪算法与A*）最好优先贪婪算法为启发式函数选择最低代价的节点为g(n)+h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。如h(n)是可接受的意即h(n)未曾付出超过达到目标的代价，则A*一定会找出最佳解A*探索新知启发式搜索算法总结启发式算法对运算效能的影响任何的搜寻问题中，每个节点都有b个选择以及到达目标的深度d，一个毫无技巧的算法通常都要搜寻bd个节点才能找到答案。探索新知启发式搜索算法总结启发式算法对运算效能的影响分叉率可以用来定义启发式算法的偏序关系，例：若在一个n节点的搜寻树上，h1(n)的分叉率较h2(n)低，则h1(n)<h2(n)。为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率，因此拥有较佳效率的计算能力启发式算法借由使用某种切割机制降低了分叉率以改进搜寻效率，由b降到较低的b'