人工智能第一章搜索问题ppt课件.ppt

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

1、第一章搜索问题内容：状态空间的搜索问题。搜索：根据问题的实际情况，不断寻找可利用的知识，从而构造一条代价最小的推理路线，使问题得以解决的过程。1S0Sg解路径搜索空间问题全状态空间第一章搜索问题2第一章搜索问题按搜索方式分：盲目搜索：按预定的控制策略进行搜索，在搜索的过程中获得的中间信息并不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解。3第一章搜索问题按问题的表示方式分：状态空间搜索：按状态空间法来求解问题所进行的搜索。与/或树搜索：用问题归约法来求解问题时所进行的搜索。状态空间法和问题归约法是人工智能中最

2、基本的两种问题求解方法。状态空间表示法和与/或表示法是人工智能中最基本的两种问题表示方法。4第一章搜索问题关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。5讨论的问题：有哪些常用的搜索算法？问题有解时能否找到解？找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何？第一章搜索问题6搜索问题回溯策略图的搜索策略盲目搜索启发式搜索与或树搜索博弈树搜索消解原理7解决实际问题的两个关键之处：①问题的表达状态空间法问题归约法谓词逻辑法②问题的求解搜索技术推理技术8盲目与启发式搜索：状态空间法、图的搜索技术与或树搜索：问题归约法、与或图的特例的搜索技术博弈树搜索：状态空间法＋问题归约法

3、、双人博弈的特殊搜索技术消解原理：谓词逻辑法、推理技术91.1回溯策略回溯策略：属于盲目搜索的一种。首先将规则给出一个固定的排序，在搜索时，对当前状态依次检测每一条规则，在当前状态未使用过的规则中找到第一条可用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。101.1回溯策略例：皇后问题11()12()Q((1,1))13()QQ((1,1))((1,1)(2,3))14()Q((1,1))((

4、1,1)(2,3))15()QQ((1,1))((1,1)(2,3))((1,1)(2,4))16()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))17()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))18()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))19()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))20()((1,1))((1,1)(2,3))((1,1)(2,4))((1,

5、1)(2,4)(3.2))Q((1,2))21()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))22()((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))23()((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))2

6、4递归的思想从前有座山……从前有座山……从前有座山……25一个递归的例子intListLenght(LIST*pList){if(pList==NULL)return0;elsereturnListLength(pList->next)+1;}NULLpLIST12326回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。功能：如果从当前状态DATA到目标状态有路径存在，则返回以规则序列表示的从DATA到目标状态的路径；如果从当前状态DATA到目标状态没有路径存在，则返回FAIL。设置两个回溯点：当遇到非法状态时回溯

7、；当试探了一个状态的所有子状态后，仍然找不到解时回溯。27回溯搜索算法递归过程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);