《我的第一本算法书》阅读笔记 4-6 A* 算法

缺乏、安全感 2022-10-22 07:41 200阅读 0赞

A\*（A-Star）算法也是一种在图中求解最短路径问题的算法，由狄克斯特拉算法发展而来。 狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说， 一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A\* 就 会预先估算一个值，并利用这个值来省去一些无用的计算。

--------------------

![2021040511002117.png][]

首先，试着用狄克斯特拉算法来求该 迷宫中的最短路径吧。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

将迷宫看作是一个图，其中每个方块都是一个顶点，各顶点间的距离（权重）都为1。

![20210405110618206.png][]

以这个设定为前提，用狄克斯特拉算法来求最短路径。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

用狄克斯特拉算法求最短路径的结果会如上图所示，方块中的数字表示从起点到该顶点的距离（权重），蓝色和橙色的方块表示搜索过的区域，橙色方块同时还表示从S到G的最短路径。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

狄克斯特拉算法只根据起点到候补顶点的距离来决定下一个顶点。因此，它无法发现蓝色箭 头所指的这两条路径其实离终点越来越远，同样会继续搜索。

![20210406201212449.png][]

而A\*算法不仅会考虑从起点到候补顶点的距离， 还会考虑从当前所在顶点到终点的估算距离。 这个估算距离可以自由设定，此处我们用的是 将顶点到终点的直线距离四舍五入后的值。

如步骤06中方块右下角的数字所示，由人工预先设定的估算距离被称为“距离估算值”。如 果事先根据已知信息设定合适的距离估算值，再将它作为启发信息辅助计算，搜索就会变得 更加高效①。这里我们只知道终点所在位置，不知道该如何通往终点，所以使用了直线距离。

![2021040620125563.png][]

接下来，就试着用 A\* 算法来求解吧。首先把 起点设为搜索完毕状态。搜索完的点都用蓝色表示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

分别计算起点周围每个顶点的权重。计算方法 是“从起点到该顶点的距离”（方块左下）加上 “距离估算值”（方块右下）。

![20210406201554804.png][]

选择一个权重最小的顶点，用橙色表示。

![20210406201625694.png][]

将选择的顶点设为搜索完毕状态。

![20210406201651290.png][]

计算搜索完毕的顶点到下一个顶点的权重。

![20210406201728526.png][]

选择距离最短的一个顶点。

![20210406204150778.png][]

将选好的顶点设为搜索完毕状态。之后重复上述操作，直到到达终点为止。

![20210406204343837.png][]

搜索中……

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

搜索完毕。效率比狄克斯特拉算法的高了很多。

--------------------

如果我们能得到一些启发信息，即各个顶点到终点的大致距离（这个距离不需是准 确的值）我们就能使用 A\* 算法。当然，有时这类信息是完全无法估算的，这时就不能 使用 A\* 算法。

距离估算值越接近当前顶点到终点的实际值，A\* 算法的搜索效率也就越高；反过 来，如果距离估算值与实际值相差较大，那么该算法的效率可能会比狄克斯特拉算法的 还要低。如果差距再大一些，甚至可能无法得到正确答案。

不过，当距离估算值小于实际距离时，是一定可以得到正确答案的（只是如果没有 设定合适的距离估算值，效率会变差）。

### 应用示例 ###

A\* 算法在游戏编程中经常被用于计算敌人追赶玩家时的行动路线等，但由于该算法 的计算量较大，所以可能会使游戏整体的运行速度变慢。因此在实际编程时，需要考虑 结合其他算法，或者根据具体的应用场景做出相应调整。

--------------------

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[2021040511002117.png]: /images/20221022/75b0985d8081496ca615817bc0a424ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/f7903f6e51fe4c5eb2493d777440c4e8.png
[20210405110618206.png]: /images/20221022/cd043ed170b9423b938553163eedda22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/7def2c092afa4358b9f35433f72671ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/1f30391966e141e296abc55fcb4cef6e.png
[20210406201212449.png]: /images/20221022/a554a562a2a14b8eb432dbe622a13a5d.png
[2021040620125563.png]: /images/20221022/3fd88068d7da49d980843a19536d7caf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/8d48a1ad35bd436e83fc31e605c07051.png
[20210406201554804.png]: /images/20221022/8c5796a00151419983c3f7948c27eb53.png
[20210406201625694.png]: /images/20221022/360ad71d0db34484ad86ed97d63a08e5.png
[20210406201651290.png]: /images/20221022/6d6af9807ed34dc39000d461e6e35b01.png
[20210406201728526.png]: /images/20221022/75d27f9ab9d94da5a4e28a37d8f9e042.png
[20210406204150778.png]: /images/20221022/4b1080b453e3446a82269a252a6abf82.png
[20210406204343837.png]: /images/20221022/8b2ba04fc2654dbfa1facbc7e9fe7959.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/e38f9f0743f84fe58554493fb3873912.png