[精选]佛山市合诚汽车销售服务有限公司Crea。。。.pptx

《[精选]佛山市合诚汽车销售服务有限公司Crea。。。.pptx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、问题求解与博弈主要内容状态空间搜索技术机器博弈一些例子搭积木智力游戏：有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到右岸，但受下列条件限制：船太小，农夫每次只能带一样东西过河没有农夫看管，则狼要吃羊，羊要吃菜请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）状态空间表示法人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个“问题求解”过程问题求解过程实际上就是一个搜索过程为了进行搜索，首先必须用某种形式把问题表示出来状态空间表示法就是用来表示问题及其搜索过程的一种方法状态空间表示法状态空间表

2、示法是用“状态”和“算子”来表示问题的一种方法状态：用来描述问题求解过程中不同时刻的状况算子：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解状态空间表示法状态状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示SK(SK0,SK1,…)当给每一分量以确定的值时，就得到一个具体的状态算子引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子状态空间由问题的全部状态及一切可用算符所构成的集合称为

3、问题的状态空间，一般用三元组表示:(S,F,G)S:所有初始状态构成的集合F:算子的集合G:目标状态的集合例子:HanoiTower二阶hanoitowerSK=(SK0,SK1)表示问题的状态，SK0表示盘片A所在的柱号，SK1表示盘片B所在的柱号全部可能的状态:S0=(1,1),S1=(1,2),S2=(1,3),S3=(2,1),S4=(2,2),S5=(2,3),S6=(3,1),S7=(3,2),S8=(3,3).问题的初始状态集合S={S0},目标集合为G={S4,S8}算子分别用A(i,j),B(i,j)表示A(i,j):盘片A从柱i移到柱jB(i,j

4、):盘片B从柱i移到柱j全部可能的算子：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2),B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)状态空间表示法首先必须定义状态的描述形式，通过使用这种描述可把问题的一切状态都表示出来。其实还要定义一组算子，通过使用算子可把问题由一种状态转变为另一种状态问题的求解过程就是一个不断把算子作用于状态的过程算子的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算子序列都可使问题从初始状态变到目标状态，这就得到了多个解，我们把使用算子最少的解称为最优解对于任何

5、一种状态，可使用的算子可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算子生成更进一步状态时，首先应对哪一状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的。搜索技术搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。例如，A.Newell(艾伦·纽厄尔)和H·A·Simon(西蒙)等人编写的LT(LogicTheorist)程序,J.Slagle写的符号积分程序SAINT,A·Newell和H·A·Simon写

6、的GPS(GeneralProblemSolver)程序,H·Gelernter(格伦特尔)写的Geometrytheorem-provingmachine程序,R.Fikes(菲克斯)和N.Nilsson(尼尔逊)写的STRIPS(StanfordResearchInstituteProblemSolver)程序以及A.Samuel(塞缪尔)写的Chechers程序等,都使用了各种搜索技术。现在,搜索技术渗透在各种人工智能系统中,可以说没有哪一种人工智能的应用不用搜索方法,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈都广泛使用搜技术。

7、搜索技术搜索问题是AI核心理论问题之一一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：(1)搜索空间小;(2)解最佳。搜索技术搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。当所给定的问题用状态空间表示时,则求解过程可归结为对状态空间的搜索。当问题有解时,使用不同的搜索策略,找到解的搜索空间范围是有区别的。一般来说,对大空间问题,搜索策略是要解决组合爆炸的问题搜索策略通常搜索策略的主要任务是确定如何选取规