人工智能原理第4章知识表示(阅读)ppt课件.ppt

《人工智能原理第4章知识表示(阅读)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能原理第2章搜索技术（上）1本章内容2.1搜索与问题求解2.2无信息搜索策略2.3启发式搜索策略2.4局部搜索算法2.5约束满足问题2.6博弈搜索参考书目附录A*算法可采纳性的证明第2章搜索技术22.1搜索与问题求解2.1.1问题与问题的解2.1.2问题实例2.1.3搜索策略第2章搜索技术3搜索与问题求解问题求解过程是搜索答案(目标)的过程/所以问题求解技术也叫搜索技术—通过对状态空间的搜索而求解问题的技术问题求解智能体是一种基于目标的智能体在寻找到达目标的过程中，当智能体面对多个未知的选项时，首先检验各个不同的导致已知评价的状态的可能行动序

2、列，然后选择最佳序列—这个过程就是搜索第2章搜索技术42.1.1问题与问题的解问题可以形式化地定义为4个组成部分智能体的初始状态(即搜索的开始)后继函数—智能体采取的可能行动的描述，通常为<行动，后继状态>/初始状态和后继函数隐含地定义了问题的状态空间/状态空间中的一条路径是通过行动序列连接起来的一个状态序列目标测试—检查给定的状态是不是目标路径耗散函数—每条路径都有一个数值化的耗散值，反映了性能度量/求解问题的代价第2章搜索技术5问题的解问题的解就是初始状态到目标状态的路径解的优劣由路径耗散函数量度(代价)最优解就是路径耗散函数值最小的路径上述解题过

3、程把解决一个问题的过程描述出来，称之为解题知识的过程性表示过程性知识与陈述性知识相对搜索过程解题的特点—没有直接的方法(公式)可以求解，而是一步一步的探索第2章搜索技术6状态空间数据基：代表了所要解决的问题，有初始状态，可能有目标状态也可能没有状态空间：在解题过程中的每一时刻，数据基都处于一定的状态，数据基所有可能状态的集合称为状态空间有向图：若把每个状态看成一个节点，则整个状态空间是一个有向图/该图不一定全连通，即从某些状态不一定能到达另外一些状态第2章搜索技术7问题的可解性可解的：在每个连通部分，每个弧代表一个运算符，将状态改变/如果从代表初始状态

4、的节点出发，有一条路径通向目标状态，则称此目标状态所代表的问题在当前初始状态下是可解的搜索空间：在解题过程中达到过的所有状态的集合，称为搜索空间不同于状态空间，搜索空间只是其中一部分状态空间和搜索空间都属于过程性知识表示第2章搜索技术82.1.2问题实例玩具问题八数码游戏(九宫图)河内塔八皇后问题真空吸尘器世界现实问题旅行商问题超大规模集成电路的布局自动装配排序/蛋白质设计互联网搜索第2章搜索技术9八数码游戏八数码游戏：1-8数字(棋子)/9个方格(棋盘格)/1个空格可用如下形式的规则来表示数字通过空格进行移动：

5、7,a8,a9>→共24条规则=4角*2+4边*3+1中间*4搜索顺序举例：(1)优先移动行数小的棋子(数字)(2)同一行中优先移动列数大的棋子约束规则：不使离开既定位置的数字数增加第2章搜索技术10八数码游戏的搜索树第2章搜索技术既定位置=终态11八数码问题形式化初始状态初始状态向量—规定向量中各分量对应的位置，各位置上的初始数字后继函数移动规则—按照某条规则移动数字，将得到的新向量目标测试新向量是否是目标状态(也是向量形式)路径耗散函数每次移动代价为1第2章搜索技术12河内塔(1)河内塔问题：

6、n个大小不等的圆盘从一个柱子移到另一个柱子，共有3个柱子(n阶河内塔问题)约束：从第1根柱子移动到第3根柱子上去，利用第2根柱子/每次移动1个盘子，且移动过程必须是小盘落大盘描述：设每个状态为(a1,a2,a3,…,an),ai=1,2,3—表示第i个盘子在第1/2/3根柱子上第2章搜索技术13河内塔(2)递归定义：{(a1,a2,a3,…,an)}为n阶河内塔的状态集合，则{(a1,a2,a3,…,an,1),(a1,a2,a3,…,an,2),(a1,a2,a3,…,an,3)}是n+1阶河内塔的状态集合1阶河内塔有3个状态，2阶河内塔有9个状态，

7、n阶河内塔有3n个状态，给出1/2/3阶河内塔的状态图第2章搜索技术14河内塔问题图解第2章搜索技术15河内塔问题形式化初始状态初始状态向量—规定向量中各分量对应所有n个盘子，位置上数字代表3个柱子之一后继函数移动规则—依据约束条件给出的各状态的后继状态目标测试新向量是否是目标状态(也是向量形式)路径耗散函数每移动一个盘子的代价为1第2章搜索技术16河内塔问题求解求最短路径问题：状态图中从三角形1个顶点走到另一个顶点结论：(1)如果初始状态或目标状态在三角形顶点上，则最短路径唯一；(2)对于任意2个状态，最短求解路径至多为2条。(中国某大学研究生证明)

8、求解过程—对状态空间的搜索—以2阶河内塔为例第2章搜索技术17河内塔问题的搜索树第2章搜索技术