算法集锦

算法集锦之路径规划算法(1)

 
 
Picture of admin AM
算法集锦之路径规划算法(1)
by admin AM - Sunday, 13 August 2017, 11:10 AM
 

如何通过百度地图找到去飞机场的最短路径?吃豆人Pacman游戏中一个幽灵(ghost)应该如何尽快吃到食豆人(pacman)呢?这两个问题,有什么共同的地方呢?




它们都与路径搜索(path-finding)有关。

对于吃豆人游戏,我们可能需要一个迷宫地图:依据迷宫地图中相邻的正方形之间的连接情况,找到一条沿着黑色方块的路线,就可将幽灵导向吃豆人。而为了找到从火车站到机场的行车路线,我们可能会使用百度地图,基于道路的连接情况,从中找到最合适的路径,若没有道路直接连接火车站与机场,则可以通过相关的几条路转接。

以Pacman游戏为例,问题可以简化为如何把幽灵如何从起始点移动到目标点(Pacman所在的位置)。为了实现这一点,游戏程序需要确定幽灵的移动路径,以便到达Pacman当前的位置,然后设计移动幽灵的动画。注意,可能会找到多条路径,一般程序会选择最短的路径。




图3 简化的Ghost找Pacman的算法


图3是一个简化的路径搜索算法的演示。我们先假定移动的规则:墙壁由灰色方块组成,可以通过的位置为空。在每个步骤中,游戏角色可以从一个正方形移动到相邻的正方形,但是不能对角移动。在每个步骤中移动1个格子使幽灵更靠近目标 - Pacman当前位置。但是,“靠近目标”是什么意思?朝着目标直线行进往往会导致撞墙。该算法需要确定哪个周围的方块确实“更靠近目标”,我们可以通过为每个方块分配一个“成本”来代表从该方块到目标顶点所需的最少移动步数。

以下是为每个方块分配成本的算法:
1)从目标方块开始。标记为0,表示离开目标方块为0步;
2)找到距离目标方块正好一步之遥的迷宫中的所有方块。 用数字1标注它们。在该迷宫例子中,目标点是出口方块,只有一个方块距离出口方块1步,标记为1。
3)现在找到距离目方块正好2步的迷宫中的所有方块, 这些方块距离标记为1的方块还有一步,并且尚未被标记,用数字2标记这些方块。
4)标记距离目标方块正好3步的迷宫中的所有方块,它们与标记为2的方块距离一步,尚未被标记。用数字3标记这些方块。
5)按照与目标距离增加的顺序,在迷宫中标记所有方块。用数字k标记方块后,找到与标记为k的方块距离为1的并且尚未标记的方块,为它们标记为k+1。

最后,该算法会为角色出发的方块做标记。此时,程序可以从该方块开始依次选择方块,使得方块的数字总是依次减少,一直到目标方块,把这些方块依次连接起来,就是得到的搜索路径。

本文描述的是一种非常简单的路径搜索算法,属于路径规划算法。在实际应用中,常见的路径规划算法有:最速下降法、部分贪婪算法, Dijkstra算法、Floyed算法、SPFA算法(Bellman_Ford的改进算法)、A*算法、D*算法、图论最短算法、遗传算法、元胞自动机、免疫算法、禁忌搜索、模拟退火、人工神经网络、蚁群算法、粒子群算法等等。