A*搜索核心
\[f(x)=g(x)+h(x)\]$f(x)$为总耗散
$g(x)$为当前在x点的耗散
$h(x)$为当前在x点预估的还需要的耗散
八数码中h(x)估算方法
g(x)我们这儿直接等于从初始情况走到前面局面x走过的步数。g(初始)=0，我们重点关注h(x)的计算
- 错位法
-
曼哈顿距离
-
线性冲突(Linear Conflict)
-
模式数据库
-
游走距离(Walking Distance)
- …
搜索小例子
A*搜索、DFS、BFS在具体例子中的比较
