北大公开课-人工智能基础 21 通过搜索求解问题之有信息搜索（二）A*搜索

A*搜索，类似于剪枝

扩展节点的评价函数，包括当前节点到该节点的代价，加上该节点到目标节点的代价，之和。

优先扩展这两个代价之和最低的节点。

（a）初始节点：arad，

（b）优先扩展sibiu，因为sibiu的两个代价之和最低

以此类推，

A*搜索，本质上也是一种迭代加深深度优先搜索。

先扩展深度，然后选择综合路径代价最低的节点进行下一级扩展

本质上还是一种深度优先搜索，但是这种搜索是基于估算最低代价的搜索，比起单纯的深度优先搜索，内存使用较低

有了评价函数的参与，A*搜索更有目的性，且内存占用较小，搜索效率较高。