人工智能状态空间搜索策略ppt课件

1、第五章 形状空间搜索战略第5章 形状空间搜索战略5.1 搜索的概念及种类5.1.1 搜索的概念5.1.2 搜索的种类5.2 盲目搜索战略5.2.1 形状空间图的搜索战略5.2.2 宽度优先搜索5.2.3 深度优先搜索5.2.4 有界深度优先搜索5.2.5 代价树的宽度优先搜索5.2.6 代价树的深度优先搜索5.3 启发式搜索战略5.3.1 启发信息与估价函数5.3.2 最正确优先搜索5.3.3 A*算法 需求重点掌握的问题用宽度优先搜索和深度优先搜索求解八数码问题；用代价树的宽度优先搜索和深度优先搜索求解推销员游览问题；用全局最正确优先搜索八数码问题。形状空间搜索战略搜索是人工智能的根本问题，

2、是推理不可分割的一部分问题求解就是搜索过程搜索对应的知识表示法：形状空间表示法、与/或树表示法 6对节点n进展扩展，将它的一切后继节点放入OPEN表的末端，并为这些后继节点设置指向父节点n的指针，然后转步骤2宽度优先搜索1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( );2, LOOP: IF OPEN=( ) THEN EXIT (FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT (SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, G:=ADD(mi

3、, G);7, ADD(OPEN, mj), 并标志mj到n的指针;8, GO LOOP;深度优先搜索1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( );2, LOOP: IF OPEN=( ) THEN EXIT (FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT (SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, G:=ADD(mi, G);7, ADD(mj, OPEN), 并标志mj到n的指针;8, GO LOOP;A算法1, OPEN:=(s

4、), f(s):=g(s)+h(s);2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, 计算f(n, mi):=g(n, mi)+h(mi);7, OPEN中的节点按f值从小到大排序；8, GO LOOP； 一个A算法的例子定义评价函数：f(n) = g(n) + h(n)g(n)为从初始节点到当前节点的代价值h(n)为当前节点“不在位的位置数2 8 31 6 47

5、51 2 38 47 6 5h计算举例h(n) =4 2 8 31 6 47 51 2 3457 6 82 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(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)目的123456A*条件举例8数码问题h1(n) = “不