如何选择启发式函数

• 对8数码问题来说：
  • $h_1(n)$ = number of misplaced tiles(错位的棋子数)
  • $h_2(n)$ = total Manhattan distance(所有棋子到其目标位置的水平竖直距离和)
    (i.e., no. of squares from desired location of each tile
  • 如下起始状态与结束状态
    
  • 在上述两个启发式函数下，对到达目标状态的估计耗散为：$h_1(S)=8$
    $h_2(S)=3+1+2+2+2+3+3+2=18$

如何评价启发式函数

• If $h_2(n)\ge h_1(n)$for all n (both admissible)
• then $h_2$ dominates $h_1$ (dominate 统治、占优)即$h_2$ 优于$h_1$
• $h_2$ is better for search
• 典型的搜索成本(扩展的平均节点数)：
• d=12
  • IDS = 3,644,035 nodes(迭代加深深度优先搜索)
  • $A^{\ast }(h_1)$ = 227 nodes
  • $A^{\ast }(h_2)$ = 73 nodes
• d=24
  • IDS = too many nodes
  • $A^{\ast }(h_1)$= 39,135 nodes
  • $A^{\ast }(h_2)$ = 1,641 nodes
• 给定任何可容许的启发函数$h_a，h_b$$$h(n)=max(h_a(n)；h_b(n))$$
  也是可容许的并且dominates$h_a，h_b$
• 使用 评价函数$f(n)=g(n)+h(n)$搜索
  • h(n)=错放数字个数
  • g(n) = 节点深度
  • 结果如下：

松弛操作

• 有些复杂问题不能像上面一样直观的得到启发函数，此时就要考虑松弛操作
• 如下移动三角至目标位置
• 这里在有障碍物的情况下，很难得到一个满足要求(预估耗散永远不会大于实际耗散)启发式函数，因此在这里考虑一个更简单情况，使用更简单情况下的实际耗散作为启发式函数，这样就可以保证估计耗散不会大于实际耗散，启发式函数采用起点到终点的曼哈顿距离
  因此，这里可以将松弛操作理解为去除问题中的部分约束、限制
• 构造松弛问题
  • 原问题：一个棋子可以从方格A移动到方格B，如果A与B水平或者垂直相邻而且B是空的
  • 松弛1：一个棋子可以从方格A移动到方格B，如果A与B相邻 — h2
  • 松弛2：一个棋子可以从方格A移动到方格B，如果B是空的
  • 松弛3：一个棋子可以从方格A移动到方格B —h1
• 如果有一个可采纳启发式的集合$h_1,\dots ,h_m$
  $$h(n)=max(h_1(n),\dots ,h_m(n))$$可采纳并比成员启发式更有优势

评价函数f(n)

• h(n) — heuristic, estimate of cost from n to the closest goal
  （节点n到目标节点的最低耗散路径的耗散估计值）
• g(n) — path cost to n （初始节点到这个节点的路径损耗的总和）
• Possible evaluation functions:估计通过节点n的解决方案路径的总成本