B B S1,1,1) S(1,1,3) S(1,2,3) A B 3 2 123 S(1,2,2) S3,2,2) S(3,2,1) B B A C 2 3 1命2 3 S3,3,1) S3,3,3)
1 2 3 S(3,3,1) C B A 1 2 3 S(1,1,1) C B A 1 2 3 S(1,1,3) C B A 1 2 3 S(1,2,3) C B A 1 2 3 S(1,2,2) B C A 1 2 3 S(3,2,2) A B C 1 2 3 S(3,2,1) C B A C B A 1 2 3 S(3,3,3)
S(1,1,1)S(1,1,3)S(1,2,3)S(1,2,2) 变换（状态） S3,2,2)S3,2,1)S3,3,1)S3,3,3) (1,1,1)→3,3,3) (1,1,1)→(1,2,2) (1,2,2)→3,2,2) (3,2,2)→3,3,3) 1,1,1)→(1,13) (1,1,3)台(1,2,3) (1,2,3)→1,2,2 3,2,2)→3,2,1) 32,1)→3,3,1) 3,3,1)→3,3,3) 有七个终止节点，对应七个原本问题，本 原问题的解左至右顺序
变换（状态） (1,1,1) (3,3,3) (1,1,1)(1,2,2) (1,2,2) (3,2,2) (3,2,2) (3,3,3) (1,1,1)(1,1,3) (1,1,3)(1,2,3) (1,2,3)(1,2,2) (3,2,2)(3,2,1) (3,2,1)(3,3,1) (3,3,1)(3,3,3) 有七个终止节点，对应七个原本问题，本 原问题的解左至右顺序 S(1,1,1) S(1,1,3) S(1,2,3) S(1,2,2) S(3,2,2) S(3,2,1) S(3,3,1) S(3,3,3)
§5.2状态空间的搜索策略 广度优先搜索 深度优先搜索 盲目搜索 有界优先搜索 搜索策略 代价树的广度优先搜索 代价树的深度优先搜索 启发式搜索「局部择优搜索 全部择优搜索 盲目搜索适用： ·搜索按规定路径进行，无启发信息 ·状态空间图为树状结构
§5.2 状态空间的搜索策略 广度优先搜索 深度优先搜索 盲目搜索 有界优先搜索 搜索策略 代价树的广度优先搜索 代价树的深度优先搜索 启发式搜索 局部择优搜索 全部择优搜索 盲目搜索适用： • 搜索按规定路径进行，无启发信息 • 状态空间图为树状结构
1状态空间的一般搜索过程 (1)基本思想 ①初始状态作为当前状态 ②选择适用的算符对其进行操作，生成一组 子状态 ③检查目标状态是否在其中出现，若出现， 搜索成功，找到问题的解，若不出现，按某 种搜索策略从已生成的状态中再选一个状态 作为当前状态 ④重复①-③，直到目标状态出现，或无可用 的算符为止
1 状态空间的一般搜索过程 (1)基本思想 初始状态作为当前状态 选择适用的算符对其进行操作，生成一组 子状态 检查目标状态是否在其中出现，若出现， 搜索成功，找到问题的解，若不出现，按某 种搜索策略从已生成的状态中再选一个状态 作为当前状态 重复-，直到目标状态出现，或无可用 的算符为止
(2)搜索过程 。OPEN表：用于存放则生成的节点 ·CLOSE表：用于存放将要扩展或已扩展的节点 ①把初始节点S0放入OPN表，并建立只含S0的图，记为G OPEN:=So>G:=Go(Go=So) ②检查OPN表是否为空，若为空则问题无解，退出 LOOP:IF(OPEN)=()THEN EXIT(FAIL) ③把0PEN表的第一个节点取出放入CL0SE表，记该节点为 节点n n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSE) ④观寨节点是否为目标节点，若是，则求得问题的解， 退出 IF GOAL(n)THEN EXIT(SUCCESS)
(2)搜索过程 • OPEN表：用于存放刚生成的节点 • CLOSE表：用于存放将要扩展或已扩展的节点 把初始节点S0放入OPEN表，并建立只含S0的图，记为G OPEN:=S0, G:=G0(G0=S0) 检查OPEN表是否为空，若为空则问题无解，退出 LOOP: IF(OPEN)=( )THEN EXIT(FAIL) 把OPEN表的第一个节点取出放入CLOSE表，记该节点为 节点n n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSE) 观察节点n是否为目标节点，若是，则求得问题的解， 退出 IF GOAL(n) THEN EXIT(SUCCESS)