主要内容
课程: 计算机科学理论 > 单元 1
课程 1: 算法简介寻路
有时候，听起来非常不同的问题，在解决这些问题时所用的方法却很相似。英国皇室，Pac-Man游戏和开车去奥兰多有什么共同之处？它们都涉及路径查找或路径搜索问题：
- 现任威廉王子与1693年捐赠威廉和玛丽学院的威廉三世国王有什么关系？
- 游戏中，鬼应该走那条路径，才能最快到达Pac-Man ？
- 从德克萨斯州达拉斯开车到佛罗里达州奥兰多的最佳方式是什么？
要回答上面任何一个问题，我们必须知道一些信息。
例如，英国王室的家谱显示了直接相关的人之间的联系。威廉王子是查尔斯·菲利普·阿瑟·温莎的儿子。查尔斯是伊丽莎白二世女王的儿子。您需要做的是，根据这些直接关系，在家谱中找到连接威廉王子和威廉三世的一条最短路径。正如您从下面的家族树中看到的，它可能需要相当多的连接关系。
对于Pac-Man游戏，我们需要知道迷宫的地图。下面这张地图显示了迷宫中相邻的开放方块之间的连接关系——如果中间有一堵墙的话，就是无法连接——您的任务是找到一条沿着黑色方块的小路，把幽灵鬼带到 Pac-Man。
为了找到从达拉斯到奥兰多的行车路线，我们需要使用一张能显示附近城市之间的连接、道路的美国地图。虽然没有一条道路直接连接达拉斯和奥兰多，但可以把几条道路顺序连接起来，达到目的地。
迷宫游戏
迷宫游戏很有趣，所以我们选一个深入研究。在我们的游戏中, 游戏角色可以导航到迷宫中的目的地。
作为玩家，您可以通过单击迷宫中的下一个目标来控制角色，计算机会找出如何将角色移动到那里的路线。 目标用标记为 "GOAL" 的红色矩形标记，角色从它所在的第一个位置 (开始正方形) 开始。 尝试在下面这个迷宫里玩一下：
注意角色是如何移动到目标的？要到达目标，程序需要确定角色应该遵循的精确的动作集，以到达玩家点击的位置，然后对这些动作进行动画处理。该角色可能有多个路径可能到达目标，程序需要选择其中的最佳路径。
在决定算法之前，首先需要确定移动规则：墙是由灰色方块组成的，而合法的路径是空白的位置。在每个步骤中，角色可以从一个方块移动到相邻的方块。这个角色，就像国际象棋里的车，不能沿对角线移动。
以下是此程序使用的算法背后的思路：每走一步，都要距离目标 (玩家单击的位置)更近一个方块。但 "离目标更近" 是什么意思呢？沿直线向目标前进，往往会导致角色撞到墙上。因此该算法需要确定周围的哪个方块确实 "更接近目标"，我们可以通过为每个方块分配一个 "成本" 来实现这一点，该成本表示角色从该点到达目标所需的最小步数。下面是为每个方块分配成本的算法：
- 从目标方块开始。目标离目标有多远？零步，用数字0标记目标。
- 找到迷宫中距离目标方块只有一步的所有方块。用数字 1 来标记。在这个迷宫中，如果目标方块是出口方块，那么只有一个方块与它距离一步。
- 现在找到迷宫中与目标点相距为两步的方块。这些方块与刚才已经标识为 1 的方块距离为 1 步，且还没有被标识，现在我们把它们标识为 2。
- 接着标记迷宫中距离目标点需要走三步的所有方块，这些方块与刚才标记为 2 的方块相距 1 步，且还没有被标识。把这些方块标识为 3。
- 继续按照与目标点距离的远近，标识迷宫中的方块。在标记了方块为数字
最终，该算法标记了角色开始位置的方块。然后，程序就可以通过从起始位置选择一个方块序列来找到通往目标的路径，沿着这条路径，方块上的数字总是持续减少。如果你把这个数字当做是正方形的高度，那么整个过程就像下坡一样。
您可以在下面玩一下这个成本标识算法。点击 "重新计算" 就可以清空重来。
当玩家想要从起点位置到达目标点，该怎么做？根据方块标识算法，起点与目标的距离是 13 步。下图显示了角色的可能位置之间的关系，起点、目标、距离目标的每一个位置的最短距离：
我们立刻看到，在起点位置的南方有一个方块，距离目标只有 12 步远。因此第一步路径是向南移动。这个方块的南方是 11。 继续向南。 再向南到达10。然后向东到达 9。再向东两次到达 7，然后向北五次到达 2。再向西一步到达 1，最后向北一次，就到达目标点了。
我们现在不会展开说明到底怎样进行迷宫搜索算法，但您可能发现使用 JavaScript 来表示迷宫和角色位置，以及执行算法，是非常有意思的。
