关于此实验
地图导航、机器人和电子游戏都要解决同一个问题：找到从起点到目标点成本最低的路线。在这个网格中，沿道路前进一步的成本为 1，进入泥地一步的成本为 5，而墙壁无法穿越。观察三种经典算法如何从 S 向外扩展。广度优先搜索统计步数，不考虑泥地；戴克斯特拉算法总是优先探索成本最低的格子；A* 则会加入对剩余距离的估算，从而直奔目标。绘制自己的地图，比较每种算法需要完成多少工作。
学习目标
- 将地图表示为一个由相邻格子连接而成的图，并为每一步设置成本
- 描述广度优先搜索如何按步数相同的环状层级进行探索
- 解释为什么在每一步的成本不同的情况下，Dijkstra 能找到成本最低的路径
- 解释 A* 的启发式算法如何在不丢失最优路径的情况下减少探索的格子数量
- 比较各算法找到的路径成本以及它们所需的工作量
使用方法
- 1选择 BFS 并点击“搜索”。它找到的路径会经过泥地吗？在表格中查看路径成本。
- 2选择 Dijkstra 并再次搜索。比较它与 BFS 找到的路径及其成本。
- 3选择 A*。它的路径成本和 Dijkstra 相同吗？它少探索了多少个格子？
- 4观察搜索过程中的蓝色边界。Dijkstra 和 A* 的边界形状有什么不同？
- 5画一堵墙，封住泥地周围的道路。哪个算法会改变路径？为什么？
- 6点击“清空地图”，然后把 S 和 G 拖远。没有障碍物时，每种算法会探索多少个格子？
模型
假设
- 只能向上、向下、向左或向右移动。进入道路格子的代价为 1，进入泥地格子的代价为 5；墙壁格子无法进入。
- BFS 在搜索时将每一步的代价都视为 1，因此会找到步数最少的路径。表中该路径的代价是真实代价，其中包括泥地的代价。
- 如果两个格子的优先级相同，先加入的格子会先被探索，因此在相同地图上每次运行的探索顺序都完全相同。
- 一旦目标从前沿集合中取出，搜索就会停止，因为此时已经确定到达目标的最低代价。
在课堂上试试这个实验
- Q1为什么 BFS 使用的步数更少，找到的路径却可能比 Dijkstra 的代价更高？
- Q2如果所有格子都是道路，BFS 和 Dijkstra 找到的路径代价会相同吗？为什么？
- Q3如果估算值 h 是曼哈顿距离的十倍，A* 会有什么变化？
- Q4为什么目标位于开阔区域时，A* 探索的格子更少；而在迷宫中，探索的格子数却与 Dijkstra 大致相同？
- Q5卫星导航能在不到一秒的时间内，为穿越一个拥有数百万个道路交叉口的国家找到快速路线。这个实验中的哪些理念让这一切成为可能？
常见问题
哪种算法最好？
这取决于问题。如果每一步的代价都相同，BFS 简单且正确。代价各不相同则使用 Dijkstra。如果能很好地估算到目标的距离，A* 就能在探索更少格子的情况下，得出与 Dijkstra 相同的结果。
什么是边界集合（frontier）？
前沿是已经到达但尚未探索的格子的集合。每种算法每次都会从前沿中取出一个格子；它们之间的区别仅在于决定下一步取出哪个格子的规则。
这些算法能处理负代价吗？
Dijkstra 和 A* 假设每一步的代价都不是负数。如果存在负代价，先前已确定的格子之后可能会出现代价更低的路线，因此需要使用 Bellman-Ford 等其他算法。