《搜索问题教学》ppt课件

《《搜索问题教学》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章搜索问题内容：状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。1搜索问题（续1）S0Sg2搜索问题（续2）讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。31.1回溯策略例：皇后问题4()5()Q((1,1))6()QQ((1,1))((1,1)(2,3))7()Q((1,1))((1,1)(2,3))8()QQ((1,1))((1,1)(2,3))((1,1)(2

2、,4))9()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))11()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()((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))

3、((1,1)(2,4)(3.2))Q((1,2))14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))15()((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))16()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((

4、1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))17递归的思想从前有座山……从前有座山……从前有座山……18递归的思想（续）当前状态目标状态g19一个递归的例子intListLenght(LIST*pList){if(pList==NULL)return0;elsereturnListLength(pList->next)+1;}NULLpLIST12320回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态

5、的路径（以规则表的形式表示）或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,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAIL

6、GOLOOP;10,RETURNCONS(R,PATH);22存在问题及解决办法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态问题：深度问题死循环问题23回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。24回溯搜索算法11,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTER

7、M(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)>BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);25回溯搜索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH

8、:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);26一些深入的问题失败原因分析、多步回溯QQ27一些深入问题（续）回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ3223281.2图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。29一些基本概念节点深度：根节点深度=0其它节点深度=父节点深度