AI第三章 搜索策略ppt课件.ppt

《AI第三章 搜索策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章搜索策略3.1基本概念3.2状态空间的搜索策略状态空间的一般搜索过程广度、深度、有界深度优先搜索代价树的广度、深度优先搜索启发式搜索A*算法3.3与/或树的搜索策略一般搜索过程广度、深度优先搜索有序搜索博弈树的启发式搜索剪枝技术0什么是问题？283710514115964111412123487659101112151413?3.1基本概念1问题：就是在给定信息和目标状态之间有某些障碍需要加以克服的情境。问题情境：①给定：有关问题条件的描述，即问题的起始状态；②目标：有关构成问题结论的描述，即问题

2、的目标状态；③障碍：无法直接到达目标，必须通过一定的思维活动才能找到答案，达到目标状态。问题解决：就是运用已有的知识去成功地寻找达到目标的手段或途径的过程。按解决问题所需的领域特有知识的多寡，问题求解系统可以划分为两大类：①知识贫乏系统：依靠搜索技术去解决问题。②知识丰富系统：依靠推理技术解决问题。21.搜索:人工智能所研究的对象大多是属于结构不良或非结构化的问题。对于这些问题，一般很难获得其全部信息，更没有现成的算法可供求解使用。因此，只能依靠经验，利用已有知识逐步摸索求解。像这种根据问题的实际情况，

3、不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程，称为搜索。对那些结构性能较好，理论上有算法可依的问题，如果问题或算法的复杂性较高（如按指数形式增长），由于受计算机在时间和空间上的限制，有时也需要通过搜索来求解。一、什么是搜索32.搜索的分类：①根据搜索过程是否使用启发式信息盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，因此这种搜索具有盲目性。启发式搜索：搜索过程中加入与问题有关的启发性

4、信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。②根据问题的表示方式状态空间搜索：基于状态空间表示求解问题所进行的搜索。与／或树搜索：基于与／或树表示利用问题归约法来求解问题时所进行的搜索。4二、问题状态空间的表示状态空间表示：状态操作状态空间1.什么是状态？状态（State）是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk＝｛Sk0，Sk1，…｝在这种表示方式中，当对每一个分量都给予确定的值时，就得到了一个具体的状态。任何一种类型的数据结构都可以用来描述状

5、态，只要它有利于问题求解，就可以选用。52.什么是操作？操作（Operator）也称为算符，它是把问题从一种状态变换为另一种状态的手段。当对一个问题状态使用某个可用操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。State1State2Operator63.什么是状态空间？状态空间（Statespace）用来描述一个问题的全部状态以及这些状态之间的相互关系

6、。状态空间常用一个三元组表示：（S，F，G）S：为问题的所有初始状态的集合；F：为操作的集合；G：为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。InitialStateMediumState1MediumState2TargetState74.如何求解问题？①选择合适的问题“状态”描述方法；②定义合理的“操作”；③从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止；注意：由初始状态到目

7、标状态所使用的算符序列就是该问题的一个解。上述问题求解过程实际上是一个搜索过程（每一步搜索合适的操作）。8设有三根钢针，它们的编号分别是1号、2号和3号;在初始情况下，l号钢针上穿有A、B两个金片;A比B小，A位于B的上面;要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。如何将A、B两个金片移到2号或3号钢针上面？BA123BA123123BA【例3.1】二阶Hanoi问题9解:①状态：Sk=｛Sk0，Sk1｝Sk0表示金片A所在的钢针号；Sk1表

8、示金片B所在的钢针号。②全部可能的问题状态共有以下9种：S0=(1,l)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)③目标：G＝{S4,S8}BA123S0=(1,1)123BAS8=(3,3)BAS4=(2,2)12310④操作：A(i,j)表示把金片A从第i号钢针移到j号钢针上；B(i,j)表示把金片B从第i号钢针移到j号钢针上；所有的操作共有12种