寻找最短路径

BFS

BFS 只是访问 node，但是不会构造路径

frontier = Queue()
frontier.put(start )
reached = set()
reached.add(start)

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in reached:
         frontier.put(next)
         reached.add(next)

路径

这时候把用于记录重复的数组，变为 parent 或者叫 come_form 记录父节点，或者叫从哪来的。就记录的路径

frontier = Queue()
frontier.put(start)
came_from = dict() # path A->B is stored as came_from[B] == A
came_from[start] = None // this！

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current // this！

此时就能反推，从 goal 开始访问 come_from 就能得到最短路径

current = goal 
path = []
while current != start
   path.append(current)
   current = came_from[current]
path.append(start) # optional
path.reverse() # optional

提前退出

发现到 goal 就直接退出，BFS 不需要访问所有路径

image-20220522215007257

权重

不同路径会花费不同时间，算上权重，结果会和单纯的 BFS 不一样。

储存用的数据结构，也增到了三个。遍历用的、路径用的、权重用的

  1. 首先加权重要改变记录图的结构，从数组变为优先队列。优先队列先得到最小值

  2. 其次需要新增数据结构记录从开始到此节点的路径花费的权重，从路径最短转为权重最小

  3. 每次遍历时，需要计算当前权重。如果此节点没有访问过，或者小于之前访问此节点时的权重，才访问此节点

Dijkstra’s Algorithm (or Uniform Cost Search) ：

image-20220522220334065

搜索预测，贪婪 BFS

在 BFS 和 Dijkstra’s 中，都搜索了一层中所有节点，其实并不需要，只是想接近目标。

这时就需要让更接近目标的方向，有更多的权重，所以需要改变计算权重的方式

定义一个计算目标距离的函数image-20220522221335661

Dijkstra’s 使用真是距离，现在替换为定义的函数，并且不需要记录每个节点距离目标的权重image-20220522221614636

A*

Dijkstra’s 可以找到最短路径，但是会去搜索没有希望的路径，不会预测

贪婪 BFS，只去寻找最有希望的方向，但不一定会找到最短路径

这时候就需要他俩相结合，就得到了 A*

代码和 Dijkstra’s 很像，只是在其基础上，另外增加了权重

image-20220522221838807

Contents