路径查找


BFS,DFS

Dijkstra 算法:需要计算每一个节点距离起点的总移动代价。同时,还需要一个优先队列结构。对于所有待遍历的节点,放入优先队列中会按照代价进行排序。

最佳优先搜索:以每个节点到达终点的距离作为优先级,每次始终选取到终点移动代价最小(离终点最近)的节点作为下一个遍历的节点

A*算法:f(n)=g(n)+h(n) // 不一样的场景不同的优先级计算方法会有区别,给出一个近似解而不是保证最佳解
  • f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时,我们总会选取综合优先级最高(值最小)的节点。
  • g(n)是节点n距离起点的代价
  • h(n)是节点n距离终点的预计代价,这也就是A*算法的启发函数。
A*算法在运算过程中,每次从优先队列中选取f(n)值最小(优先级最高)的节点作为下一个待遍历的节点。另外,A*算法使用两个集合来表示待遍历(有优先级)的节点,与已经遍历过的节点,这通常称之为open_setclose_set
完整的A*算法描述如下:
* 初始化open_set和close_set;
* 将起点加入open_set中,并设置优先级为0(优先级最高);
* 如果open_set不为空,则从open_set中选取优先级最高的节点n:
* 如果节点n为终点,则:
* 从终点开始逐步追踪parent节点,一直达到起点;
* 返回找到的结果路径,算法结束;
* 如果节点n不是终点,则:
* 将节点n从open_set中删除,并加入close_set中;
* 遍历节点n所有的邻近节点:
* 如果邻近节点m在close_set中,则:
* 跳过,选取下一个邻近节点
* 如果邻近节点m也不在open_set中,则:
* 设置节点m的parent为节点n // 最终生成最短路径
* 计算节点m的优先级
* 将节点m加入open_set中

启发函数会影响A*算法的行为。
  • 在极端情况下,当启发函数h(n)始终为0,则将由g(n)决定节点的优先级,此时算法就退化成了Dijkstra算法
  • 如果h(n)始终小于等于节点n到终点的代价,则A*算法保证一定能够找到最短路径。但是当h(n)的值越小,算法将遍历越多的节点,也就导致算法越慢。
  • 如果h(n)完全等于节点n到终点的代价,则A*算法将找到最佳路径,并且速度很快。可惜的是,并非所有场景下都能做到这一点。因为在没有达到终点之前,我们很难确切算出距离终点还有多远。
  • 如果h(n)的值比节点n到终点的代价要大,则A*算法不能保证找到最短路径,不过此时会很快。
  • 在另外一个极端情况下,如果h(n)
  • 相较于g(n)大很多,则此时只有h(n)产生效果,这也就变成了最佳优先搜索。
网格形式的图,有以下这些启发函数可以使用:
  • 如果图形中只允许朝上下左右四个方向移动,则可以使用曼哈顿距离(Manhattan distance)。
  • 如果图形中允许朝八个方向移动,则可以使用对角距离。
  • 如果图形中允许朝任何方向移动,则可以使用欧几里得距离(Euclidean distance)。