A*算法的实践及改进
A*算法简介：
A*（读作AStar或A星）算法是一种很常用的路径查找和图形遍历算法，它有较好的性能和准确度。
用人话说，就是先有一个方格组成的矩形平面（称作“地图”），每一个方格代表一个点。在知道起点和终点还有附近的地
形（障碍物）的前提下，A*算法（在大部分情况下）能够绕开所有障碍，找到一条从起点通向终点的路径，而这条路径在
大部分情况下是能够达到的最短的路径。
工作原理：
A*算法有很多种变体，这里以最简单的一种为例。
1.已知矩形平面的长宽，起点和终点（设终点为pe）的坐标，每一个障碍物的坐标。
2.关于行走的规则，设我们从起点开始走，每次可以走到周围的8个点的位置（上下左右，以及斜着走）。
3.接下来要确定往哪个点走最合适。
3.1.设我们所在的点为pn。pn不一定是起点，它会随着我们的行走而改变。
3.2.先缩小选择范围：一开始有8个选择，也就是8个点。如果这8个点中，有些点超出了平面的范围，又或者是这个点
恰好是障碍物，则把这些点排除在外，剩余m个点（0<=m<=8）。注意，m可能依旧为8。另外，当m=0时，你就还剩下0
个可以选择的点，也就是你只能原地不动，但这不意味着你一定不可能走到终点（我会在“关于细节”一栏中讲到其中的
原因）。
3.3.接下来就要决定究竟走那个点更好了。对此，我们需要求余下的m个点当中，每个点（都设为p）的“距离值x”。那
么，如何求每个点p的x值？首先要用到一个函数f(n)=g(n)+h(n)。其中，n为一个点；g(n)表示点n与点pn的距离，
可以用勾股定理求得，即((Xn-Xpn)^2 + (Yn-Ypn)^2)的平方根；h(n)表示点n与点pe的距离，也可以用勾股定理求
得，即((Xn-Xpe)^2 + (Yn-Ype)^2)的平方根。
3.4.最后我们可以求得f(n)的值，而x就等于f(p)，所以我们得知了剩余m个点中每个点的距离值x。我们下一步要走
的点就是x值最小的点！
3.5.总结3.3和3.4，总有:
x=f(p)
=g(p)+h(p)
=√((Xp-Xpn)^2 + (Yp-Ypn)^2) + √((Xp-Xpe)^2 + (Yp-Ype)^2)
（其中，√()表示平方根）
4.按照步骤3一直行走，并记录下行走的路线，直到走到终点（即pn=pe）或卡死在某个区域（有可能是在一个地方一直不
动，如3.2中n=0的情况；也有可能是一直在绕圈圈）。
使用感受：
A*算法的具体实现详见astar.py。完成后，我的第一感觉就是不稳定。我尝试了几次简单的寻路，A*算法可以正常运行。
但是，当我把障碍物的数量、终点离起点的距离逐渐增加时，A*算法开始出现了频繁的死循环（类似于步骤4举出的例子）。
甚至是在某些原本十分简单的地图上也出现了错误。并不是代码出现了问题（代码我是完全依照其工作原理来写的），而是
A*算法本身的局限性。我发现了这个算法的一些技术上的缺点，最重要的一点是它很难做到绕远路，举个例子，如下图：
口口口口口口口口口
口口口口口口口口口
口口墙墙墙墙口口口
口口口始口墙口口口
口口口口口墙口口口
墙墙墙墙墙墙终口口
口口口口口口口口口
口口口口口口口口口
在这张尺寸为9*8的地图中，设左上角坐标为(0, 0)， “口”为可以行走的空地，“墙”为障碍物，“始”(3, 3)为起点，“终”
(6, 5)为终点。用A*算法寻路，得到的结果不是绕墙到达终点，而是在点(4, 4)和点(3, 4)之间来回游走。
探索与研究：
为了解决A*算法的绕远问题，我开始了大块大块的代码重写。在代码不断地被删除和撤回的过程中，我发现了一个对绕远问
题至关重要的变量，在此，我将这个变量命名为“足迹”（footprints），字母表示为fp，它是我于A*算法最重要的发现。
fp是一个列表，它储存了在A*算法工作时走过的点，而fp的长度Lfp代表的是足迹会储存“我”当前所在位置（pn）的上Lfp步
的Lfp个点。当“我”每次排除要走的点（即进入步骤3.2）时，如果这8个待选择的点中，有的点在列表fp内时（即之前在Lfp
步内已经走过这个点了），也会把这个点排除在外具体实现详见（astar-pro.py）。理解这段话有点复杂，举原来的这个例
子来看：
口口口口口口口口口
口口口口口口口口口
口口墙墙墙墙口口口
口口口始口墙口口口
口口口口口墙口口口
墙墙墙墙墙墙终口口
口口口口口口口口口
口口口口口口口口口
在这里，我们设Lfp=5。
我们一步一步分析：
初始状态：我们默认起点(3, 3)也算是走过的点，因此(3, 3)被储存在fp中。
位置：(3, 3)
fp=[(3, 3)]
总路径：[]
走第1步：当前位置(3, 3)周围的8个点中有3个点为墙，所以剩余的点的数量m=8-3=5。根据x=√((Xp-Xpn)^2 + (Yp-Ypn)
^2) + √((Xp-Xpe)^2 + (Yp-Ype)^2)得到这5个点的距离值x（这里保留两位小数）：往左：5.47，往右：3.83，左下：
5.54，往下：4.16，右下：3.65。x值最小的点是往右下的点，因此下一步的位置是(4, 4)，把(4, 4)存入fp和总路径中。
位置：(4, 4)
fp=[(3, 3), (4, 4)]
总路径：[(4, 4)]
走第2步：重复步骤3，当前位置(4, 4)周围有5个墙和1个存在于fp中的点(3, 3)，因此m=8-5-1=2。然后求得各个点的x：
往左：4.16， 往上：3.83。然后求得应该往上走，因此下一步的位置是(4, 3)，同样地，把(4, 3)存入fp和总路径中。
位置：(4, 3)
fp=[(3, 3), (4, 4), (4, 3)]
总路径：[(4, 4), (4, 3)]
走第3步：与走第1、2步一样，重复一次步骤3。在第3步这里，当前位置(4, 3)周围有5个墙，2个点(3, 3)和(4, 4)存在
于fp中，因此m=8-5-2=1。m为1，这意味着我们只有一个选择，即使不经过比较距离值也能得出下一步走到点(3, 4)。
位置：(3, 4)
fp=[(3, 3), (4, 4), (4, 3), (3, 4)]
总路径：[(4, 4), (4, 3), (3, 4)]
走第4步：
位置：(2, 4)
fp=[(3, 3), (4, 4), (4, 3), (3, 4), (2, 4)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4)]
走第5步：这里有一个很重要的地方。我们之前设Lfp为5，这意味着fp最多储存有5个点。但在这一步，如果我们继续把点
(2, 3)存入fp，那么fp里就会有6个点，显然大于Lfp。因此，为了使fp的长度恒为5，在这一步及往后的所有步中，往fp
存入点的同时要删除fp中的第一个点。如现在，原来的fp为[(3, 3), (4, 4), (4, 3), (3, 4), (2, 4)]，往fp中存
入(2, 3)，得到[(3, 3), (4, 4), (4, 3), (3, 4), (2, 4), (2, 3)]；再删除fp的第一个点，得到[(4, 4), (4,
3), (3, 4), (2, 4), (2, 3)]。
位置：(2, 3)
fp=[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3)]
走第6步：
位置：(1, 3)
fp=[(4, 3), (3, 4), (2, 4), (2, 3), (1, 3)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3)]
走第7步：
位置：(1, 4)
fp=[(3, 4), (2, 4), (2, 3), (1, 3), (1, 4)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4)]
走第8步：
位置：(0, 4)
fp=[(2, 4), (2, 3), (1, 3), (1, 4), (0, 4)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4)]
走第9步：经过了前面8步，现在的位置还是在U字形的墙内部，似乎没有什么起色。但是，fp能使我们不走重复的路，所以
只要我们走过的路程足够大，我们就有可能走出墙体。
位置：(0, 3)
fp=[(2, 3), (1, 3), (1, 4), (0, 4), (0, 3)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3)]
走第10步：
位置：(1, 2)
fp=[(1, 3), (1, 4), (0, 4), (0, 3), (1, 2)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2)]
走第11步：我们在这一步成功走出U形墙，接下来只要走直线，再拐个弯，继续直走，就可以到达终点。
位置：(2, 1)
fp=[(1, 4), (0, 4), (0, 3), (1, 2), (2, 1)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2), (2, 1)]
走第12步：
位置：(3, 1)
fp=[(0, 4), (0, 3), (1, 2), (2, 1), (3, 1)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2), (2, 1),
(3, 1)]
走第13步：
位置：(4, 1)
fp=[(0, 3), (1, 2), (2, 1), (3, 1), (4, 1)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2), (2, 1),
(3, 1), (4, 1)]
走第14步：
位置：(5, 1)
fp=[(1, 2), (2, 1), (3, 1), (4, 1), (5, 1)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2), (2, 1),
(3, 1), (4, 1), (5, 1)]
走第15步：
位置：(6, 2)
fp=[(2, 1), (3, 1), (4, 1), (5, 1), (6, 2)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2), (2, 1),
(3, 1), (4, 1), (5, 1), (6, 2)]
走第16步：
位置：(6, 3)
fp=[(3, 1), (4, 1), (5, 1), (6, 2), (6, 3)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2), (2, 1),
(3, 1), (4, 1), (5, 1), (6, 2), (6, 3)]
走第17步：
位置：(6, 4)
fp=[(4, 1), (5, 1), (6, 2), (6, 3), (6, 4)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2), (2, 1),
(3, 1), (4, 1), (5, 1), (6, 2), (6, 3), (6, 4)]
走第18步：到达终点。
位置：(6, 5)
fp=[(5, 1), (6, 2), (6, 3), (6, 4), (6, 5)]
总路径：[(4, 4), (4, 3), (3, 4), (2, 4), (2, 3), (1, 3), (1, 4), (0, 4), (0, 3), (1, 2), (2, 1),
(3, 1), (4, 1), (5, 1), (6, 2), (6, 3), (6, 4), (6, 5)]
从本质上来说，footprints就是让你瞎跑，还是不带走重复路的那一种，最后总能跑出一条七拐八弯但又符合条件的路径。
它的优点是提高了A*算法寻路可以接受的地图复杂度，让其以一种易于理解的方式判断路径。它的缺点也很明显，复杂度过
高的地图会带来极多冗余的路程，降低了结果的质量，而又增加了计算时间。
问题延伸：
即使在增加了footprints后，A*算法的缺陷实在让人难以接受。有没有更好的方法让A*算法可以减少一些行走路程？在经
过我苦思冥想后，我把注意力聚焦到了Lfp上面，我开始了对Lfp的研究。
在上一个例子里，我在最开头设Lfp的值为5。这个5不是随便设的，它是经过演算后得出的最优的Lfp。什么是“最优Lfp”？
你可以理解为：在同一个地图中，使用不同的值作为Lfp来做A*算法，得到的结果可能是不同的（一些结果的路径很长，一
些稍微短一点，还有些结果压根无法求得路径，即死循环），而如果一个Lfp做A*算法的结果是所有结果里面最小的，那么这
个Lfp就是最优Lfp。最优Lfp还有另外一个条件，如果有多个Lfp的结果相等且都是最小的结果，，那么最优Lfp就是它们当
中值最小的Lfp，再举个例子：
Lfp的值 0 1 2 3 4 5 6 7 8 9 10 11 12 13
结果的路程长度 - - 19 17 15 15 14 14 14 14 15 16 17 20
问这个例子中最优Lfp为多少。首先看结果最小的Lfp，通过比较可以得知，当Lfp为6、7、8、9时，结果最小，路程为14。
然后在根据最优Lfp的定义，得知最优Lfp是6、7、8、9这四个值当中最小的一个。显而易见地：6<7<8<9，所以在这个例子
当中，最优Lfp为6。
以上是关于最优Lfp的解释，最优Lfp是降低A*算法路径过长问题的关键点。对于这个问题，我将其与最优Lfp结合起来，得
到的思路是：在做A*算法时，先求其最优Lfp，再计算路径。这样可以让算法在某些情况下得到更短的结果。那么，问题又来
了，怎样才能知道最优Lfp是多少呢？
我的解决方案是：暴力枚举。所谓暴力枚举，听起来很高大上，但其实就是一个一个地测试。详细过程是第一次设Lfp为0，
然后用A*算出结果的长度；第二次设Lfp为1，算出结果的长度......以此类推，直到当Lfp=MaxLfp+1时结束。最后比较所
有的结果，长度最短的就是最终的路径。其中，MaxLfp是一个需要我们自己设定的常数，且MaxLfp>=0。MaxLfp表示的是
Lfp的最大取值（即总有0<=Lfp<=MaxLfp）。这样又引出一个问题：如何求MaxLfp？首先我们要知道MaxLfp有两个要求。
一是要保证0<=最优Lfp<=MaxLfp，这样做可以使最优Lfp在暴力枚举的范围内，防止出现没有测试到最优Lfp的情况，因此
MaxLfp应足够大；二是测试的次数要尽量少，否则算法的速度就会非常慢，因此MaxLfp又应足够小。综合以上两点，在这两
个要求之间做一个平衡，找到一个平衡点，这个平衡点就可以作为MaxLfp。对于如何平衡这两个要求，我仍没有什么好的方
法，但这里有一个可供使用的公式：MaxLfp=(a+b)/2。其中，a、b分别为地图的长和宽。要注意的是，这个公式未被证明
有用，它仅适用于70%的情况（或许更糟），因此绝对不能将此公式用于重要的地方，尤其是商用，以免出现难以觉察的漏洞。
另外，还有一种方法，就是把MaxLfp设置得尽量大，但代价是极慢的速度，而且这个方法只在你知道最优Lfp大致在什么区
间内才有效。
总之，以最优Lfp来减少A*算法结果的长度是一种不算很复杂，实现难度较低，但速度慢的方式。而且无法找到MaxLfp的精
确值，只能知道它的大致值。
关于细节：
关于在介绍A*算法工作原理中，步骤3.2所出现的问题的解释。
在A*算法中，如果m=0（即在周围8个点都被排除的情况下），你仍有可能到达终点，这个问题要分类讨论：
1.周围8个点是地图边界或墙。此时m=0，显而易见，在这种情况下，你无路可走，不可能到达终点。另外，如果你处于
这种情况下，你的坐标一定等于起点的坐标。这是因为你不可能主动地进入一个封闭空间，也不可能主动地从一个封闭
空间里出去。
2.周围8个点中，至少有一个点被排除的原因是它存在于fp当中，即你最近已经走过了这个点。此时m=0，但你仍有可能
到达终点，原因是fp中的点会逐渐地按先后顺序被删除。可能此时周围某个点存在于fp中，你无法动弹；但经过w步后
（w<=Lfp），这个点会从fp中被删除，你可以从这个点离开封闭空间，所以你仍有可能到达终点。