3.8 本章小结
- 许多实际问题可以抽象为在图中进行路径搜索的问题。
- 宽度优先搜索和深度优先搜索可以在没有任何图以外的额外信息的情况下通过图来找到路径。
- A 搜索可以使用启发函数,来估计从一个节点到目标节点的花费。如果这个估计低于实际花费,A能保证找到最低花费路径。
- 迭代深化搜索和深度优先分支界限搜索可以用来找到最低花费路径,且能比像A 之类的算法节省更多的内存,因为A算法会储存多条路径。
- 当图很小的时候,动态规划搜索可以用来纪录从每一个节点到目标节点的最低花费路径的实际花费,这可以用来找到最优路径的下一段弧。
时间: 2024-07-30 17:28:30