人工智能状态空间搜索策略56

第五章状态空间搜索策略第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*算法需要重点掌握的问题用宽度优先搜索和深度优先搜索求解八数码问题；用代价树的宽度优先搜索和深度优先搜索求解推销员旅行问题；用全局最佳优先搜索八数码问题。状态空间搜索策略搜索是人工智能的基本问题，是推理不可分割的一部分问题求解就是搜索过程搜索对应的知识表示法：状态空间表示法、与/或树表示法（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:=ADD(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):=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)=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