资源描述：
《人工智能之搜索培训讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、人工智能导论 第二章：搜索、问题求解与博弈第二章搜索、问题求解与博弈问题求解能力是人类智能的基本组成部分，研究并实现问题求解是人工智能的重要研究内容之一。知识（问题）的表示是问题求解的基础，两种普遍采用的问题表示方法：状态空间表示与或图表示搜索（优化）：在问题表示基础上，在合理的时间范围内，从问题所有可能的解中找到一个最优解或可行解，是问题求解中的核心技术。启发式搜索----人工智能的本质特征之一。计算机博弈涉及问题表示、搜索技术等AI核心问题，现有的计算机博弈本质上是将博弈问题转变为一个与或图搜索问题进行处理。主要内容2.1搜索概述2.2问题求解2.2
2、.1状态空间2.2.2与或图2.3搜索技术图搜索2.4机器博弈一些例子搭积木智力游戏：有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到右岸，但受下列条件限制：船太小，农夫每次只能带一样东西过河没有农夫看管，则狼要吃羊，羊要吃菜请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。类似问题：野人和传教士问题下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）2.1搜索概述人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个“问题求解”过程问题求解过程实际上就是一个搜索过程最优性和计算法复杂性是搜索中的一对矛盾，搜索必须考虑的三个问题：采用盲
3、目搜索还是启发式搜索盲目搜索：不考虑问题本身的特性，通过遍历问题解的集合来寻找可行解或最优解。启发式搜索：利用与问题有关的启发式信息来确定搜索方向，以加快搜索过程。进行局部搜索还是全集搜索搜索可行解还是最优解2.1搜索概述评价一个搜索算法的因素：完备性：如果问题有解，一定能找到一个解最优性：如果问题存在最优解，则一定能找到这个最优解复杂性：时间和空间复杂性，在保证最优性和完备性的前提下，算法的复杂性越小越好。目前的搜索算法还不能同时满足以上三个要求。为了进行搜索，首先必须用某种形式把问题表示出来：状态空间表示法和与或图表示法就是用来表示问题及其搜索过程的两
4、种常用方法。2.2问题求解状态空间表示法和与或图表示法不仅是问题表示的方法，也分别代表了两种问题求解的思路状态空间将问题求解所涉及的每个可能的步骤表示成一个状态，全部状态以及状态之间的所有转换构成一个以图的形式表示的状态空间。问题的求解过程是在状态空间中搜索一条最优的或可行的从初始状态到目标状态的路径的过程。与或图表示法的基础是问题归约，通过一系列分解或变换，将复杂问题逐步转化为比较简单的问题，直至可以直接求解的本原问题。与或图的求解过程是在与或图中搜索一个将原始问题变换为简单问题在变换为本原问题的、最优的或可行的归约步骤的过程。2.2.1状态空间表示法状
5、态空间表示法是用“状态”和“算子”来表示问题的一种方法状态：用来描述问题求解过程中不同时刻的状况算子：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解2.2.1状态空间表示法状态状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK(SK0,SK1,…)当给每一分量以确定的值时，就得到一个具体的状态算子引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子状态空间由问题的全部状态
6、及一切可用算符所构成的集合称为问题的状态空间，一般用三元组表示:(S,F,C,I,G)S:所有状态构成的集合F:用于状态转换的算子的集合C:状态转换代价的聚合I:初始状态的集合G:目标状态的集合例:二阶HanoiTower（梵塔）问题设有三根柱子，在1号柱于上穿有A、B两个盘片，盘A小于盘B，盘A位于盘B的上面。要求把这两个盘片全部移到另一根柱子上，而且规定每次只能移动一片，任何时刻都不能使盘B位于盘A的上面。设SK=(SK0,SK1)表示问题的状态，SK0表示盘片A所在的柱号，SK1表示盘片B所在的柱号全部可能的状态:S0=(1,1),S1=(1,2),
7、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移到柱j；B(i,j):盘片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)例:二阶HanoiTower（梵塔）问题9种状态，12种算子构成的状态空间转移图：2
8、.2.1状态空间表示法总结：用状态空间方法表示问题时，首先必须定义
