先来想想这么一个题目：
在方格图中，有 \(M\) 个障碍，不能通过这些障碍。给定起点坐标和终点坐标，求出最短路。
1. 贪心最优搜索和 Dijkstra 算法
- 贪心最优搜索
贪心最优搜索的流程是：从起点出发，在它的邻居结点上选择离终点最近的点。但是这样往往不能取得最优解。其思想为只看终点，不管起点。
- Dijkstra 算法
Dijkstra 的流程是：从起点出发，在它的邻居结点上选择里起点最近的点。但是这样搜索是盲目的。其思想为只看起点，不管终点。
2. A* 算法的原理
A* 算法结合了这两个算法，即既看起点，也看终点。它比 Dijkstra 快，因为它不像 Dijkstra 一样盲目。它比贪心最优搜索更准确，因为它可以找到最短路。
那么如何结合呢？
设起点为 \(s\)，终点为 \(t\)。当走到点 \(i\) 的时候，可以把 \(s \rightarrow t\) 的路径分为 \(s \rightarrow i \rightarrow t\)。
-
\(s \rightarrow i\) 的距离，可以在扩散搜索的时候记录。
-
\(i \rightarrow t\) 的距离，用贪心最优搜索来预测下一个结点。
以上思路可以用估价函数具体操作。即：
\(f(i)=g(i)+h(i)\)。
其中 \(f(i)\) 是对 \(i\) 的评估，\(g(i)\) 是记录的距离，\(h(i)\) 是到终点的曼哈顿距离。
每次根据最小的 \(f(i)\) 选择下一个点，可以使用优先队列选择最小的点。这样当 \(i=t\) 时，\(f(i)\) 即为最短路。
3 种算法的对比
这张图可以直观地解释出来。
其中黑色格子是障碍，数字是估价，有数字的格子是该算法搜索到的格子。
Dijkstra 算法搜索的结点最多，A* 算法居中，贪心最优搜索最少。
Dijkstra 算法和 A* 算法取得了最短路。
在这个图中，A* 算法会先访问所有估价为 \(10\) 的格子，接着访问 \(12,14\)，然后到达终点。
h 函数的设计
对于平面问题，一般有以下 \(3\) 种方法：
-
曼哈顿距离，即 \(h(i)=\lvert x_1-x_2 \rvert+\lvert y_1-y_2 \rvert\)。应用于向 \(4\) 个方向移动的题目。
-
对角线距离，即 \(h(i)=\max(\lvert x_1-x_2 \rvert,\lvert y_1-y_2 \rvert)\)。应用于向 \(8\) 个方向移动的题目。
-
欧式距离，即 \(h(i)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)。应用于可以任意方式移动的题目。
对于非平面问题，根据题目灵活处理。
应遵循以下三条规则：
-
\(g\) 和 \(h\) 应采用同样的计算方法。例如 \(g\) 是曼哈顿距离，\(h\) 也应是曼哈顿距离。
-
根据应用情况正确选择 \(h\)。如题目要就计算曼哈顿距离，就不能选择欧氏距离。
-
\(h\) 应该优于实际存在的所有路径。这是最重要的一条规则。如果不这样，程序可能会选择另一条非最优的路径，会造成错误。
A* 算法例题
这道题可以用 A* 算法解决。
我们每搜到一个一个点时，就将它与它的距离加入优先队列，并用它去扩展更多的点。优先队列中弹出的节点顺序就是距离的顺序。当终点 \(t\) 第 \(K\) 次从优先队列弹出，就是第 \(K\) 短路径。
接下来考虑估价函数。\(g(i)\) 表示 \(s \rightarrow i\) 的距离，可以在扩展的时候计算。\(h(i)\) 表示 \(i \rightarrow t\) 的距离，可以用 Dijkstra 算法求出，建一个反图，然后对 \(t\) 跑 Dijkstra。于是这个题就可以做了。
这样时间复杂度为 \(\mathcal{O}(NK \log N)\)。
下面给出 POJ-2449 的代码。
标签：终点,Dijkstra,距离,算法,搜索,rightarrow From： https://www.cnblogs.com/lrxmg139/p/18012131