搜索策略搜索是人工智能中的一个基本问题是推理课件.ppt

《搜索策略搜索是人工智能中的一个基本问题是推理课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章搜索策略搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的四个核心问题之一。5.1基本概念1.什么是搜索人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步摸索着前进。在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。如：在正向推理中，•对已知的初始事实，需要在知识库中寻找可使用的知识，这就

2、存在按何种线路进行寻找的问题。•另外，可能存在多条线路都可实现对问题的求解，这就又出现按哪一条线路进行求解以获得较高的运行效率的问题。像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。2.搜索分类搜索分为盲目搜索和启发式搜索。盲目搜索——按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索——在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问

3、题的求解过程并找到最优解。5.2求解问题的表示方法用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表示出来.一般来说，有两种方法：状态空间表示法；与/或树表示法；1.状态空间表示法状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最基本的形式化方法。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中，“状态”——用以描述问题求解过程中不同时刻的状况；“算符”——表示对状态的操作，算符的每一次使用就使问题由一种状态变换为另一种状态;解——当到达目标状态时，由初始状态到目标状

4、态所用算符的序列就是问题的一个解。Ⅰ.状态状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK＝(SK0,SK1,…)当给每一个分量以确定的值时，就得到了一个具体的状态。Ⅱ.算符引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。在产生式系统中，每一条产生式规则就是一个算符。Ⅲ.状态空间由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，—般用—个三元组表示：(S，F，G)其中,S是问题的所有初始状态构成的集合；F是算符的集合；G是目标状态的集合。

5、状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边(弧)表示算符。例1：钱币翻转问题，如图所示。设有三个钱币，起初是状态为（反正反），允许每次翻转一个钱币（只反一个，也必反一个），连反三次，问是否可达到目标状态？（正正正）或（反反反）？正反正正正反反反反设用Sk=(s1,s2,s3)表示问题的状态，s=0表示钱币正面，s=1表示钱币反面。则钱币可能出现的状态有八种：S0=(0,0,0),S1=(0,0,1),S2=(0,1,0),S3=(0,1,1)S4=(1,0,0),S5=(1,0,1),S6=(1

6、,1,0),S7=(1,1,1)问题的初始状态集合：S={S5}目标状态集合：G={S0,S7}算符：f1——把s1翻一面；f2——把s2翻一面；f3——把s3翻一面；上述问题的状态空间“三元组”为：（{S5},{f1,f2,f3},{s0,s7}）相应的状态空间图：000100001101111011110010S0S4S1S5S7S3S6S2从图中看出：从S5不可能经三次翻转到达S0,从S5可经三次翻转到达S7,且有七种操作方式。f1f1f1f1f2f2f2f2f3f3f3f32.与/或树表示法与/或树是用于

7、表示问题及其求解过程的又一种形式化方法，通常用于表示比较复杂问题的求解。对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化：(1)分解：“与”树把一个复杂问题分解为若干个较为简单的子问题，然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。这是“与”的问题。PP1P2P3P1,P2,P3为子节点，子问题对应子节点。P为“与”节点，只有当三个子问题都有解时，P才可解。如图所示，称为“与”树。(2)等价变换：“或”树利用等价变换，把它变换为若干个较容易求解的新问题。若新问题中

8、有一个可求解，则就得到了原问题的解。这是“或”的问题。如图所示，称为“或”树。PP1P2P3与/或树：将上述两种方法也可结合起来使用，此时的图称为“与/或树”，其中既有“与”节点，也有“或”节点。在此统称为子节点。P1P11P12P3P31P32P33PP2(3)几个基本概念：Ⅰ.本原问题不能再分解或变换，而且直接可解的子问题称为本原问题。Ⅱ.端节点与终止节点在与/或树中