启发式（有信息）搜索 Heuristic (Informed) Search ( 我们试着做一些聪明的选择) R&N: Chap. 4, Sect. 4.13 1 启发函数 h(N) 0 估计从状态（N ）到目标状 态的耗散 其值与当前的搜索树无关；仅取决于状态 STATE(N) 和目标测试 GOAL? Example: h 1 (N) = 不在位的牌数 = 6 为什么它是对目标距离的一个估计呢？ 启发函数 Heuristic Function 1 4 7 5 2 6 3 8 STATE(N) 6 4 7 1 5 2 8 3 Goal state 2 h 1 (N) = 不在位的牌数 = 6 h 2 (N) = 每个数码牌与其目标位置的 (Manhattan) 距离和 = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13 h 3 (N) = sum of permutation inversions = n 5 + n 8 + n 4 + n 2 + n 1 + n 7 + n 3 + n 6 = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16
