人工智能搜索问题10233613.pptx

第一章 搜索问题 内容：状态空间的搜索问题。搜索方式：盲目搜索 启发式搜索 关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。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,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)(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(1,2)(2,4)Q(1,2)(2,4)(3,1)Q(1,2)(2,4)(3,1)(4,3)17递归的思想从前有座山 从前有座山 从前有座山18递归的思想（续）当前状态目标状态g19一个递归的例子int ListLenght(LIST*pList)if(pList=NULL)return 0;else return ListLength(pList-next)+1;NULLpLIST1 2320回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。21回溯搜索算法递归过程BACKTRACK(DATA)1,IF TERM(DATA)RETURN NIL;2,IF DEADEND(DATA)RETURN FAIL;3,RULES:=APPRULES(DATA);4,LOOP:IF NULL(RULES)RETURN FAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);22存在问题及解决办法 解决办法：对搜索深度加以限制 记录从初始状态到当前状态的路径当前状态l 问题：深度问题 死循环问题23回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。24