关键
初始化：
算法是基于图搜索的思想，所以需要先构建一个图，图中不包含障碍物，读入起点和终点信息，设置一个以代价作为键值排序的multiMap，起点入队，并设置起点是被标记过的，
进入循环
起点出队，multiMap移除这点，判断当前节点是否是终点，如果为终点则跳出循环,以这点作为邻居节点的当前结点，获取图中当前结点的邻居节点，各自到当前结点的代价距离，然后对所有邻居节点进行遍历，如果是之前已经标记过的，那么判断到起点的代价距离是否比当前大，如果大，则更新，并把邻居节点的前置节点设为当前结点，如果未标记，将该点的前置节点设为当前结点，并加入multiMap，标记上，然后重复这个过程直到multiMap为空，然后反转得到路径
2、RRT算法流程；keyword: 采样，迭代，树，两点之间是否联通
首先初始化，输入起点，终点，地图信息
设置迭代次数，开始迭代，在地图无障碍区域进行采样，获得采样点，然后寻找与采样树中最近的点，以一定的步长扩展新的节点，判断二者连接是否存在障碍物，无障碍物则扩展新的节点到树中，循环这个过程，直到终点被加入树中，当然这需要满足一定的阈值。反向查询，最后生成路径
初始化整个空间，定义初始点、终点、采样点数、点与点之间的步长t等信息 在空间中随机产生一个点xrand 在已知树的点集合中找到距离这个随机点最近的点xnear 在xnear到xrand的直线方向上从xnear以步长t截取点xnew 判断从xnear到xnew之间是否存在障碍物，若存在则舍弃该点 将new点加入到树集合中 循环2~6，循环结束条件：有一个new点在终点的设定邻域内
(225条消息) RRT与RRT_算法具体步骤与程序详解（python）问题很多de流星的博客-博客_rrt算法
3、你用过的路径规划算法原理及特点路径规划五种算法简述及对比
启发式搜索是利用启发函数来对搜索进行指导，从而实现高效的搜索
A算法是一种在静态地图中求解最短路径的直接搜索方法。_
4 说一下a*算法的流程初始化open_set和close_set；
openlist存放已经获取到的邻居节点,但是还未处理,
closelist 存放的是已经处理过的节点
对于不是openlist的节点,将其加入优先队列中, 已经在的话则需要根据代价判断是否更新;而对于closelist存放的不再处理
6、hybrid A*算法以及优化
混合A再A算法的基础上考虑了车辆的运动学模型，即满足车辆的大曲率约束，计算代价时考虑进去。
扩展方式
A扩展时是从当前栅格的中心点，扩展到周围八个栅格的中心点，路径是两两中心点的连线
HybridA扩展一共六个方向，左圆前进、倒车，直线前进、倒车，右圆前进、倒车，通过系统状态方程进行扩展
A到达新的栅格，位置必定是栅格中心，而HybridA到达的位置可以是路径上的任一点。
连通图结构
混合A* 除了考虑（x,y）维度外，还考虑量车辆姿态 θ
启发函数：
混合A表示从当前节点位姿到终点位姿的，同时满足避障条件及车辆运动学约束条件的最短路径长度，分为non-holonomic without-obstacle和 with obstacles AnalyticExpand(nc)两种类型启发函数，考虑障碍物与否区分
对于无障碍物采用Reeds-Sheep曲线生成，如果路径与障碍物发生重叠，采用动态规划或者A搜索路径；
接近目标点
混合A靠近目标点直接连接即可，因为采样不一定能刚好到目标点，同时也是为了提升效率
A则要求搜索的当前节点为目标点
正反馈，信息素
用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。
(1)采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。
(2)每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯。
(3)搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率。
(4)启发式的概率搜索方式不容易陷入局部最优，易于寻找到全局最优解。 [4]
8、 基于图论的规划方法其缺点是什么不适合于高维问题，需要事先建立图，
9.曼哈顿距离与欧式距离的优缺点，欧氏距离
D ( x , y ) = ∑ i = 1 n ( x i − y i ) 2 D(x, y)=\sqrt{\sum_{i=1}^{n}\left(x_{i}-y_{i}\right)^{2}} D(x,y)=i=1∑n(xi−yi)2
曼哈顿距离:
D ( x , y ) = ∑ i = 1 k ∣ x i − y i ∣ D(x, y)=\sum_{i=1}^{k}\left|x_{i}-y_{i}\right| D(x,y)=i=1∑k∣xi−yi∣
| Eulidean | Manhattan | |
| cons | 对异常数据敏感，往往需要归一化处理 由于计算的各个维度差异同等对待，所以无法对各个维度差异进行区别，不适合处理高维数据 | 对异常数据敏感，往往需要归一化处理 |
| pros | 计算速度快，直观 | 计算速度快，可以用于处理高维数据 |
对于向量之间的差异进行计算过程中，各个维度差异的权值不同
常见距离度量方法优缺点对比！_mob604756ea26ec的技术博客_51CTO博客
(186条消息) 欧式距离和曼哈顿距离的比较_AliceWanderAI的博客-博客_曼哈顿距离和欧式距离
9说说DP算法的过程这个可以参考
算法题64. 最小路径和
思想：把多阶段的决策过程转化为一系列单阶段的最优化问题来解决
逆向寻优，正向求值
应用
百度apollo中的em_planner也有用到DP的思想进行局部路径的搜索，再用QP的方式进行轨迹平滑。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