10.29A*算法、一致代价搜索

A*算法

流程

在更新邻居节点时，包含两部分，首先是从未到过，其次最重要的是，之前到过，但是现在发现有更短的路径（即从起点到该点），那么就需要将这个邻居点重新入队，然后在新值的基础上重新更新

所以这也是只能在只有正边的情况下使用，因为如果有负边，就可能形成一个总和为负的环，然后不断走这个环造成死循环

启发式函数h(n)很重要

一致代价搜索

基本流程