人工智能第一章讲义.pptVIP

* 4 其他的有哪些信誉好的足球投注网站算法 爬山法（局部有哪些信誉好的足球投注网站算法） 如果对于任何n，当g(n)=0时，f(n)=h(n), A*算法就成为爬山法。 爬山法优先扩展距离目标节点的耗散值最小的节点。 * 4 其他的有哪些信誉好的足球投注网站算法（续1） 动态规划算法 如果对于任何n，当h(n)=0时， f(n)=g(n), A*算法就成为了动态规划法。 动态规划算法优先扩展具有最小耗散值分支路径上的端节点。 * * 如果不结束的话，引理2.1与引理2.2产生矛盾 * 由定理2，一定结束，所以f*(t)(＝f*(s))会被扩展，所以f(n)f*(s)的节点定被扩展 * A算法（续） ADD(mj, OPEN), 标记mj到n的指针； IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 标记mk到n的指针； IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml), 标记ml到n的指针, ADD(ml, OPEN); 7 OPEN中的节点按f值从小到大排序； 8 GO LOOP； * …... …... …... …... …... mj mk ml n a b * 一个A算法的例子 定义评价函数： f(n) = g(n) + h(n) g(n)--从初始节点到当前节点的耗散值，单位耗散 时为当前节点的深度（即所走的步数）。 h(n)-- 当前节点“不在位”的将牌数，即估计要走 的步数。 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 * h(n)计算举例 h(n) =4 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 目标状态 当前状态 * 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 s(4) A(6) B(4) C(6) D(5) E(5) F(6) G(6) H(7) I(5) J(7) K(5) L(5) M(7) 目标 1 2 3 4 5 6 有哪些信誉好的足球投注网站表 7 规则: (1)右移 (2)下移 (3)左移 (4)上移 * 有哪些信誉好的足球投注网站过程的OPEN表和CLOSED表 OPEN表 CLOSED表 初始化 ( S(4) ) ( ) 返回 第1循环(B(4) A(6) C(6) ) (S(4)) 第2循环(D(5)E(5)A(6)C(6)F(6) ) (S(4)B(4)) 第3循环(E(5)A(6)C(6)F(6)G(6)H(7)) (S(4)B(4)D(5)) 第4循环(I(5) A(6)C(6)F(6)G(6)H(7)J(7)) (S(4)B(4)D(5)E(5)) 第5循环(K(5)A(6)C(6)F(6)G(6)H(7)J(7)) (S(4)B(4)D(5)E(5)I(5)) 第6循环(L(5)A(6)C(6)F(6)G(6)H(7)J(7)M(7)) (S(4)B(4)D(5)E(5)I(5) K(5)) 第7循环结束，第4步成功退出 解路径：S(4) B(4) E(5) I(5) K(5) L(5) * 2 最佳图有哪些信誉好的足球投注网站算法A*（A*算法） 在A算法中，如果满足条件： h(n)≤h*(n) 则A算法称为A*算法。 求解最佳解的条件 * A*条件举例 8数码问题 h1(n) = “不在位”的将牌数，即估计需要走的步数 h*(n) = 当前节点n到达目标节点需要走的实际步数 必有：h1(n)≤ h*(n) 满足A*算法条件 * A*条件举例 8数码问题 h2(n) = 将牌“不在