第5章搜索策略 搜索是人工智能中的一个基本问题,并与推理密切相关, 搜索策略的优劣,将直接影响到智能系统的性能与推理效率。 搜索的基本概念 状态空间的盲目搜索 状态空间的启发式搜索 与或树的盲目搜索 与/或树的启发式搜索 博弈树的启发式搜索
搜索是人工智能中的一个基本问题，并与推理密切相关， 搜索策略的优劣，将直接影响到智能系统的性能与推理效率。 搜索的基本概念 状态空间的盲目搜索 状态空间的启发式搜索 与/或树的盲目搜索 与/或树的启发式搜索 博弈树的启发式搜索 第5章 搜索策略 1
51搜索的基本概念 51.1搜索的含义 512状态空间法 513问题归约法
5.1 搜索的基本概念 5.1.1 搜索的含义 5.1.2 状态空间法 5.1.3 问题归约法 2
51.1搜索的含义 适用情况: 不良结构或非结构化问题;难以获得求解所需的全部信息;更没有现成的 算法可供求解使用。 概念: 依靠经验,利用已有知识,根据问题的实际情况,不断寻找可利用知识 从而构造一条代价最小的推理路线,使问题得以解决的过程称为搜索 搜索的类型 按是否使用启发式信息 盲目搜索:按预定的控制策略进行搜索,在搜索过程中获得的中间信息并 不改变控制策略。 启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导搜索朝 着最有希望的方向前进,加速问题的求解过程并找到最优解 按问题的表示方式: 状态空间搜索:用状态空间法来求解问题所进行的搜索 与或树搜索:用问题归约法来求解问题时所进行的搜索
5.1.1 搜索的含义 适用情况： 不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的 算法可供求解使用。 概念： 依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识， 从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索 搜索的类型 按是否使用启发式信息： 盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并 不改变控制策略。 启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝 着最有希望的方向前进，加速问题的求解过程并找到最优解。 按问题的表示方式： 状态空间搜索：用状态空间法来求解问题所进行的搜索 与或树搜索：用问题归约法来求解问题时所进行的搜索 3
51.2状态空间法 1.状态空间表示方法 状态( State) 是表示问题求解过程中每一步问题状况的数据结构,它可形式地表示为 Sks k0k15 当对每一个分量都给以确定的值时,就得到了一个具体的状态。 操作( Operator) 也称为算符,它是把问题从一种状态变换为另一种状态的手段。。操作可以 是一个机械步骤,一个运算,一条规则或一个过程。操作可理解为状态集合上的 一个函数,它描述了状态之间的关系。 状态空间( State space) 用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元 组表示为: (S, F, G) 其中,S为问题的所有初始状态的集合;F为操作的集合;G为目标状态的集合。 状态空间也可用一个赋值的有向图来表示,该有向图称为状态空间图。在状 态空间图中,节点表示问题的状态,有向边表示操作
5.1.2 状态空间法 1. 状态空间表示方法 状态(State)： 是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为： Sk={Sk0, Sk1, …} 当对每一个分量都给以确定的值时，就得到了一个具体的状态。 操作(Operator) 也称为算符，它是把问题从一种状态变换为另一种状态的手段。。操作可以 是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的 一个函数，它描述了状态之间的关系。 状态空间(State space) 用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元 组表示为： (S, F, G) 其中，S为问题的所有初始状态的集合；F为操作的集合；G为目标状态的集合。 状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状 态空间图中，节点表示问题的状态，有向边表示操作。 4
51.2状态空间法 2状态空间问题求解 状态空间法求解问题的基本过程: 首先为问题选择适当的“状态”及“操作”的形式化 描述方法; 然后从某个初始状态出发,每次使用一个“操作”, 递增地建立起操作序列,直到达到目标状态为止; 此时,由初始状态到目标状态所使用的算符序列就是 该问题的一个解
状态空间法求解问题的基本过程： 首先为问题选择适当的“状态”及“操作”的形式化 描述方法； 然后从某个初始状态出发，每次使用一个“操作”， 递增地建立起操作序列，直到达到目标状态为止； 此时，由初始状态到目标状态所使用的算符序列就是 该问题的一个解。 5.1.2 状态空间法 2. 状态空间问题求解 5