第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
51.2状态空间法 3.状态空间的例子(111) 例5.1二阶梵塔问题。设有三根钢针,它们的编号分别是 1号、2号和3号。在初始情况下,1号钢针上穿有A、B两个 金片,A比B小,A位于B的上面。要求把这两个金片全部移 到另一根钢针上,而且规定每次只能移动一个金片,任何时 刻都不能使大的位于小的上面 解:设用S=(S10,S1)表示问题的状态,其中,S0表示金 片A所在的钢针号,S1表示金片B所在的钢针号。全部可能 的问题状态共有以下9种: 0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S5=(2,2) S=(2,3)S6=(3,1)S1=(3,2)S8=(3,3)
例5.1 二阶梵塔问题。设有三根钢针，它们的编号分别是 1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个 金片，A比B小，A位于B的上面。要求把这两个金片全部移 到另一根钢针上，而且规定每次只能移动一个金片，任何时 刻都不能使大的位于小的上面。 解：设用Sk=(Sk0, Sk1)表示问题的状态，其中，Sk0表示金 片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能 的问题状态共有以下9种： S0=(1, 1) S1=(1, 2) S2=(1, 3) S3=(2, 1) S5=(2, 2) S5=(2, 3) S6=(3, 1) S7=(3, 2) S8=(3, 3) 5.1.2 状态空间法 3. 状态空间的例子(1/11) 6
512状态空间法 3.状态空间的例子(2/11) 问题的初始状态集合为S={S0 目标状态集合为G={S,S5} 初始状态S和目标状态S4S如图所示 A B B B 123 123 S0=(1,1) S=(2,2) S3=(3,3) 二阶梵塔问题的初始状态和目标状态
A B A B A B 1 2 3 1 2 3 1 2 3 二阶梵塔问题的初始状态和目标状态 问题的初始状态集合为S={S0 } 目标状态集合为G={S4 , S5 } 初始状态S0和目标状态S4、S8如图所示 S0=(1, 1) S4=(2, 2) S8=(3, 3) 5.1.2 状态空间法 3. 状态空间的例子(2/11) 7
512状态空间法 3.状态空间的例子(3/11) 操作分别用A(和B(i,j)表示 A(i,j)表示把金片A从第i号钢针移到j号钢针上; B(i,j)表示把金片B从第i号钢针一到第j号钢针上。共有12种 操作,它们分别是: 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) 根据上述9种可能的状态和12种操作,可构成二阶梵塔问题的 状态空间图,如下图所示
操作分别用A(i, j)和B(i, j)表示 A(i, j)表示把金片A从第i号钢针移到j号钢针上； B(i, j)表示把金片B从第i号钢针一到第j号钢针上。共有12种 操作，它们分别是： 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) 根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的 状态空间图，如下图所示。 5.1.2 状态空间法 3. 状态空间的例子(3/11) 8
A(1,2 A(1,3) (3,1) B(1,3 B(1,2) 2,3) (3,2) A(2,3 A(3,2) (3,3) (2,2) 二阶梵塔的状态空间图 从初始节点(1,1到目标节点(2,2)及(3,3的任何一条路径都是问题的 个解。其中,最短的路径长度是3,它由3个操作组成。例如,从(1,1)开始, 通过使用操作A(1,3)、B1,2)及A(3,2),可到达(3,3)
(3,3) (1,3) (1,2) (2,2) 二阶梵塔的状态空间图 从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一 个解。其中，最短的路径长度是3，它由3个操作组成。例如，从 (1, 1)开始， 通过使用操作A(1, 3)、B(1, 2)及A(3, 2)，可到达 (3, 3)。 A(1,2) B(1,3) A(2,3) (1,1) (3,1) (3,2) (2,1) (2,3) A(1,3) B(1,2) A(3,2) 9
512状态空间法 3.状态空间的例子(5/11) 例52修道士( Missionaries)和野人( Cannibals)问题(简称 MC问题)。 设在河的一岸有三个野人、三个修道士和一条船,修道士想 用这条船把所有的人运到河对岸,但受以下条件的约束: 是修道士和野人都会划船,但每次船上至多可载两个人 二是在河的任一岸,如果野人数目超过修道士数,修道士会 被野人吃掉。 如果野人会服从任何一次过河安排,请规划一个确保修道士 和野人都能过河,且没有修道士被野人吃掉的安全过河计划
例5.2 修道士(Missionaries)和野人(Cannibals)问题(简称 M-C问题)。 设在河的一岸有三个野人、三个修道士和一条船，修道士想 用这条船把所有的人运到河对岸，但受以下条件的约束： 一是修道士和野人都会划船，但每次船上至多可载两个人； 二是在河的任一岸，如果野人数目超过修道士数，修道士会 被野人吃掉。 如果野人会服从任何一次过河安排，请规划一个确保修道士 和野人都能过河，且没有修道士被野人吃掉的安全过河计划。 5.1.2 状态空间法 3. 状态空间的例子(5/11) 10