《人工智能状态空间搜索策略56》由会员分享，可在线阅读，更多相关《人工智能状态空间搜索策略56（56页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 状态空间搜索策略状态空间搜索策略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 最佳
2、优先搜索最佳优先搜索5.3.3 A*算法算法 2需要重点掌握的问题需要重点掌握的问题n用用宽度优先搜索宽度优先搜索和和深度优先搜索深度优先搜索求解求解八数八数码问题码问题；n用用代价树的宽度优先搜索代价树的宽度优先搜索和和深度优先搜索深度优先搜索求解推销员旅行问题；求解推销员旅行问题；n用全局最佳优先搜索用全局最佳优先搜索八数码问题八数码问题。3状态空间搜索策略状态空间搜索策略n搜索是人工智能的基本问题，是推理不可搜索是人工智能的基本问题，是推理不可分割的一部分分割的一部分n问题求解就是搜索过程问题求解就是搜索过程n搜索对应的知识表示法搜索对应的知识表示法：n状态空间表示法、与/或树表示法45
3、67891011 （6）对节点对节点n进行扩展，将它的所有后继节点放入进行扩展，将它的所有后继节点放入OPEN表的末端，表的末端，并为这些后继节点设置指向父节点并为这些后继节点设置指向父节点n的指针，然后转步骤（的指针，然后转步骤（2）12宽度优先搜索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(
4、n) mi, G:=ADD(mi, G);7, ADD(OPEN, mj), 并标记mj到n的指针;8, GO LOOP;131415161718深度优先搜索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的
5、指针;8, GO LOOP;1920212223242526272829303132333435363738394041424344454647A算法1, OPEN:=(s), 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 L
6、OOP； 48495051一个A算法的例子定义评价函数：f(n) = g(n) + h(n)g(n)为从初始节点到当前节点的代价值h(n)为当前节点“不在位”的位置数 2 8 31 6 47 51 2 38 47 6 552h计算举例h(n) =4 2 8 31 6 47 51 2 3457 6 8532 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)目标12345654A*条件举例n8数码问题nh1(n) = “不在位”的将牌数nh2(n) = 将牌“不在位”的距离和2 8 31 6 47 51 2 3457 6 8将牌1：1将牌2：1将牌6：1将牌8：25556
