资源描述：
《人工智能 第1章 搜索问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章搜索问题内容：状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。1问题的状态空间表示状态空间可用三元组（S,O,G）来描述。S：状态的集合，状态是某种事实的符号或数据O：操作算子，利用它将一个状态转化为另一状态G：S的非空子集，表示目标状态集S0：初始状态，也是S的非空子集状态空间的一个解是一个有限的操作算子，它使初始状态转化为目标状态：O1O2OKS0→S1→S2→…→G0其中为状态空间的一个解，解不一定是唯一的。状态空间可用有向图表示，其节点表示状态，节点间的弧
2、表示操作算子。传教士与野人问题的状态空间有向图2搜索问题（续1）S0Sg3搜索问题（续2）讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。41.1回溯策略例：皇后问题5()6()Q((1,1))7()QQ((1,1))((1,1)(2,3))8()Q((1,1))((1,1)(2,3))9()QQ((1,1))((1,1)(2,3))((1,1)(2,4))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.
3、2))11()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))15()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4
4、)(3.2))Q((1,2))Q((1,2)(2,4))16()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))17()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))18递归的思想从前有座山……从前有座山……从前有座山……19递归的思
5、想（续）当前状态目标状态g20回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。21回溯搜索算法递归过程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:=APPRULES(DATA);4,LOOP:IFNULL(RULES)RETURNFAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R
6、,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAILGOLOOP;10,RETURNCONS(R,PATH);四皇后问题22加快搜索速度回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ322323存在问题及解决办法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态问题：深度问题死循环问题24回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表
7、的形式表示）或FAIL。25回溯搜索算法11,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)>BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);26回溯搜索算法1（续）9,RULES
8、:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNC
