| 类型 | 例子 | 完备性 | 最优性 |
|---|---|---|---|
| 基于搜索 | A* , Dijkstra | 完备 | 最优 |
| 基于采样 | PRM , RRT | 概率完备 | 非最优(RRT* 渐进最优) |
| 基于启发 | 遗传 ， 蚁群 | 完备 | 非最优 |
迪杰斯特拉算法，单源最短路径问题，无向图，权值都为正
设 G=(V,E) 是一个带权有向图，把图中顶点集合V分为两个集合，S ，已求出最短路径的顶点集合（初始时 S 中只有一个源点 v ，以后每求得一条最短路径 , 就将加入到集合 S 中，直到全部顶点都加入到 S ）。U 未确定最短路径的顶点集合，按照最短路径，把 U 中的添加到 S ，保证从 v 到 S 中各点最短路径长度不大于从源点 v 到 U 中任意点距离。此外，每个顶点对应一个距离， S 中的顶点的距离就是从 v 到此顶点的最短路径长度， U 中的顶点的距离，是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前路径的最短长度。
启发式搜索，能找到最短路径，快
思路跟Dijkstra相近，两个集合分别存放已经搜寻的点和未完成搜寻的点，在选择下一个搜索点的时候， f(n) = g(n) + h(n) ， g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价。如果说 h(n)=0，那么f(n) = g(n)，A* 退化为 Dijkstra，如果 h(n) 非常大，远大于 g(n)，那么 f(n) = h(n) ，演变为 最佳优先搜索（BFS）。
所以说启发式函数 h(n) 至关重要。如果满足： h(n) <= 从n移动到目标的实际代价 ，则 A*保证能找到一条最短路径。h(n)越小，A*扩展的结点越多，运行就得越慢。
网格地图中常用距离 h(n)： D 系数
曼哈顿距离：h(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )
对角线距离：h(n) = D * max(abs(n.x - goal.x), abs(n.y - goal.y))
欧氏距离：h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)
欧式距离平方：h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)
A*算法和 Dijkstra 都需要维护两个表，open，closed。首先需要查找节点是否可扩展，也就是需要查找节点是否在close表中，频繁查找，降低复杂度，于是利用python封装好的set数据结构进行closed表的存储，set是使用 红黑树 实现的，因此查询速度很快。每次都要从open中找最小的节点，节点少的话遍历 O(N) 就行，如果节点数非常多，可以考虑使用 二叉堆 维护，每次调整堆 O(log N)。
随机路图（Probabilistic Road Maps，PRM）就是在规划空间内随机选取N个节点，之后连接各节点，并去除与障碍物接触的连线，由此得到一个随机路图。显然，当采样点太少，或者分布不合理时，PRM算法是不完备的，但是随着采用点的增加，也可以达到完备。所以PRM是概率完备且不最优的。
快速扩展随机树法,是基于树状结构的搜索算法，RRT算法是从起始点开始向外拓展一个树状结构，而树状结构的拓展方向是通过在规划空间内随机采点确定的。与PRM类似，该方法是概率完备且不最优的。
Genetic Algorithm，遗传算法，启发式，组合优化类问题通用解法（函数最值、路径规划等）
1、编码：常用二进制编码、浮点编码、字符编码。注意编码要能覆盖可选择区域。地图比如栅格离散化
2、种群初始化：比如数轴上随机生成 N 个点（种群大小）。路径问题：随机生成 N 条路径，每一条路径可看做由 M 个点组成的序列，起始点S，终点Q，路径 S -> P1 -> P2 -> ... -> Pm -> Q，M+2 个点，M+1 条边。
3、适应度函数、评价函数：函数最值问题通常是 f(X)。路径问题通常是 M+1 条边路径距离之和。
4、选择：根据适应度函数，轮盘赌的方式选择两个个体作为父方、母方。路径问题就是在这 N 条路径中选择需要交叉的两条路径。
5、交叉：选择的父方、母方，根据编码，随机一个片段交换，生成子代。两条路径交换拼接其中一段。
6、变异：随机编码中的某一位、某几位改变。路径中改变某个点位置。
7、终止条件：迭代轮数，运算精度，或者收敛即可
Simulate Anneal，模拟退火算法，组合优化类问题通用解法
流程同 GA 遗传算法 类似，过程没有那么多，只是在考虑状态转移的过程中，遵循Metropolis准则：
如果 E(Xnew) <= E(Xold) , 能量低，直接转移状态
如果 E(Xnew) > E(Xold) , 能量高，状态转移的概率为 exp(- delta E / T)
系统落入低能量状态的概率随着温度 T 的下降而单调上升。注意：
1、初始温度 T0 必须足够高。取值方法具体情况具体分析，比如路径问题的“能量函数”为路径和，为保证刚开始有较大概率状态转移，比如取0.8 或 0.9，令 exp(- delta E / T0)=0.9，即可求得 T0。路径问题以 旅行商 TSP 为例，T0 取几百即可。
2、每个温度下，状态交换必须足够充分。通常采用固定轮数方法：比如路径问题取了 M 个点，通常每个温度 T 下迭代轮数取 10M ~ 100M。每次迭代变化点的坐标，或者交换点的顺序。
3、温度 T 下降足够慢。通常采用等比例下降，衰减系数 0.8~0.95 ，或者是等值减小。
4、终止条件：通常当 T 下降到接近于零度左右即可，或者已经收敛，没有新的解出现即可。
1、路径概率选择机制信息素踪迹越浓的路径,被选中的概率越大
2、信息素更新机制路径越短,路径上的信息素踪迹增长得越快
3、协同工作机制蚂蚁个体通过信息素进行信息交流。