算法流程

  • 维护一个容器用来存储待访问的节点；维护一个数组用来标记已访问的节点；维护一个数组用来标记父节点
  • 进行初始化
  • 循环遍历容器：
    • 按照预设规则弹出容器中的节点，将这个节点标记为已访问
    • 如果弹出的节点是终点，则证明找出路径，根据父节点回溯整条路经，结束
    • 扩展邻居节点，将未访问过且非障碍物的节点按着某种顺序放入容器中，记录父节点
  • 结束

1. 广度优先与深度优先

1.1 广度优先(BFS)

广度优先算法使用的容器为队列(queue)，遵循的规则是先进先出。

1.2 深度优先(DFS)

深度优先算法使用的容器为栈(stack)，遵循的规则是先进后出。

1.3 二者对比

  • 二者都只能用于各边代价相同的情况。

  • BFS能找到全局最优解，但是速度比较慢

  • DFS不一定能找到全局最优解，但是速度比较快

Djikstra算法需要维护一个容器用来记录每个节点的cost，当扩展节点未被扩展过则cost为inf，当这次扩展时cost小于记录的cost则更新，并添加到open_list里面

若是不判断cost，则每次扩展都会把扩展的节点添加进去，虽然最优队列会保证被访问的节点一定是cost最小的，但是同一个节点会被重复添加进open_list，里面的元素会过多