资源描述：
《人工智能状态空间搜索策略.ppt》由会员上传分享，免费在线阅读，更多相关内容在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.3A*算法需要重点掌握的问题用宽度优先搜索和深度优先搜索求解八数码问题；用代价树的宽度优先搜索和深度优先搜索求解推销员旅行问题；用全局最佳优先搜索八数码问题。状态空间搜索策略搜索是人工智能的基本问
2、题，是推理不可分割的一部分问题求解就是搜索过程搜索对应的知识表示法：状态空间表示法、与/或树表示法（6）对节点n进行扩展，将它的所有后继节点放入OPEN表的末端，并为这些后继节点设置指向父节点n的指针，然后转步骤（2）宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=A
3、DD(mi,G);7,ADD(OPEN,mj),并标记mj到n的指针;8,GOLOOP;深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,ADD(mj,OPEN),并标记mj到n的指针;8,GOLOOP;A算法1,OPEN:=(s),f(s):=
4、g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},计算f(n,mi):=g(n,mi)+h(mi);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；一个A算法的例子定义评价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的代价值h(n)为当前节点“不在位”的位置数2831647512384765h计算举例h(n
5、)=428316475123457682831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和2831647512345768将牌1：1将牌2：1将牌6：1将牌8：2第五章结束
6、谢谢您的使用
