| 人工智能笔记02 启发式搜索 | 您所在的位置：网站首页 › 搜索朱亚如 › 人工智能笔记02 启发式搜索 |
人工智能笔记02 启发式搜索
|
搜索算法 Ø 利用计算机的高性能来有目的的穷举一个问题解空间的部分或者所有的 可能情况，从而求出问题的解的一种计算机算法 启发式搜索算法Ø 利用启发式信息引导算法搜索，达到减少搜索范围，降低问题复杂度的 目的 Ø 将人类求解问题的经验固化到求解算法 估价函数基于一般图搜索算法，定义一个评价函数 f f f，对当前的搜索状态进行评估，从Open表中找出一个最有希望的节点来扩展。 f的一般定义 f ( x ) = g ( x ) + h ( x ) f(x)=g(x)+h(x) f(x)=g(x)+h(x) g ( x ) g(x) g(x):从根节点（起始节点）到当前节点的估计路径长， g ∗ ( x ) 的 估 计 g^*(x)的估计 g∗(x)的估计 h ( x ) h(x) h(x):从当前节点到目标节点的估计路径长， h ∗ ( x ) 的 估 计 h^*(x)的估计 h∗(x)的估计 g ∗ ( x ) g^*(x) g∗(x):从根节点（起始节点）到当前节点的最短路径长 h ∗ ( x ) h^*(x) h∗(x):从当前节点到目标节点的最短路径长 爬山法 Ø只考虑与目标之间的差距，即 g ( n ) = 0 g(n)=0 g(n)=0 分支界限法 Ø 总是扩展具有最小耗散值的路径 Ø 使用g(n)，h(n)=0 ** 动态规划法** Ø 总是扩展具有最小耗散值的路径 Ø 总是删除明显不可能的路径 Ø 使用g(n)，h(n)=0 A算法伪代码 1 G=G0 (G0=s), Open := (s), 计算f(s) := g(s) + h(s), Closed=(); 2 Loop: If Open = ( ) Then Exit(Fail); 3 n := First(open), Remove(n, Open), Add(n, Closed); 4 If Goal(n) Then Exit(Success); 6 Expand(n) →{mi}, 计算f(n, mi) := g(n, mi) + h(mi), G:=Add(mi, G); 7 标记和修改指针： Add(mj, Open), 标记mj到n的指针； //新节点 If f(n, mk) < f(mk) Then f(mk) := f(n, mk), //Open表中未扩展节点 标记mk到n的指针； If f(n, ml) h 1 ( n ) h_2(n) > h_1(n) h2(n)>h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。 算法改进因A算法第6步对 m 1 m_1 m1 类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。 解决的途径: 对h加以限制：对h增加适当的限制，使得第一次扩展一个节点时，就找到了从S到该节点的最短路径。 对算法加以改进：对算法加以改进，避免或减少节点的多次扩展。 改进的条件: 可采纳性不变 不多扩展节点 不增加算法的复杂性 实践
|
模板代码【本文地址】