- 时间紧迫，直接上用法
- 设当前状态state到目标状态所需要的代价的估计值尾f(state)
- 设在未来的搜索中，实际求出的从当前状态state到目标状态的最小值为g(state)
- 对于任意的state，应该有f(state)<=g(state)
- 也就是说，估价函数不能大于未来的实际代价。
- 即使估价不太准确，导致非最优状态s先被扩展，但是随着”当前代价“的不断累加，在目标状态被取出之前的某个时刻：
- 根据s并非最优，s的当前代价就会大于从起始状态到目标状态的最小代价
- 对于最优解搜索路径上的状态t，因为f(t)<=g(t),所以t的[”当前代价“+f(t)]必定小等于[t的”当前代价“+g(t)],而后者的含义就是从起始状态到目标状态的最小代价。
- 结合1、2，可知 [ t的当前代价+f(t) ] 小于s的当前代价。因此，t就会被从堆中取出进行拓展，最终更新到目标状态上，产生最优解。
- 总之，只要保证于任意状态都有f(state)<=g(state)，A*算法就一定能在目标状态第一次从堆中被取出时得到最优解，并且爱搜索过程中每个状态只需要拓展一次。
- f()函数应该尽可能地反应实际代价地变化趋势和相对大小关系。
- 比如求第k短路时，选择x到ed的最短路径作为f()函数。
撰写