版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、3 1 心理模拟心理模拟, 符号推演符号推演n“心理模拟, 符号推演”就是从人脑的宏观心理层面入手, 以智能行为的心理模型为依据,将问题或知识表示成某种逻辑网络,采用符号推演的方法,模拟人脑的逻辑思维过程,实现人工智能。n基于心理模拟和符号推演的人工智能研究, 被称为心理学派、逻辑学派、符号主义。早期的代表人物有纽厄尔(Allen Newell)、肖(Shaw)、西蒙(Herbert Simon)等, 后来还有费根宝姆(E. A. Feigenbaum)、尼尔逊(Nilsson)等。 n其代表性理念是所谓的“物理符号系统假设”, 即认为人对客观世界的认知基元是符号, 认知过程就是符号处理的过程
2、;而计算机也可以处理符号, 所以可以用计算机通过符号推演的方式来模拟人的逻辑思维过程, 实现人工智能。4 2 生理模拟生理模拟, 神经计算神经计算n“生理模拟, 神经计算”就是从人脑的生理层面, 即微观结构和工作机理入手,以智能行为的生理模型为依据,采用数值计算的方法,模拟脑神经网络的工作过程, 实现人工智能。n具体来讲, 就是用人工神经网络作为信息和知识的载体,用称为神经计算的数值计算方法来实现网络的学习、记忆、联想、识别和推理等功能。 n采用生理模拟和神经计算方法的人工智能研究, 被称为生理学派、连接主义。5 3行为模拟行为模拟, 控制进化控制进化n基于“感知-行为”模型的研究途径和方法,
3、 称为行为模拟法。用模拟人和动物在与环境的交互、控制过程中的智能活动和行为特性, 如反应、适应、学习、寻优等, 来研究和实现人工智能。强调智能系统与环境的交互, 认为智能取决于感知和行动, 智能行为可以不需要知识, 提出“没有表示的智能”, “没有推理的智能”的观点, 主张智能行为的“感知-动作”模式。n基于行为模拟方法的人工智能研究, 被称为行为主义、 进化主义、控制论学派。行为主义曾强烈地批评传统的人工智能(主要指符号主义, 也涉及连接主义)对真实世界的客观事物和复杂境遇, 作了虚假的、过分简化的抽象。 第第2 2章章 基于图的知识表示与图搜索技术基于图的知识表示与图搜索技术2021-11
4、-21人工智能8第第2 2章章基于图的知识表示与图搜索技术基于图的知识表示与图搜索技术2.1 2.1 概述概述2.2 2.2 状态空间图表示状态空间图表示2.3 2.3 状态空间图的盲目搜索状态空间图的盲目搜索2.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索2.5 2.5 与或图表示及搜索技术与或图表示及搜索技术2.6 2.6 博弈树及搜索技术博弈树及搜索技术2021-11-21人工智能92.1 2.1 概述概述2.1.1 2.1.1 知识与问题求解框架知识与问题求解框架2.1.2 2.1.2 知识表示知识表示2.1.3 2.1.3 图搜索技术图搜索技术2021-11-21人工智能
5、102.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(1)(1) 1.知识的定义知识的定义心理学心理学:个体通过与环境相互作用后获得的信息及其组织。费根鲍姆费根鲍姆:知识是经过消减、塑造、解释和转换的信息。博恩斯坦博恩斯坦(Bernstein):知识是由特定领域的描述、关系和过程组成的。 概括地说,知识是高度组织起来的信息集团,是人们在长期的生活和社会实践中、科学研究和科学实验中积累起来的经验或对客观世界规律的认识等。2.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(2)(2)2.知识的分类知识的分类(1)从应用领域来划分n常识性知识n领域(专业)性知识(2)从在问题求
6、解中的作用来划分n叙述性知识n过程性知识n控制性知识(3)从确定性来划分n确定性知识n非确定性知识(4)从知识的表现形式来划分,可分为文字、符号、声音、图形、图像等。2021-11-21人工智能112.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(3)(3)3.问题求解框架问题求解框架问题:问题:是指事件或事物的已知或当前状态当前状态与目标状态目标状态之间有差异差异。问题求解:问题求解:是指在一定的控制策略下,通过通过一系列的操作操作或运算运算来改变改变问题的状态状态,使之与目标状态接近或一致。例如,李明在北京,他要去西安(办事)。又如,博弈问题。问题的求解框架问题的求解框架(1)
7、叙述性知识:叙述性知识:描述问题的状态有关的各种知识。(2)过程性知识:过程性知识:描述状态之间的变换关系的各种知识。(3)控制性知识:控制性知识:描述如何在当前状态下选择合适操作的知识。2021-11-21人工智能122021-11-21人工智能132.1.2 2.1.2 知识表示知识表示(1)(1)知识表示:知识表示:就是研究在计算机中在计算机中如何用最合适的形式表示表示问题求解过程中所需要的各种知识,包括构成问题求解框架的全部知识。常用的知识表示形式常用的知识表示形式状态空间图与或图谓词逻辑产生式框架语义网络2.1.2 2.1.2 知识表示知识表示(2)(2)2021-11-21人工智能
8、14例例2.12.1麦卡赛问题麦卡赛问题。 在一个2n2n的方格棋盘中,去掉对角的两个方格,如图(a),问能否将它全部划成若干12的小长方块?目标状态目标状态初始状态初始状态可达状态可达状态同构问题同构问题同态问题同态问题2021-11-21人工智能152.1.3 2.1.3 图搜索技术图搜索技术(1)(1)1.搜索搜索 搜索,简单地说就是“寻找”,目的是找到问题的解。在问题求解过程中,待求解的问题被抽象成一定空间上的图,搜索过程就是从图中初始节点出发,沿着与之相连的边试探着前进,寻找目标节点或可解节点的过程。2.搜索树搜索树 搜索过程中经过(考察过)的节点和边,按原图的连接关系,便会构成一个
9、树型的有向图,称为搜索树。搜索树是一个搜索过程的搜索轨迹,或称之为搜索空间。2.1.3 2.1.3 图搜索技术图搜索技术(2)(2)2021-11-21人工智能16图 2-2搜索空间示意图问题的状态空间、搜索空间及解的示意图:2.1.3 2.1.3 图搜索技术图搜索技术(3)(3)3.搜索策略搜索策略 搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点。盲目搜索盲目搜索:无向导的搜索,也称穷举搜索。启发式搜索启发式搜索:利用“启发性信息”作为导航的搜索过程。 对于较大或无限状态空间问题,盲目搜索效率太低,所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中,
10、如博弈、机器学习、数据挖掘、智能检索等。2021-11-21人工智能172021-11-21人工智能182.2 2.2 状态空间图表示状态空间图表示2.2.1 2.2.1 状态空间图状态空间图2.2.2 2.2.2 隐式状态空间图隐式状态空间图2021-11-21人工智能192.2.1 2.2.1 状态空间图(状态空间图(1 1)1.状态状态 状态对应叙述性知识状态对应叙述性知识,描述一个问题在开始、结束或中间的某一时刻所处的状况或状态。通常引进一组变量 ,表示与问题状态相关的各种要素,并用这组变量所构成的多元组 来表示状态。 状态在状态图中表示为节点节点。12nqqq, , ,12()nqq
11、q, ,2021-11-21人工智能202.2.1 2.2.1 状态空间图(状态空间图(2 2)2.2.操作操作 操作对应过程性知识操作对应过程性知识,即状态转换规则,描述状态之间的关系。描述一个操作要包含两个部分 条件条件:指明被作用的状态要满足的约束条件 动作动作:指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤、过程、规则或算子。操作在状态图中表示为边边。在程序中,状态转换规则可用数据对、条件语句、规则、函数、过程等表示。 如:如果室内温度低于26度,则关闭空调。 2021-11-21人工智能212.2.1 2.2.1 状态空间图(状态空间图(3 3)3.状态空间
12、图状态空间图问题的状态空间图是一个描述该问题全部可能的状态及相互关系的图,如考虑操作的代价,状态空间图就是一个赋值有向图。状态空间常记为三元组: S:初始状态的集合 F:操作的集合 G:目标状态的集合。 由问题的状态空间表示就可以构造出状态空间图。SFG, ,2.2.1 2.2.1 状态空间图(状态空间图(4 4)4.求解求解n在状态空间表示法中,问题求解过程转化为在图中在状态空间表示法中,问题求解过程转化为在图中寻找寻找从初始状态从初始状态Q Qs s出发出发到达到达目标状态目标状态Q Qg g的的路径路径问题问题,也就是寻找操作序列的问题。,也就是寻找操作序列的问题。n状态空间的解为三元组
13、状态空间的解为三元组 Q nQ Qs s :某个初始状态:某个初始状态nQ Qg g :某个目标状态:某个目标状态na a:把:把Q Qs s变换成变换成Q Qg g的有限的操作序列的有限的操作序列n状态转换图状态转换图S1S3S2f1f2f3f4QsQgfn2021-11-21人工智能222021-11-21人工智能23例例2.2 翻转钱币问题(翻转钱币问题(1) 三枚钱币处于反、正、反状态,每次只许翻动一枚钱币,问连续翻动三次后,能否出现全正或全反状态。 初始状态Qs目标状态集合Q0, Q7例例2.2 翻转钱币问题(翻转钱币问题(2)引入一个三元组引入一个三元组(q(q0 0,q,q1 1
14、,q,q2 2) )来描述总状态,钱币正面为来描述总状态,钱币正面为0 0,反面,反面为为1 1,全部可能的状态为:,全部可能的状态为: Q Q0 0=(0,0,0)=(0,0,0) ; Q ; Q1 1=(0,0,1); Q=(0,0,1); Q2 2=(0,1,0)=(0,1,0) Q Q3 3=(0,1,1) ; Q=(0,1,1) ; Q4 4=(1,0,0); =(1,0,0); Q Q5 5=(1,0,1)=(1,0,1) Q Q6 6=(1,1,0) ; =(1,1,0) ; Q Q7 7=(1,1,1)=(1,1,1)。翻动钱币的操作抽象为改变上述状态的算子,翻动钱币的操作抽象
15、为改变上述状态的算子, 即即F Fa, b, ca, b, c a: a:把钱币把钱币q q0 0翻转一次翻转一次 b:b:把钱币把钱币q q1 1翻转一次翻转一次 c:c:把钱币把钱币q q2 2翻转一次翻转一次 问题的状态空间为问题的状态空间为 2021-11-21人工智能24例例2.2 翻转钱币问题(翻转钱币问题(4)3.状态空间图状态空间图 问题的状态空间为: 2021-11-21人工智能25 构造状态空间图: 507QabcQQ, , , ,aabababaabbbbcccbcccb例例2.2 翻转钱币问题(翻转钱币问题(5)2021-11-21人工智能26图2-5 翻动三次后三枚钱
16、币问题的状态变化翻转钱币问题状态空间图的另一种表示:2021-11-21人工智能27例例2.3修道士和野人问题(修道士和野人问题(1) 在河的左岸有三个修道士、三个野人和一条船,修在河的左岸有三个修道士、三个野人和一条船,修道士们想用这条船将所有的人都运过河去,但受到以下道士们想用这条船将所有的人都运过河去,但受到以下条件的限制:条件的限制: (1 1)修道士和野人都会划船,但船一次)修道士和野人都会划船,但船一次最多最多只能只能运运两个人两个人; (2 2)在任何岸边)在任何岸边野人数目野人数目都都不得超过修道士不得超过修道士,否则,否则修道士就会被野人吃掉。修道士就会被野人吃掉。 假定野人
17、会服从任何一种过河安排,试规划出一种确假定野人会服从任何一种过河安排,试规划出一种确保修道士安全过河方案。保修道士安全过河方案。2021-11-21人工智能28例例2.3修道士和野人问题(修道士和野人问题(2)1 1、问题的状态、问题的状态可以用一个三元数组来描述:可以用一个三元数组来描述: S S(m, c, b)(m, c, b) m m:左岸的修道士数:左岸的修道士数 c c:左岸的野人数:左岸的野人数 b b:左岸的船数:左岸的船数 右岸的状态不必标出,因为:右岸的状态不必标出,因为: 右岸的修道士数右岸的修道士数 mm 3 3m m 右岸的野人数右岸的野人数 cc 3 3c c 右岸
18、的船数右岸的船数 bb 1 1b b2021-11-21人工智能29例例2.3修道士和野人问题(修道士和野人问题(3)状态m, c, b状态m, c, b状态m, c, b状态m, c, bS03 3 1S81 3 1S163 3 0S241 3 0S13 2 1S91 2 1S173 2 0S251 2 0S23 1 1S101 1 1S183 1 0S261 1 0S33 0 1S111 0 1S193 0 0S271 0 0S42 3 1S120 3 1S202 3 0S28 0 3 0S52 2 1S130 2 1S212 2 0S290 2 0S62 1 1S140 1 1S222
19、1 0S300 1 0S72 0 1S150 0 1S232 0 0S310 0 02021-11-21人工智能30例例2.3修道士和野人问题(修道士和野人问题(4)2.2.操作集操作集Fp01, p10,p11,p02,p20,q01,q10,q11, q02,q20q20b=0, (m=0,c=2)或(m=1,c=1)b=1, m=m+2q02b=0, m=0或3, c2b=1, c=c+2q11b=0, m=c, c2b=1, m=m+1, c=c+1q10b=0, (m=0,c=1)或(m=2,c=2)b=1, m=m+1q01b=0, m=0或3, c2b=1, c=c+1p20b=
20、1, (m=3,c=1)或(m=2,c=2)b=0, m=m-2p02b=1, m=0或3, c2b=0, c=c-2p11b=1, m=c, c1b=0, m=m-1, c=c-1p10b=1, (m=3,c=2)或(m=1,c=1)b=0, m=m-1p01b=1, m=0或3, c1b=0, c=c-1操作符条 件动 作例例2.3修道士和野人问题(修道士和野人问题(5)3.状态空间状态空间给出状态和操作的描述之后,该问题的状态空间是:S0, P 01,P 10,P 11,P 02,P 20,Q01,Q 10,Q 11,Q 02,Q 20,S31。2021-11-21人工智能32例例2.3
21、修道士和野人问题(修道士和野人问题(6)S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S31(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S30(0,1,0) p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.4.状态空间图:状态空间图:四条S0到
22、S31长度相等的最短路径,对应的操作序列就是该问题的四个最优解2021-11-21人工智能332.2.2 2.2.2 隐式状态空间图隐式状态空间图显式状态空间图:显式状态空间图:表示了问题所有可能的状态及状态之间的关系,这种表示方式称为显式状态空间显式状态空间图图,或称为状态空间图的显示表示状态空间图的显示表示。隐式状态空间图隐式状态空间图:利用有关状态描述和状态转换(操作)的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识,包括该问题的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态,以及全部操作的条件和动作等。隐式状态空间图也称为是状态空间图的隐式表状态空间图
23、的隐式表示或隐式图示或隐式图。重排九宫问题的隐式图描述为: (1)有关状态的知识:)有关状态的知识:状态S的定义:S(X0,X1,X2,X3,X4 ,X5, X6 ,X7 ,X8) 其中, Xi0,1,2,3,4,5,6,7,8, ,且 。初始状态: S0 (0,1,2,3,5,6,4,7,8) 目标状态: Sg (0,1,2,3,4,5,6,7,8) 重排九宫问题的状态表示80 iijijXX时,例例2.42.4重排九宫问题重排九宫问题(八数码问题)(八数码问题) 例例2.42.4重排九宫问题(重排九宫问题(2 2)(2 2)有关操作的知识(规则):)有关操作的知识(规则):0 0组规则组规
24、则 R R1 1(X(X0 0=0=0 ) ) (X(X2 2=n=n ) ) X X0 0 = n = n X X2 2 =0 =0; R R2 2(X(X0 0=0=0 ) ) (X(X4 4=n=n ) ) X X0 0 = n = n X X4 4 =0 =0; R R3 3(X(X0 0=0=0 ) ) (X(X6 6=n=n ) ) X X0 0 = n = n X X6 6 =0 =0; R R4 4(X(X0 0=0=0 ) ) (X(X8 8=n=n ) ) X X0 0 = n = n X X8 8 =0 =0;1 1组规则组规则 R R5 5(X(X1 1=0=0 ) )
25、 (X(X2 2=n=n ) ) X X1 1 = n = n X X2 2 =0 =0; R R6 6(X(X1 1=0=0 ) ) (X(X8 8=n=n ) ) X X1 1 = n = n X X8 8 =0 =0;8 8组规则组规则: : R R2222(X(X8 8=0=0 ) ) (X(X1 1=n=n ) ) X X8 8 = n = n X X1 1 =0 =0; R R2323(X(X8 8=0=0 ) ) (X(X0 0=n=n ) ) X X8 8 = n = n X X0 0=0=0; R R2424(X(X8 8=0=0 ) ) (X(X7 7=n=n ) ) X
26、X8 8 = n = n X X7 7 =0 =0;例例2.42.4重排九宫问题(重排九宫问题(3 3)八数码的状态图可表示为八数码的状态图可表示为 (SS0 0, r, r1 1 , r , r2 2 , , r , , r2424 , S , Sg g ) 八数码问题状态图仅给出了初始节点八数码问题状态图仅给出了初始节点和目标节点,其余节点需用状态转换规则和目标节点,其余节点需用状态转换规则来产生。类似于这样表示的状态图称为来产生。类似于这样表示的状态图称为隐隐式状态图式状态图,或者说,或者说状态图状态图的的隐式表示隐式表示。例例2.42.4重排九宫问题(重排九宫问题(4 4)(3 3)隐
27、式图搜索)隐式图搜索 初始状态S( 0,1,2,3,5,6,4,7,8 )满足条件X0 =0,故可以使用第0组的四条规则: 如果选择规则R1,则状态转换为:S1( 2,1,0,3,5,6,4,7,8)R2R4R1R3 1 2 3 8 5 7 4 6 1 3 8 2 5 7 4 6 1 2 3 8 5 7 4 6 1 2 3 8 4 5 7 6 1 2 3 8 8 5 7 4 62021-11-21人工智能38例例2.5 2.5 旅行商问题旅行商问题(TSP)(1)(TSP)(1) 设有n个互相可直达的城市,某推销商准备从其中的A城出发,周游各城市一遍,最后又回到A城。要求为该推销商规划一条最短
28、的旅行路线。(1)状态描述状态描述:该问题的状态为以A打头城市序列: =AA1Ai AjA其中:A、Ai、Aj、A为城市名, 1i、jn-1,AjA,AiA; 1|n+1;当i j 时,Ai Aj; 当且仅当|=n+1时,A=A。初始状态初始状态:=A,|=1终止状态终止状态:=AA1A2A,|=n+1例例2.5 2.5 旅行商问题旅行商问题(TSP)(2)(TSP)(2)(2)操作描述)操作描述(状态转换规则):规则规则1 :如果=AA1Ai Aj,且| n,但A,则置= A。即没遍历完时,在城市序列中添加一个没有到过的城市。规则规则2 :如果|= n,置= A,即从当前城市返回A城。 (3
29、 3)隐式图搜索)隐式图搜索对于有A、B、C、D四个城市所组成的连通城市网,初始状态:=A,|=1,满足规则1 ,则操作的结果为:=AB 、或=AC、或=AD,继续使用规则1 ,直到生成包含四个城市的序列出现,再使用规则2。2021-11-21人工智能39补充例补充例 二阶梵塔问题(二阶梵塔问题(1 1) 一号杆有一号杆有A A、B B两个金盘,两个金盘,A A小于小于B B。要求将。要求将A A、B B移至三号移至三号杆,每次只可移动一个盘子,任何时刻杆,每次只可移动一个盘子,任何时刻B B不能在不能在A A上。上。 (1 1)有关状态的知识:)有关状态的知识:用二元组用二元组(S SA A
30、,S SB B)表示状态,表示状态,S SA A表示表示A A所在杆号,所在杆号,S SB B表示表示B B所在杆号。其中所在杆号。其中: : S SA A ,S SB B 1,2,31,2,3 , , 则则全部状态如下:全部状态如下: (1 1,1 1),(),(1 1,2 2),(),(1 1,3 3) (2 2,1 1),(),(2 2,2 2),(),(2 2,3 3) (3 3,1 1),(),(3 3,2 2),(),(3 3,3 3)初始状态为初始状态为(1 1,1 1),),终止状态为终止状态为:(:(3 3,3 3) 。2021-11-21人工智能40AB123S0:(:(1
31、,1)123S1:(:(1,2)123S2:(:(1,3)AA123S5:(:(2,3)123S4:(:(2,2)123S3:(:(2,1)123S8:(:(3,3)123S7:(:(3,2)123S6:(:(3,1)AAAAABABBBBB补充例补充例 二阶梵塔问题(二阶梵塔问题(2 2)2021-11-21人工智能41(2 2)有关操作的知识(规则):)有关操作的知识(规则): A A(i i,j j)表示金盘)表示金盘A A从第从第I I号杆移到号杆移到j j号杆,号杆,B B(i i,j j)表示金盘)表示金盘B B从第从第i i号杆移到号杆移到j j号杆,其中:号杆,其中:i,j i
32、,j 1,2,31,2,3,但,但i i j j ,全部操作为:,全部操作为: A A(1 1,2 2),),A A(1 1,3 3),), A A(2 2,1 1) A A(2 2,3 3),),A A(3 3,1 1),), A A(3 3,2 2) B(1 1,2 2),),B B(1 1,3 3),), B B(2 2,1 1) B B(2 2,3 3),),B B(3 3,1 1),), B B(3 3,2 2)分析每个操作的条件和动作,得到下表:分析每个操作的条件和动作,得到下表:补充例补充例 二阶梵塔问题(二阶梵塔问题(3 3)2021-11-21人工智能42补充例补充例 二阶梵
33、塔问题(二阶梵塔问题(4 4)操作符操作符条件动作A A(1 1,2 2)SA=1SA=2A A(1 1,3 3)SA=1SA=3A A(2 2,1 1)SA=2SA=1A A(2 2,3 3)SA=2 SA=3A A(3 3,1 1)SA=3 SA=1A A(3 3,2 2)SA=3 SA=2B(1 1,2 2)SB=1, SA 1,2 或或SA=3SB=2B B(1 1,3 3)SB=1, SA 1,3 或或SA=2SB=3B B(2 2,1 1)SB=2, SA 1,2 或或SA=3SB=1B B(2 2,3 3)SB=2, SA 2,3 或或SA=1SB=3B B(3 3,1 1)SB
34、=3, SA 1,3 或或SA=2SB=1B B(3 3,2 2)SB=3, SA 2,3 或或SA=1SB=22021-11-21人工智能43补充例补充例 二阶梵塔问题(二阶梵塔问题(5 5)(3 3)状态空间图)状态空间图1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)2021-11-21人工智能442.3 状态空间图的盲目搜索状态空间图的盲目搜索n盲目搜索盲目搜索:搜索时不参考与具体待求解问题相关的任何信息,只是按预先设定的顺序逐个考察节点。盲目搜索与问题无关,具有通用性。n
35、算法中使用的数据结构算法中使用的数据结构:OPEN表表:专门登记已经生成但还没有考察的节点,即待考察节点。CLOSED表:表:用来记录考察过的节点以及节点之间的关系,如每个节点指向父节点的编号(返回指针)。CLOSED表中存放的就是一定搜索策略下的搜索树。2021-11-21人工智能45节点父节点编号编号节点父节点编号OPEN表表CLOSED表表2021-11-21人工智能462.3 状态空间图的盲目搜索状态空间图的盲目搜索2.3.1 广度优先搜索广度优先搜索2.3.2 深度优先搜索深度优先搜索2021-11-21人工智能472.3.1 广度优先搜索(广度优先搜索(1)广度优先搜索(广度优先搜
36、索(A A?eded)基本思想:)基本思想: 广度优先搜索是严格按节点在树中的出现位置一层一层向下的搜索过程。通过将OPEN表设计为一个队列来实现,将新生成的子节点放在OPEN表的后面,保证先生成的节点先考察。广度优先搜索算法:广度优先搜索算法:步步1 1 把初始节点把初始节点S S0 0放入放入OPENOPEN表中;表中;步步2 2 若若OPENOPEN表为空,则搜索失败,退出;表为空,则搜索失败,退出;步步3 3 否则,取否则,取OPENOPEN表中第一个节点表中第一个节点N N放在放在CLOSEDCLOSED表中;并冠以顺序表中;并冠以顺序编号编号n n;步步4 4 若节点若节点N N为
37、目标节点,则搜索成功。利用为目标节点,则搜索成功。利用CLOSEDCLOSED表中的返回指表中的返回指针找出针找出S S0 0到到N N的路径即为所求解,退出;的路径即为所求解,退出;步步5 5 若若N N不可扩展,转步不可扩展,转步2 2;步步6 6 否则,扩展否则,扩展N N,将其所有子节点配上指向,将其所有子节点配上指向N N的返回指针放入的返回指针放入OPENOPEN表的表的尾部尾部,转步,转步2 2。2.3.1 广度优先搜索(广度优先搜索(2)2021-11-21人工智能49例例2.6使用广度优先搜索算法求解重排九宫问题使用广度优先搜索算法求解重排九宫问题1 2 38 57 4 61
38、1 2 38 5 67 481 38 2 57 4 6101 2 38 4 5 7 671 2 38 4 57 6 6 1 38 2 57 4 6111 2 38 4 57 621 2 38 5 7 4 631 2 38 4 57 641 2 37 8 5 4 612 2 31 8 57 4 6131 2 38 47 6 5141 2 3 4 58 7 6151 28 5 37 4 6171 3 58 27 4 6188 1 3 2 57 4 6191 2 37 8 54 6202 31 8 5 7 4 6211 28 4 37 6 5221 2 3 8 57 4 651 2 38 47 6
39、523八数码广度优先搜索八数码广度优先搜索1 28 5 37 4 69161 2 38 5 67 42021-11-21人工智能502.3.1 广度优先搜索广度优先搜索广度优先搜索的特点:广度优先搜索的特点:广度优先中OPEN表是一个队列,CLOSED表是一个顺序表,表中各节点按顺序编号,正被考察的节点在表中编号最大。广度优先搜索又称为宽度优先或横向搜索。广度优先策略是完备的,即如果问题的解存在,则它一定可以找到解,并且找到的解还是最优解。广度优先搜索策略与问题无关,具有通用性。缺点搜索效率低。2021-11-21人工智能512.3.2 深度优先搜索深度优先搜索(1)深度优先搜索的基本思想:深
40、度优先搜索的基本思想: 深度优先搜索是一种一直向下的搜索过程,它优先在自己的子节点集合中选择下一个被考察的节点,不断向纵深方向前进,直到到达叶子节点或受到深度限制时,才返回到上一级节点沿另一方向继续前进。深度优先搜索算法:深度优先搜索算法: 与广度优先搜索策略的唯一不同点就是OPENOPEN表表被设计成后进先出的栈后进先出的栈,新生成的子节点放在OPEN表的前面,后生成的节点优先被考察。深度优先搜索算法只需将宽将宽度优先搜索算法步度优先搜索算法步6 6修改为修改为:步步6 6 否则,扩展否则,扩展N N,将其所有子节点配上指向,将其所有子节点配上指向N N的指针的指针放入放入OPENOPEN表
41、的表的首部首部,转步,转步2 2。 例例2.7使用深度优先搜索算法求解重排九宫问题使用深度优先搜索算法求解重排九宫问题 1 2 38 57 4 611 2 38 4 5 7 631 2 38 4 57 6 1 2 38 4 57 61 2 38 5 7 4 61 2 38 4 57 61 2 38 47 6 541 28 4 37 6 51 2 3 8 57 4 621 2 38 47 6 552021-11-21人工智能532.3.2 深度优先搜索深度优先搜索深度优先搜索的特点深度优先搜索的特点:OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。如下图所示:图2-13 深度
42、优先搜索不具有完备性示意图2021-11-21人工智能541.1.有界深度优先搜索(有界深度优先搜索(A Acdcd )为克服深度优先搜索的不足,可以对其深度进行为克服深度优先搜索的不足,可以对其深度进行限制限制n深度界限的选择很重要深度界限的选择很重要 d dm m 若太小,则达不到解的深度,得不到解;若太若太小,则达不到解的深度,得不到解;若太大,既浪费了计算机的存储空间与时间,又降低了搜索大,既浪费了计算机的存储空间与时间,又降低了搜索效率。由于解的路径长度事先难以预料,所以要恰当地效率。由于解的路径长度事先难以预料,所以要恰当地给出给出d dm m的值是比较困难的。的值是比较困难的。n
43、即使能求出解,它也不一定是最优解。即使能求出解,它也不一定是最优解。2.2.可变界深度优先搜索算法可变界深度优先搜索算法(1)(1) 当在dm界限之内找不到解时,可以将深度界限dm不断扩大,每次增加一个深度增量d,直到找到解,或者搜索完整棵树。这样算法的完备性得到了保证,称为可变界深度优先搜索算法(或迭代加深搜索)。 当d =1时,算法开始蜕变为广度优先搜索算法。 2.2.可变界深度优先搜索算法可变界深度优先搜索算法(2)(2)n迭代加深搜索过程:迭代加深搜索过程:步步1 把初始节点把初始节点S0放入放入OPEN表中,置表中,置S0的深度的深度d( S0 )0,dm为任意初值。为任意初值。步步
44、2 若若OPEN表为空,表为空,则考查则考查CLOSED表是否有待扩展节点:表是否有待扩展节点: 若无,则问题无解,退出。若无,则问题无解,退出。 若有,则取出若有,则取出CLOSED表中待扩展节点放入到表中待扩展节点放入到OPEN表表中,令中,令 dm=dm+d。 2.2.可变界深度优先搜索算法可变界深度优先搜索算法(3)(3) 步步3 取取OPEN表中第一个节点表中第一个节点N放在放在CLOSED表中;并表中;并冠以编号冠以编号n; 步步4 若节点若节点N为目标节点,成功退出。为目标节点,成功退出。 步步5 若若N的深度的深度d(N)dm(深度限制值),(深度限制值),则标则标N为为待扩展
45、节点,待扩展节点,则转步则转步2; 步步6 N无子节点,则转步无子节点,则转步2; 步步7 扩展扩展N,将其所有子节点,将其所有子节点Ni配上指向配上指向N的指针放入的指针放入OPEN首部首部, 置置 d( Ni )d(N)1,转步,转步2。3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(1)(1)问题:问题:当d d 1 时, 是否能保证找到最优解?2021-11-21人工智能603.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(2)(2)步步1 1 把初始节点把初始节点S S0 0放入放入OPENOPEN表中,置表中,置d(Sd(S0 0)=0)=0,d
46、dm m=d=dm0m0,G=NULLG=NULL。步步2 2 若若OPENOPEN表为空,则考察表为空,则考察CLOSEDCLOSED表是否有待扩展节点:表是否有待扩展节点: (1 1)若无待扩展节点,则判断)若无待扩展节点,则判断G G表是否为空:表是否为空: 若为空,搜索失败,退出;若为空,搜索失败,退出; 否则,取出否则,取出G G表最后面的节点表最后面的节点S Sg g, S Sg g即为所求最优解,搜即为所求最优解,搜索成功,退出;索成功,退出; (2 2)若有待扩展节点,则取出)若有待扩展节点,则取出CLOSEDCLOSED表中待扩展节点放入到表中待扩展节点放入到OPENOPEN
47、表中,令表中,令dm=dm+d,转步,转步2 2;3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(3)(3)步步3 3 取取OPENOPEN表中首部的节点表中首部的节点N N放在放在CLOSEDCLOSED表中;并冠以顺序编号表中;并冠以顺序编号n n; 步步4 4 若若d(N N)dm m,则标,则标N N为待扩展节点,转步为待扩展节点,转步2 2;步步5 5 若若N N是目标节点是目标节点S Sg g ,则令,则令dm md( S Sg g )-1 ,把,把S Sg g放到放到G G 表的尾表的尾部,转步部,转步2 2。步步6 6 若若N N不可扩展,则转步不可扩展,则转
48、步2 2; 步步7 7 否则,扩展否则,扩展N N,将其所有子节点,将其所有子节点N Ni i配上指向配上指向N N的返回指针放入的返回指针放入OPENOPEN表首部,表首部, 置置d( Ni )d(N)1 ,转步,转步2 2。 2021-11-21人工智能612.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(1)(1)1.启发性知识与启发函数启发性知识与启发函数启发性知识启发性知识 就是与被求解问题自身特性相关的知识,包括被求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等,对应于问题求解框架中的控制性知识。 启发函数启发函数 要实现启发式搜索,需要把启发性知
49、识形式化,即用一定的函数表示出来,通过函数计算来评价每种选择的价值大小,用以指导搜索过程,这样的函数称为启发函数。 2021-11-21人工智能622021-11-21人工智能632.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(2)(2)2.启发函数的设计启发函数的设计 在实际设计过程中,启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数,通常记为h(x)。启发函数可以是:(1)一个节点到目标节点的某种距离或差异的量度;(2)一个节点处在最佳路径上的概率;(3)根据主观经验的主观打分等。2021-11-21人工智能642.4 2.4 状态空间图的启发式搜索状态空间图的启发
50、式搜索(3)(3)2.4.1 启发式搜索算法启发式搜索算法2.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法算法2.4.3 A*算法在游戏中的应用算法在游戏中的应用2021-11-21人工智能652.4.1 启发式搜索算法启发式搜索算法(1 1)启发式搜索启发式搜索用启发函数来导航,其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程,并且由启发函数值来确定节点的扩展顺序。按选择范围不同,启发式搜索分为按选择范围不同,启发式搜索分为:全局择优搜索全局择优搜索局部择优搜索局部择优搜索2021-11-21人工智能662.4.1 启发式搜索算法启发式搜索算法(2 2)1.
51、全局择优搜索全局择优搜索基本思想:基本思想:在OPEN表中保留所有已生成而未考察的节点,并用启发函数h(x)对它们全部进行估价,从中选出最优节点进行扩展,而不管这个节点出现在搜索树的什么地方。2.4.1 启发式搜索算法启发式搜索算法(3 3)全局择优搜索算法:全局择优搜索算法:步步1 1 把初始节点把初始节点S S0 0放入放入OPENOPEN表中,计算表中,计算h(Sh(S0 0) );步步2 2 若若OPENOPEN表为空,则搜索失败,退出;表为空,则搜索失败,退出;步步3 3 否则,移出否则,移出OPENOPEN表中第一个节点表中第一个节点N N放入放入CLOSEDCLOSED表中,表中
52、,并冠以序号并冠以序号n n ;步步4 4 若目标节点若目标节点Sg Sg N N,则搜索成功,利用,则搜索成功,利用CLOSEDCLOSED表中表中的返回指针找出的返回指针找出S S0 0到到N N的路径即为所求解,退出;的路径即为所求解,退出;步步5 5 若若N N不可扩展,则转步不可扩展,则转步2 2 ;步步6 6 否则,扩展否则,扩展N N,计算,计算N N的每个子节点的每个子节点x x的函数值,并将的函数值,并将N N所有子节点所有子节点x x配以指向配以指向N N的返回指针后放入的返回指针后放入OPENOPEN表中表中,依据启发函数对节点的计算,再对,依据启发函数对节点的计算,再对
53、OPENOPEN表中表中所有节所有节点点按其启发函数值的大小以升序排列,转步按其启发函数值的大小以升序排列,转步2 2。2021-11-21人工智能672.4.1 启发式搜索算法启发式搜索算法(4 4)2.局部择优搜索局部择优搜索基本思想:基本思想:局部择优搜索是在启发性知识导航下的深度优先搜索,在OPEN表中保留所有已生成而未考察的节点,对其中新生成的每个子节点x计算启发函数,从全部子节点中选出最优节点进行扩展,其选择下一个要考察节点的范围是刚刚生成的全部子节点,局部择优搜索算法:局部择优搜索算法: 与全局择优搜索算法的区别仅在步步6: 步步6 6 否则,扩展否则,扩展N N,计算,计算N
54、N的每个子节点的每个子节点x x的函数值,并将的函数值,并将N N的所有子节点的所有子节点x x配以指向节点配以指向节点N N的指针后,将的指针后,将全部子节点全部子节点按按启发函数值升序排列后放入启发函数值升序排列后放入OPENOPEN表的首部,转步表的首部,转步2 2。2021-11-21人工智能682.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法(算法(1) 启发函数是对当前节点到达目标节点未来可能要付出的代价的估计。 在全局择优和局部择优搜索算法中,都没有考虑从初始节点到当前节点已经付出的实际代价。 在很多实际问题中,已经付出的实际代价是必须考虑的,如TSP问题等。将两者同时
55、考虑,用于指导搜索的算法称为A算法和算法和A*算法算法。内容回顾:树形图树式搜索策略比较内容回顾:树形图树式搜索策略比较全局全局局部局部深度深度d(x)d(x)宽度优先搜索宽度优先搜索 深度优先搜索深度优先搜索启发值启发值h(x)h(x)全局择优搜索全局择优搜索 局部择优搜索局部择优搜索代价值代价值g(x)g(x)分支界限法分支界限法瞎子爬山法瞎子爬山法范围范围标准标准S S0 0S Sg g2 23 3a ab b4 46 61 15 5c cd dg gf fh hi ij jk k5 5f f5 54 43 37 78 89 9h h(x x),有利于搜索纵向发展,有利于搜索纵向发展,提
56、高搜索效率,但影响完备性。提高搜索效率,但影响完备性。g g(x x),有利于搜索横向发展,有利于搜索横向发展,提高完备性,但影响搜索效率。提高完备性,但影响搜索效率。穷举式搜索穷举式搜索启发式搜索启发式搜索加权状态图搜索加权状态图搜索2021-11-21人工智能712.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法(算法(2)1. 1. A算法算法估价函数估价函数f(x) : :为了防止在单独利用启发函数的时候误入歧途,将启发函数h(x)与代价函数g(x)相结合,即初始节点S0到达节点x处已付出的代价与节点x 到达目标节点Sg的接近程度估计值总和。 f(x) g(x)h(x) g(x
57、)代价函数)代价函数:初始节点S0到达节点x处已付出的代价,有利于搜索纵向发展,提高搜索效率,但影响完备性。 h(x)启发函数)启发函数:节点x 到达目标节点Sg的接近程度估计值有利于搜索横向发展,提高搜索的完备性,但影响搜索效率。2.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法(算法(3)代价代价g(x)的计算的计算 g(x)表示从初始节点S0到节点x的代价: g( S0 0 )0 0 g( xj j )g( xi i ) c(xi i,xj j) 其中,其中,c(xi i,xj j)表示父节点xi到子节点xj的代价ADCEB464332323462344632C1B1D1D2E1
58、C2E2D3C3B2E4E36B32021-11-21人工智能722.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法(算法(4)对估价函数 f(x) g(x)h(x) 令其中的h(x)=0=0时,这时得到的是代价树代价树的非启发式搜索算法非启发式搜索算法。按对节点的考察范围不同,可分为两种搜索策略:n分支界限法分支界限法将全局择优搜索算法中的h(x)替换为g(x) ,即可得到分支界限搜索算法。n瞎子爬山法瞎子爬山法将局部择优搜索算法中的h(x)替换为g(x) ,即可得到瞎子爬山搜索算法。2021-11-21人工智能732021-11-21人工智能742.4.2 启发式搜索的启发式搜索的
59、A算法和算法和A*算法(算法(5)步步1 1 把附有把附有f( S0 0 )的初始节点的初始节点S0 0放入放入OPEN表中;表中;步步2 2 若若OPEN表为空,则搜索失败,退出;表为空,则搜索失败,退出;步步3 3 否则,移出否则,移出OPEN表中第一个节点表中第一个节点N放入放入CLOSED表中,并冠以顺序编号表中,并冠以顺序编号n;步步4 4 若目标节点若目标节点Sg gN,则搜索成功,利用,则搜索成功,利用CLOSED表表中的返回指针找出中的返回指针找出S0 0到到N的路径即为所求解,退出。的路径即为所求解,退出。步步5 5 若若N不可扩展,则转步不可扩展,则转步2 2;2.4.2
60、启发式搜索的启发式搜索的A算法和算法和A*算法(算法(6)步步6 6 否则,扩展否则,扩展N,生成一组子节点,生成一组子节点xi i,计算,计算f( xi i ) ,并对这组节点并对这组节点xi作如下处理:作如下处理: 1 1)若)若xi是是N的的先辈节点先辈节点,则,则删除删除之。之。 2 2)若)若xi存在于存在于OPEN或或CLOSED表中,也表中,也删除删除之,但表之,但表明此时存在两条初始节点明此时存在两条初始节点S0 0到到xi的路径;如果的路径;如果新路径新路径较较短短,则,则修改修改xi i节点的节点的返回指针返回指针(指向(指向N),并修改),并修改x xi i及及其后裔节点
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 河大版六年级上册语文期末复习卷含答案
- 化工离心分离工安全生产意识竞赛考核试卷含答案
- 制氢工岗前管理应用考核试卷含答案
- 胫腓骨骨折护理教学课件
- 紧固件镦锻工8S考核试卷含答案
- 燃气具安装工安全综合知识考核试卷含答案
- 工业炉及电炉装配工安全教育评优考核试卷含答案
- 作物制种工班组协作竞赛考核试卷含答案
- 镁电解工岗中实战考核试卷含答案
- 磷酸生产工安全演练能力考核试卷含答案
- 浙江省国际贸易集团有限公司行测笔试题目汇编2026
- 2025年公司主要负责人安全培训考试试题及答案(有一套)
- 2026事业单位笔试-福建-福建康复医学与技术(医疗招聘)历年参考题库含答案详解
- 2026年临床医师三基三严年度培训计划
- 2026年初级经济师经济基础真题试卷及答案解析
- 非典型溶血尿毒综合征(aHUS)专家共识解读(2025版)
- 重卡充电站施工总承包合同
- T∕TAF 074-2020 移动智能终端数字车钥匙信息安全技术要求
- 保安门岗管理制度
- 宪法知识教育主题班会-大学生专场
- 异舒吉(硝酸异山梨酯)治疗急性心梗并发急性心衰-病例分享
评论
0/150
提交评论