下载此文档

知识的状态空间表示法.docx


文档分类:行业资料 | 页数:约40页 举报非法文档有奖
1/40
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/40 下载此文档
文档列表 文档介绍
第二章知识的状态空间表示法1课前思考:人类的思维过程,可以看作是一个搜索的过程。某个方案所用的步骤是否最少也就是说它是最优的吗如果不是, 如何才能找到最优的方案在计算机上又如何实现这样的搜索这些问题实际上就是本章我们要介绍的搜索问题。2学****目标:掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法,对典型问题,掌握启发式函数的定义方法。3学****指南:了解算法的每一个过程和细节问题, 掌握一些重要的定理和结论, 在有条件的情况下,程序实现每一个算法,求解一些典型的问题。4难重点:回溯搜索算法、 算法及其性质、改进的A*算法。本章所要的讨论的问题如下:有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗什么情况下可以找到最佳解求解的效率如何。状态空间表示知识一、状态空间表示知识要点1状态状态(State)用于描述叙述性知识的一组变量或数组,也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成:Q={q1,q2,……,qn}当给每一个分量以确定的值时, 就得到一个具体的状态,每一个状态都是一个结点(节点)。实际上任何一种类型的数据结构都可以用来描述状态, 只要它有利于问题求解,就可以选用。2•操作(规则或算符)操作(Operator)是把问题从一种状态变成为另一种状态的手段。 当对一个问题状态使用某个可用操作时,它将引起该状态中某一些分量发生变化, 从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数,它描述了状态之间的关系。通常可表示为:F={fl,f2, fm}状态空间状态空间(StateSpace)是由问题的全部及一切可用算符(操作)所构成的集合称为问题的状态空间。用三元组表示为:({Qs},{F},{Qg})Qs:初始状态,Qg:目标状态,F:操作(或规则)。状态空间(转换)图状态空间也可以用一个赋值的有向图来表示, 该有向图称为状态空间图, 在状态空间图中包含了操作和状态之间的转换关系,节点表示问题的状态,有向边表示操作。、状态图搜索搜索方式用计算机来实现状态图的搜索,有两种最基本的方式:树式搜索和线式搜索。搜索策略大体可分为盲目搜索和启发式(heuristic)搜索两大类。搜索空间示意图例钱币翻转问题设有三枚硬币,其初始状态为(反,正,反) ,允许每次翻转一个硬币(只翻一个硬币,必须翻一个硬币)。必须连翻三次。问是否可以达到目标状态(正,正,正)或(反,反,反)问题求解过程如下:用数组表示的话,显然每一硬币需占一维空间,则用三维数组状态变量表示这个知识:Q=(q1,q2,q3)取q=0表示钱币的正面 q=1 表示钱币的反面构成的问题状态空间显然为:Q0=(0,0,0),Q仁(0,0,1),Q2=(0,1,0),Q3=(0,1,1)Q4=(1,0,0),Q5=(1,0,1),Q6=(1,1,0),Q7=(1,1,1)引入操作:f1:把q1翻一面。f2:把q2翻一面。f3:把q3翻一面。显然:F={f1,f2,f3}目标状态:(找到的答案) Qg=(0,0,0)或(1,1,1)例分油问题。有两只空油瓶,容量分别为8斤和6斤,另有一个大油桶,里面有足够的油。我们可以任意从油桶中取出油灌满某一油瓶,也可以把某瓶中的油全部倒回油桶,两个油瓶之间可以互相灌。问如何在8斤油瓶中精确的得到4斤油。问题的求解显然用2维数组或状态空间描述比较合适,第一位表示8斤油瓶油量,第二位表示6斤油瓶油量,构成整数序列偶(E,S)E:=0,1,2,3,4,5,6,7,8。表示8斤油瓶中含有的油量。S:=0,1,2,3,4,5,6。表示6斤油瓶中含有的油量。总结出如下分油操作规则:f1: 8斤油瓶不满时装满(E,S)且E<8 ( 8,S)f2: 6斤油瓶不满时装满(E,S)且S<6 ( E,6)f3: 8斤油瓶不空时倒空(E,S)且E>0 ( 0,S)f4: 6斤油瓶不空时倒空(E,S)且S>0 ( E,0)f5:8斤油瓶内油全部装入6斤油瓶内(E,S)E>0且E+S<6 (0,E+S)f6:6斤油瓶内油全部装入8斤油瓶内(E,S)S>0且E+S<8 (E+S0)f7:用6斤油瓶内油去灌满8斤油瓶(E,S)且E<8且E+S>8 (8,E+S-8)f8:用8斤油瓶内油去灌满6斤油瓶(E,S)且S<6且E+S>6 (E+S-6,6)搜索问题讨论(1)求任一解路的搜索策略回溯法(Backtracking)爬山法(HillClimbing )宽度优先法(Breadth-first)深度优先法(Depth-first)限定范围搜索法(BeamSearch)好的优先法(Best-first)(2)求最佳解路的搜索策略大英博物馆法(BritishMuseum)分枝

知识的状态空间表示法 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数40
  • 收藏数0 收藏
  • 顶次数0
  • 上传人guoxiachuanyue
  • 文件大小816 KB
  • 时间2020-09-27