文档介绍：1第六章搜索策略 基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率 2 基本概念?搜索:根据问题的实际情况不断寻找可利用的知识,从而构造一条代价较少的推理路线,使问题得到圆满解决的过程。?盲目搜索:是按预定的控制策略进行搜索,在搜索的过程中获得的中间信息不用来改进控制策略, 搜索具有盲目性,效率不高,不便于复杂问题的求解。?启发式搜索:在搜索中加入了与问题有关的启发式信息,用于指导搜索朝着最有希望的方向前进, 加速问题的求解过程并找到最优解。 3 状态空间表示法?状态空间表示法: 是由“状态”和“算符”来表示问题的一种方法。?状态:描述问题求解过程中任一时刻状况的数据结构,一般用一组变量的有序组合表示: S k =(S k0,S k1…)当每一个分量确定时,就得到一个具体的状态。?算符:引起状态中某些分量发生变化,从而使问题由一个状态变为另一个状态的操作称为算符。 4 状态空间表示法?状态空间:由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间, 一般用一个三元组表示( S,F,G) 。 S:初始状态集合。 F:算符集合。 G:目标状态集合。?状态空间的图示形式称为状态空间图,节点表示状态,有向边(弧)表示算符。 5例:二阶梵塔问题设: S k0:金片 A所在的钢针号 S k1:金片 B所在的钢针号 A(i,j): 金片 A从第 i号针移到第 j号针 B(i,j): 金片 B从第 i号针移到第 j号针 B A12 3 S 0 (1,1) A(1,2) BA 12 3 S 5 (2,3) B(1,3) BA 12 3 S 3 (2,1) 12 3 Sg =S 8 (3,3) A(2,3) B A 6例:二阶梵塔问题状态集: S 0 (1,1) ,S 1 (1,2) ,S 2 (1,3) S 3 (2,1) ,S 4 (2,2) ,S 5 (2,3) S 6 (3,1) ,S 7 (3,2) ,S 8 (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) 状态空间: S={S 0}; G={S 4 ,S 8};F 7例:二阶梵塔问题?状态空间图: ?最优解: A(1,3) , B(1,2) , A(3,2) 1,1 2,1 2,3 3,3 1,3 1,2 2,2 3,1 3,2 A(1,3) B(1,2) A(3,2) 8 状态空间表示法?解题过程?定义状态描述,定义一组算符。?问题的求解过程是一个不断把算符作用于状态的过程。?算符的一次使用,就使问题由一种状态转变为另一种状态,使用算符最少的解称为最优解。?对任何一个状态,可使用的算符不止一个,生成的后继状态可能有多个,涉及搜索策略。 9 与/或树表示法?复杂问题直接求解比较困难,需要简化。?分解:复杂问题分解为子问题。例: P 分解成 P 1,P 2,P 3 三个子问题,只有当这三个子问题都可以解时,问题 P 才可解。 P 1,P 2,P 3 之间存在“与”关系,节点 P为与节点,用一条弧连接。 pp 1p 2p 310 与/或树表示法?等价变换:利用同构或同态的等价变换,把复杂问题变换为若干个较容易求解的新问题。若新问题中有一个可求解,则原问题可解。例: P 被等价变换为三个新问题 P 1,P 2,P 3, 任何一个 Pi 可解, P 可解,则 P 1,P 2,P 3 之间存在或关系,节点P称为或节点。 pp 1p 2p 3