课堂模拟大赛教学材料

人工智能之搜索问题

Posted by Kingtous on June 12, 2019

A*搜索核心

$f(x)$为总耗散

$g(x)$为当前在x点的耗散

$h(x)$为当前在x点预估的还需要的耗散

八数码中h(x)估算方法

g(x)我们这儿直接等于从初始情况走到前面局面x走过的步数。g(初始)=0,我们重点关注h(x)的计算

  • 错位法
    • image-20190613171024138
  • 曼哈顿距离

  • 线性冲突(Linear Conflict)

  • 模式数据库

  • 游走距离(Walking Distance)

搜索小例子

image-20190613170927078

A*搜索、DFS、BFS在具体例子中的比较

image-20190613165143300-0415903