第五章搜索策略 §5.1基本概念 1什么是搜索 ()搜索引起：人工智能要解决的问题大部分 是结构不良或非结构化的问题，而对这样的 问题一般不存在成熟的的求解算法，只能用 已有的知识一步步地摸索着前进 (2)搜索：根据问题的实际情况不断寻找可利 用的知识，从而构造一条代价较少的推理路 线，使问题得到圆满解决的过程。 (3)搜索分为〔盲目搜索 启发式搜索（好）
第五章 搜索策略 §5.1 基本概念 1 什么是搜索 (1)搜索引起：人工智能要解决的问题大部分 是结构不良或非结构化的问题，而对这样的 问题一般不存在成熟的的求解算法，只能用 已有的知识一步步地摸索着前进 (2)搜索：根据问题的实际情况不断寻找可利 用的知识，从而构造一条代价较少的推理路 线，使问题得到圆满解决的过程。 (3)搜索分为 盲目搜索 启发式搜索（好）
·盲目搜索：是按预定的控制策略进行搜索 在搜索的过程获得的中间信息不用来改进控 制策略，搜索具有盲目性，效率不高，不便 于复杂问题的求解 ·启发式搜索：在搜索中加入了与问题有关的 启发式信息，用于指导搜索朝着最有希望的 方向前进，加速问题的求解过程并找到最优 解 2状态空间表示法 ·状态空间表示法是由《状态”和《算符》来 表示问题的一种方法。“状态”用以描述问 题求解过程中不同时刻的状况；“算符”表 示对状态的操作，算符的每一次使用就使问 题由一种状态变换为另一种状态
• 盲目搜索：是按预定的控制策略进行搜索， 在搜索的过程获得的中间信息不用来改进控 制策略，搜索具有盲目性，效率不高，不便 于复杂问题的求解 • 启发式搜索：在搜索中加入了与问题有关的 启发式信息，用于指导搜索朝着最有希望的 方向前进，加速问题的求解过程并找到最优 解 2 状态空间表示法 • 状态空间表示法是由“状态”和“算符”来 表示问题的一种方法。 “状态”用以描述问 题求解过程中不同时刻的状况；“算符”表 示对状态的操作，算符的每一次使用就使问 题由一种状态变换为另一种状态
(1)状态：描迷问题求解过程中任一时刻状况的数据 结构，一般用一组变量的有序组合表示： Sk=(Sko,Sk1...) 当每一个分量确定时，就得到一个具体的状态 (2)算符：引起状态中某些分量发生变化，从而使问 题由一个状态变为另一个状态的操作称为算符 (③)状态空间：由问题的全部状态及一切可用算符所 构成的集合称为问题的状态空间，一般用一个三元 组表示（S,F,G) 初始状态集合算符集合目标状态集合 (4)状态空间的图示形式称为状态空间图，节点表示 状态，有向边（弧）表示算符
(1)状态：描述问题求解过程中任一时刻状况的数据 结构，一般用一组变量的有序组合表示： Sk=(Sk0,Sk1…) 当每一个分量确定时，就得到一个具体的状态 (2)算符：引起状态中某些分量发生变化，从而使问 题由一个状态变为另一个状态的操作称为算符 (3)状态空间：由问题的全部状态及一切可用算符所 构成的集合称为问题的状态空间，一般用一个三元 组表示（S,F,G) 初始状态集合 算符集合 目标状态集合 (4)状态空间的图示形式称为状态空间图，节点表示 状态，有向边（弧）表示算符
例二阶梵塔问题 设：Sk0:金片A所在的钢针号 Sk1:金片B所在的钢针号 A(1,j):金片A从第1号针移到第j号针 B(1,j):金片B从第1号针移到第j号针 42 B(1,3 23 23 23 So(1,1) S3(2,1) Ss(2,3) 状态集： 算符集： So(1,1)S1(1,2)S2(1,3) A(1,2)A(1,3)A(2,1) A2,3 2 S3(2,1)S42,2)Ss(2,3) A(2,3)A(3,1)A(3,2) B(1,2)B(1,3)B(2,1) Sg=Ss(3,3) S6(3,1)S73,2)Sg3,3) B(2,3)B(3,1)B(3,2)
例 二阶梵塔问题 设：Sk0:金片A所在的钢针号 Sk1:金片B所在的钢针号 A(i,j):金片A从第i号针移到第j号针 B(i,j):金片B从第i号针移到第j号针 A B 1 2 3 S0 (1,1) A(1,2) B 1 2 3 S5 (2,3) A B(1,3) A B 1 2 3 S3 (2,1) 1 2 3 Sg=S8 (3,3) A(2,3) B A 状态集： S0 (1,1) S1 (1,2) S2 (1,3) S3 (2,1) S4 (2,2) S5 (2,3) S6 (3,1) S7 (3,2) S8 (3,3) 算符集： 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)
B B(1,2 23 203 2 So(1,1) S6(3,1) S73,2) 22-1=4-1=3 状态空间图 A3,2 23 最优解 Sg=S4(2,2) 状态集： 算符集： S(1,1)S1(1,2)S2(1,3) 23 3,2 A(1,2)A(1,3)A(2,1) S3(2,1)S4(2,2)Ss(2,3) A(2,3)A(3,1)A(3,2) 3,3 1222 S63,1)S73,2)Sg(3,3)B(1,2)B(1,3)B(2,1) B(2,3)B(3,1)B(3,2)
A B 1 2 3 S0 (1,1) A(1,3) B 1 2 3 S7 (3,2) A B(1,2) B A 1 2 3 S6 (3,1) 1 2 3 Sg=S4 (2,2) A(3,2) B A 2 2 -1=4-1=3 状态空间图 最优解 状态集： S0 (1,1) S1 (1,2) S2 (1,3) S3 (2,1) S4 (2,2) S5 (2,3) S6 (3,1) S7 (3,2) S8 (3,3) 算符集： 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) 1,1 2,1 2,3 3,3 1,3 1,2 2,2 3,1 3,2