2013年第二章产生式系统的有哪些信誉好的足球投注网站策略-.ppt

第6次课 2013年09月19日 中秋节 * 说明了P中有一个节点nj，他自己在closed中，nj+1在open中 * nk=n * 注意：nj＋1是在open中 对算法加以改进 一些结论（推论）： OPEN表上任一具有f(n) f*(s)的节点n定会被A*扩展。 A*选作扩展的任一节点，定有f(n)≤f*(s)。 上面两个推论是改进A*算法的理论基础。 改进的出发点（1） A*算法，按照结点的f值从小到大排序OPEN表中的结点。 以f*(s)界将OPEN表划分为两个部分： 1) f值小于f*(s)的节点（称为NEST) 2) f值大于等于f*(s)的节点 改进的出发点（2） OPEN = ( … … … … ) f*(s) f值小于f*(s)的节点 f值大于等于f*(s)的节点 推论：A*选作扩展的任一节点，定有f(n)≤f*(s)。 fm：到目前为止已扩展节点的最大f值，用fm代替f*(s) s(10) A(1) B(5) C(8) G 目标 6 3 1 1 1 8 一个例子： OPEN表 CLOSED表 s(10) s(10) A(7) B(8) C(9) A(7) s(10) B(8) C(9) G(14) A(5) C(9) G(14) C(9) G(12) B(7) G(12) A(4) G(12) G(11) B(8) s(10) A(5) B(8) s(10) C(9) A(5) s(10) B(7) C(9) s(10) A(4) B(7) C(9) s(10) 改进的出发点（3） 由前面的推论： OPEN表上任一具有f(n) f*(s)的节点n定会被A*扩展。（NEST部分） 因此，NEST中的节点，不论是先扩展还是后扩展，在A*结束前总归要被扩展。因此，如果改变NEST中结点的次序，不会影响到算法扩展结点的个数。 对NEST中的节点，按照f(n)=g(n)（即令h≡0，是单调的）次序扩展，既可避免重复扩展结点，又不会增加扩展结点的个数。 修正过程A 1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0; 2, LOOP: IF OPEN=( ) THEN EXIT(FAIL); 3, NEST:={ni|f(ni)fm} IF NEST ≠ ( ) THEN n:=NEST中g最小 的节点 ELSE n:=FIRST(OPEN), fm:=f(n); 4, …, 8: 同过程A。 s(10) A(1) B(5) C(8) G 目标 6 3 1 1 1 8 前面的例子： OPEN表 CLOSED表 fm s(0+10) s(0+10) 10 A(6+1) B(3+5) C(1+8) s(0+10) C(1+8) 10 A(6+1) B(2+5) s(0+10) C(1+8) B(2+5) 10 A(3+1) s(0+10)C(1+8)B(2+5)A(3+1) 10 G(11+0) 评价函数的启发能力（p46） A算法的启发能力和选择启发函数h(n)的关系？ 评价函数的启发能力（1） 一般来讲，启发能力越强，有哪些信誉好的足球投注网站效率越高。有时，如果选用不满足A*算法的h函数，虽然会牺牲找到最佳解的可能，但可使启发能力得到改善。有利于求解一些较难的问题。 以八数码问题为例。 初始状态 目标状态 评价函数的启发能力（2） 选用启发函数h(n)=p(n)时，仍不能估计出交换两个将牌位置难易程度的影响。 引入S(n)分量，反映状态n时的将牌排列次序的计分值 S(n)的计分值的计算： 1）对于非中心格中的数码，如果其后（顺时针）紧跟的数码和目标状态相应将牌的顺序相比不一致，则令Si(n)=2，否则Si(n)=0。 2）若中心格无将牌，则令Si(n)=0，否则令Si(n)=1。 3）S(n)为全部Si(n)之和，即S(n)= ΣSi(n)。 为每一个将牌与其目标位置之间的距离和 评价函数的启发能力（2） 2 1 6 4 8 7 5 3 2 1 6 4 8 7 5 3 g(n)=1, h(n)=p(n)+3S(n) 1 2 3 4 5 8 7 7 6 评价函数的启发能力（2） 2 1 6 4 8 7 5 3 2 6 4 1 8 7 5 3 g(n)=1, h(n)=p(n)+ 3S(n) 1 2 3 4 5 8 7 7 6 定义新的启发函数(1) 定义启发函数h(n)= p(n