人工智能实验报告_5.docx

《人工智能实验报告_5.docx》由会员分享，可在线阅读，更多相关《人工智能实验报告_5.docx（22页珍藏版）》请在第一文库网上搜索。

1、实验一搜索策略一实验内容1 .熟悉和掌握启发式搜索的定义、估价函数和算法过程；比较不同算法的性能。2 .修改八数码问题或路径规划问题的源程序，改变其启发函数定义，观察结果的变化，分析原因。二实验目的熟悉和掌握各种搜索策略的思想，掌握A*算法的定义、估价函数和算法过程,理解求解流程和搜索顺序。1、不同算法的搜索路径对比6000003ei4697j9893H12.8节点318.0早点116200000762939453/1节点2128999996153O273/92117节点412.899999618530273节点59.399999618530273节点680000019073486314.0/

2、12。盛盟9394以点83.5/14.0/13.81551Y卡13.9节点1。/6400000095367432算法比较宽度优先深度优先估价函数无无0PEN表C10SED表S1,22,3,43,4,5,6)(4,5,6,7)(5,6,7,8)(6,7,8,9,G)7,8,9,GJO)8,9,G,109,G,10G,10SS,1)S,1,2S,1,2,3)S,1,2,3,4)S,1,2,3,4,5)S,1,2,3,4,5,6)S,1,2,3,4,5,6,7)S,1,2,3,4,5,6,7,8)S,1,2,3,4,5,6,7,8,9)S)1,23,4,21亿4,214,28,2(2(5,6)9,G

3、,61(6,6)S(S,1)(S,1,3)S,1,3,7)S,1,3,7,4)S,1,3,7,4,8)S,1,3,7,4,8,2S,1,3,7,4,8,2,5S,1,3,7,4,8,2,5,9)搜索节点次序记录S-1-2-3-4-5-6-7-8-9-GS-1-3-7-4-8-2-5-6-9-G观测结果S-2-5-GS-2-5-G结论CompIete,optimaIIncompIete,notoptimaI始节由600000381469729.89.3X_128节点318.0节点116200000762939453/节点228999996185302737/2117X书点412999996185

4、30273节点59399999618530273节？568.80000019073486314.0/14013.8155/1.音13.9|2。2。盛盟9394以1点83.5令点91节笠6.5I.0.0/节点10“6400000095367432算法比较最低代价优先最佳优先(Breath)估价函数g(n)open表按g(n)由小到大排序h(n)open表按f(n)由小到大排序0PEN表C10SED表S2,111,5,6)(4,5,6,3)15,6,3,8)(6,3,8,9,G)(3,8,9,GJO)8,9,G,10,7)9,G,10,71G,10,7SS,2S,2,1)S,2,1,4)S,2,1

5、,4,5)S,2,1,4,5,6)S,2,1,4,5,6,3)S,2,1,4,5,6,3,8)S,2,1,4,5,6,3,8,9)S1(6,5,1)10,5,1)5,1G,9,1)Ss,2S,2,6)(S,2,6,10)S,2,6,10,5)搜索节点次序记录S2-1-4-5-6-3-8-9-GS-2-6-10-5-G观测结果S-2-5-GS-2-5-G结论CompIete,optimaIIncomp1ete,notoptimaI节点72020000076293945312,999996185302739.399999618530273节点4节点96.5节点5节点6S80000019073486

