启发式路径搜索算法介绍

作者丨Arwin(Haowen Yu)

来源丨古月居 

前言

启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。简单来说，就是已知起点和终点位置，寻找最佳路径。

 启发式搜索

方法（Dijkstra search，Greedy Search，A* ）

代价一致搜索 (Uniform Cost Search or Dijkstra search)

贪心搜索 (Greedy Search)

A星搜索 (A* Search)

首先， 使用评价函数 f(x) 来对上述的节点选择顺序进行排序

下面先定义两个函数：

• g(x) 为从根节点到x节点的代价总和

• h(x) 为从x节点到目标节点的估计代价总和

这类应用算法有:

• 代价一致搜索 (Uniform Cost Search or Dijkstra search) f(x) = g(x)

• 贪心搜索 (Greedy Search) f(x) = h(x)

• A星搜索 (A* Search) f(x) = g(x) + h(x)

性质

Admissible heuristic

admissibility是启发式搜索的一个性质，如果满足这个性质，那么，启发函数一定能得到最佳solution。

A*搜索能找到最优解的充分条件:

1.搜索树上存在着从起始点到目标点的最优路径

2.问题域是有限的

3.所有结点的子结点的成本>0

4.h(n) =< h*(n) (h*(n)为从节点n到目标点的实际成本)

123易满足，第4条中这样的启发函数被称为Admissible heuristic，也就是说在A*中我们对目标的估计必须小于或等于其实际值,不然可能会出现找不到最优路径或者根本找不到路径的情况

Consistent heuristic

N是开始节点，绿色的是目标节点，h(N)则是从N到目标节点的启发函数，N’为任意不同于N的节点

A star with tree能找到最优解的充分条件:

1.搜索树上存在着从起始点到目标点的最优路径

2.问题域是有限的

3.所有结点的子结点的成本>0

4.h(N’) + c(N, N’) < h(N)

这样的启发函数被称为Consistent heuristic，只有满足了这个才能保证A*算法在图搜索中能找到最优解。

一个启发函数是consistent，它也是admissible。反之，不可。

dominate

Dominance（用于表现不同启发函数的关系）

two admissible heuristics ha, hb：

如果对于所有n, ha(n) >hb(n),那么，我们可以说 ha dominates hb，对于这个search问题，我们最好使用ha作为启发函数。

总结

A star算法的特点(考虑g(x)+h(x)，注意树搜索满足Admissible heuristic，图搜索满足Consistent heuristic时)

1.完备性：肯定能找到最优解

2.最优性：找到的解花费最小

3.快：扩展更少的节点

UCS(代价一致搜索，只考虑g(x))

1.完备性：肯定能找到最优解

2.最优性：找到的解花费最小

3.比A*慢一些

广度优先搜索是代价一致搜索的特例

贪婪搜索(启发式搜索，但只考虑h(x))

1.不完备性：不保证能找到最优解

深度优先搜索是贪婪搜索的特例（令h(n)===0，A*搜索退化为宽度优先搜索(BFS)，不估计成本，肯定能找到最优解）

本文仅做学术分享，如有侵权，请联系删文。

3D视觉工坊精品课程官网：3dcver.com

1.面向自动驾驶领域的多传感器数据融合技术

2.面向自动驾驶领域的3D点云目标检测全栈学习路线！(单模态+多模态/数据+代码)
3.彻底搞透视觉三维重建：原理剖析、代码讲解、及优化改进
4.国内首个面向工业级实战的点云处理课程
5.激光-视觉-IMU-GPS融合SLAM算法梳理和代码讲解
6.彻底搞懂视觉-惯性SLAM：基于VINS-Fusion正式开课啦
7.彻底搞懂基于LOAM框架的3D激光SLAM: 源码剖析到算法优化
8.彻底剖析室内、室外激光SLAM关键算法原理、代码和实战(cartographer+LOAM +LIO-SAM)

9.从零搭建一套结构光3D重建系统[理论+源码+实践]

10.单目深度估计方法：算法梳理与代码实现

11.自动驾驶中的深度学习模型部署实战

12.相机模型与标定(单目+双目+鱼眼）

13.重磅！四旋翼飞行器：算法与实战

14.ROS2从入门到精通：理论与实战

15.国内首个3D缺陷检测教程：理论、源码与实战

16.基于Open3D的点云处理入门与实战教程

重磅！3DCVer-学术论文写作投稿 交流群已成立

扫码添加小助手微信，可申请加入3D视觉工坊-学术论文写作与投稿 微信交流群，旨在交流顶会、顶刊、SCI、EI等写作与投稿事宜。

同时也可申请加入我们的细分方向交流群，目前主要有3D视觉、CV&深度学习、SLAM、三维重建、点云后处理、自动驾驶、多传感器融合、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流、ORB-SLAM系列源码交流、深度估计等微信群。

一定要备注：研究方向+学校/公司+昵称，例如：”3D视觉 + 上海交大 + 静静“。请按照格式备注，可快速被通过且邀请进群。原创投稿也请联系。

▲长按加微信群或投稿

▲长按关注公众号

3D视觉从入门到精通知识星球：针对3D视觉领域的视频课程（三维重建系列、三维点云系列、结构光系列、手眼标定、相机标定、激光/视觉SLAM、自动驾驶等）、知识点汇总、入门进阶学习路线、最新paper分享、疑问解答五个方面进行深耕，更有各类大厂的算法工程人员进行技术指导。与此同时，星球将联合知名企业发布3D视觉相关算法开发岗位以及项目对接信息，打造成集技术与就业为一体的铁杆粉丝聚集区，近4000星球成员为创造更好的AI世界共同进步，知识星球入口：

学习3D视觉核心技术，扫描查看介绍，3天内无条件退款

 圈里有高质量教程资料、答疑解惑、助你高效解决问题

觉得有用，麻烦给个赞和在看~