终于完全了解A*到底是什么玩意儿了
对于当前的决策,选取当前花费+预估花费最小来拓展。
因为假如预估出现失误,那么很可能就会延伸到一个错误的决策点,而这个决策点偏偏就是ed,而由于预估失误,其他点的当前花费+预估花费比这个错误的花费大,那么答案就错了。
所以预估花费要比最小花费小。
证一下:
f函数为预估值,g函数为理论最小值,s函数为到达当前的费用
设通过点x延伸是最优的
由于预估失误,此时s(x)+f(x)>s(y)+f(y) 而其实 s(x)+g(x)<s(y)+g(y)
那么先被取出的是y,s(ed)=s(y)+c y->z ed
但是s(y)+c y->ed = s(y)+g(y) > s(x)+g(x) > s(x)+f(x)
先出堆的必然是x,重新更新一次edpoj2449 k短路 QAQ
poj1077 宽搜第一题做烂的八数码
没什么好放的