6、3算法比较启发式深度优先A*估价函数h(n)f(n)=g(n)+h(n)0PEN表C10SED表S16,5,1)10,5,15,1G,9,1)(S)S,2)S,2,6)S,2,6,10)S,2,6,10,5)S2,11,5,6)(5,6,4,3)6,4,G,9,318,225,69,G,6G,6)Ss,2(S,2,1)(S,2,1,5)(S,2,1,5,6)(S,2,1,5,6,4(S,2,1,5,6,4,G)搜索节点次序记录S-2-6-10-5-GS-1-3-7-4-8-2-5-6-9-G观测结果S-2-5-GS-2-5-G结论Comp1ete,optimaIIncompIete,notop

7、timaI节点1。0400000095367432算法分析：相比于无信息的盲目搜索，有启发式信息的搜索往往效率更高，其中A*算法由于启发式函数满足可纳性和一致性，而可以找到最优解也因而是完备的。贪心算法每次都扩展当前代价最小的结点，容易陷入局部最优，而忽略了全局特性，经常陷入困局。因此，在设计搜索算法时，应优先考虑寻找最佳启发式函数，以此作为指导，可大大提高程序执行的效率。2、伪代码*bfsDFS*functionBREADTH-FIRST-SEARCH(probIem)returnsaso1ution,orfaiIurenode-anodewithSTATE=prob1em.INITIA1-

8、STATE,PATH-COST=0ifprob1em.GOA1-TEST(node.STATE)thenreturnSO1UTION(node)frontier-aFIFOqueuewithnodeastheon1yeIementexp1oredanemptyset1oopdoifEMPTY?(frontier)thenreturnfaiIurenode-P0P(frontier)*choosesthesha11owestnodeinfrontier*/addnode.STATEtoexp1oredforeachactioninprobIem.ACTIONS(node.STATE)dochi1

9、dCHI1D-NODE(PrOb1em,node,action)ifchi1d.STATEisnotinexp1oredorfrontierthenifprobIem.GOA1-TEST(chiId.STATE)thenreturnSO1UTION(chiId)frontierINSERT(Chi1d,frontier)functionUNIFORM-COST-SEARCH(probIem)returnsaso1ution,orfai1urenodeanodewithSTATE=prob1em.INITIA1-STATE,PATH-COST=0frontierapriorityqueueord

10、eredbyPATH-COST,withnodeastheonIyeIementexp1oredanemptyset1oopdoifEMPTY?(frontier)thenreturnfai1urenodePOP(frontier)*choosesthe1owest-costnodeinfrontier*/ifprobIem.GOA1-TEST(node.STATE)thenreturnSO1UTION(node)addnode.STATEtoexp1oredforeachactioninprobIem.ACTIONS(node.STATE)dochi1d-CHI1D-NODE(probIem

11、,node,action)ifchi1d.STATEisnotinexp1oredorfrontierthenfrontier4-1NSERT(chiId,frontier)e1seifchi1d.STATEisinfrontierwithhigherPATH-COSTthenrep1acethatfrontiernodewithchi1dfuncionDEPTH-1IMITED-SEARCH(probIem,Iimit)returnsaso1ution,orfai1ure/cutoffreturnRECURSIVE-D1S(MAKE-NODE(probIem.INITIA1-STATE),p

12、rob1em,Iimit)functionRECURSIVE-D1S(node,prob1em,Iimit)returnsaso1ution,orfaiIure/cutoffifprob1em.GOA1-TEST(node.STATE)thenreturnSO1UTION(node)e1seifIimit=0thenreturncutoffe1secutoffoccurred?4-faIseforeachactioninprobIem.ACTIONS(node.STATE)dochi1dCHI1D-NODE(probIem,node,action)resu1tRECURSIVE-D1S(Chi

13、1d,prob1em,Iimit-1)ifresu1t=cutoffthencutoffOCCUrred?truee1seifresu1t_=fai1urethenreturnresu1tifcutoffoccurred?thenreturncutoffe1sereturnfai1ureresu1t,best.f-RBFS(prob1em,best,min(fIimit,a1ternative)ifresu1t=fai1urethenreturnresu1t3、修改启发式函数在A*算法寻找最短路径时，分别以欧几里得和曼哈顿距离为启发式函数，得到结果如下：intH=10*sqrt(x-targetX)*(x-targetX)+(y-targetY)*(y-targetY);intH=10*(abs(x-targetX)+abs(y-targetY);此图来说两种启发式生成的状态空间完全相同。-H=:?:=1:=-=:=A(使用欧氏距离)启发式在满足h(n)=h*(n)和h(n)=c(n,a,n,)+h(n,)时，可以保证最优性。启发式不同，搜索效率也不一样。越接近实际代价的启发式，效率越高。从应用来说，欧氏距离较为广泛，因为它更接近于实际代价，而曼哈顿距离由于需要在网格上进行操作需要更多的代码支持，并且很可能要大于实际代价而不能保证找到解。实验二推理技术一实