第3章-搜索问题

第三章搜索问题3.1状态空间搜索概述3.2回溯策略3.3图搜索策略3.4盲目的图搜索过程3.5启发式图搜索过程S0Sg问题全状态空间搜索空间解路径2解路径1图3-1搜索空间状态空间搜索是问题求解的主要方法之一。在人工智能中，问题求解的基本方法有搜索法、归约法、归结法、推理法等。•搜索法的主要任务：确定以何种方式选择规则？•求任一解路的搜索策略：backtracking、HillClimbing、Breadth-first、Depth-first、BeamSearch、Best-first(A).•求最佳解路的搜索策略：BritishMuseum、BranchandBound、DynamicProgramming、Optimalsearch(A*).•求与或图解图的搜索策略：AO*、Minimax、Alpha-betaPruning、HeuristicPruning.3.1状态空间搜索概述•3.1.1图的概念–图是节点及连接节点的弧的集合。–由方向性的弧连接的图是有向图。–节点深度的表示：根节点深度为0，其他节点深度dn+1=dn+1。–路径：N个有序节点组成的序列中，若每对相邻节点都表示一条弧，则称该序列为图中长度为N-1的一条路径。–路径耗散值：令C（ni，nj）为节点ni到节点nj这段路径（或弧线）的耗散值，一条路径的耗散值等于这条路径上所有弧线耗散值的总和。路径耗散值可按如下递归公式计算：C（ni，t）=C（ni，nj）+C（nj，t）–节点的扩展：操作符（规则）作用到节点（对应于某一状态描述）上，生成其所有后继节点（新状态），并给出弧线的耗散值（相当于使用规则的代价），这个过程叫做扩展一个节点。3.1.2问题状态空间的图描述图是最直观的描述问题状态空间的工具，属于显式描述。图中的节点表示问题的状态，图中的弧表示状态之间的关系。初始状态对应待求解问题的已知信息，是图的根节点。3.1.3问题状态空间的搜索•状态空间法将一个待定问题的求解过程定义为若干算子与搜索的有机结合体。–算子定义了对状态的操作，求解的目的在于找出从初始状态转换为某个（或某些）目标状态的一个（或一组）操作算子序列。–以上问题等价于在图中寻找从根节点到某个（或某些）目标节点的一条（或一组）路径。为提供对问题的形式描述，需要：1.定义状态空间，包含问题相关对象的各种可能排列。对空间的定义不必枚举所有状态。2.规定一个或多个属于该空间的初始状态。该状态用以描述问题求解过程开始时的状态。3.规定一个或多个属于该空间的目标状态。该状态用以判断是否得到了问题的解。4.规定一组规则。描述可使用的操作或算子。将待求解问题转换成状态空间描述后，使用控制策略对规则进行选择性的应用，在问题状态空间内进行搜索，直到找出从初始状态到目标状态的一条（或一组）路径。3.1.4搜索的基本概念状态空间图的搜索，是搜索满足条件的一个（或一组）操作算子序列的过程，这个过程也是将一个隐式图中包含目的节点的某个子图变为显式的过程。这种搜索过程是状态空间问题求解的主要基础。搜索过程面临的基本问题包括：1）终止搜索过程能否终止运行？或陷入死循环？2）有解搜索过程是否一定能找到一个解？3）最佳解搜索过程找到的解是否是最佳解？4）代价搜索过程的时间与空间复杂性如何？搜索过程的要点是：1)从初始或目的状态出发，并将它作为当前状态。2)扫描操作算子集合，将适用于当前状态的一些操作算子作用在其上得到新的状态，并建立新状态与父母节点的连接指针。3)检查生成的新状态是否是结束状态，如果是，则沿着有关指针从结束状态反向到达开始状态，给出一个解；否则，将新状态作为当前状态，返回第2)步继续搜索。3.1.5搜索的策略•搜索策略的任务是确定如何选取规则。–盲目搜索（无信息搜索）：不使用与特定问题有关的任何信息，按固定步骤（依次或随机调用操作算子）进行搜索；–启发式搜索（有信息搜索）：考虑特定问题领域相关知识，动态确定操作算子的调用，优先选取较合适的操作算子，尽量减少不必要的搜索，以求尽快到达结束状态，提高搜索效率。•盲目搜索中，由于没有可参考的信息，因此必须使用所有可匹配的操作算子，导致搜索出更多的状态，生成较大的状态空间显式图.•启发式搜索中，由于使用应用问题相关的启发信息，可匹配的操作算子中只有部分被使用，因此生成较小的状态空间显式图便可将搜索引向一个解答，但操作算子的选择需要更多的计算与判断。•启发式搜索一般要优于盲目搜索，但不可过于追求更多的甚至完整的启发信息，应综合考虑，尽量降低搜索系统的总开销。图3-2可说明这个问题。启发信息量系统开销被选中的操作算子的个数一个操作算子被选中的开销综合开销完整信息图3-2搜索系统的开销3.2回溯策略•回溯策略是一种尝试状态空间中各种不同路径的技术。•带回溯策略的搜索从初始状态出发，不停地、试探地寻找路径直到找到目标节点或“不可解节点”—“死胡同”。–找到目标节点，退出搜索，返回解路径。–遇到不可解节点时，回溯到路径中最近的父节点上，查看该节点是否还有其他子节点未被扩展，如有则沿这些子节点继续搜索。•可以看出，这种求解过程呈现出递归过程的性质。求解过程在每个节点上的检查遵循着递归方式。•递归法是回溯策略的一种最直接的实现方法。递归过程示例：阶乘函数的递归intfactorial(intn){if(n==1){return1;}else{returnn*factorial(n-1);}}只要初始值大于零，factorial函数就能够终止。停止的位置称为基线条件（basecase）。基线条件是递归程序的最底层位置，此位置没有必要再进行操作，直接返回一个结果。所有递归程序都必须至少拥有一个基线条件，而且必须确保它们最终会达到某个基线条件；否则,程序永远运行，直到缺少内存或者栈空间。递归过程伪码描述中用到的一些符号的含义：•变量：–DATA=当前状态；–RULES=规则集合序列表；–R=当前调用规则；–RDATA=新生成的状态；–PATH=当前解路径表。•常量：–NIL=空表；–FAIL=回溯点标记；–LOOP=循环标号。•谓词：–TERM(DATA)；(DATA满足结束条件)–DEADEND(DATA)；(DATA是非法状态)–NULL(RULES)。(规则集合序列表空)•函数：–RETURN返回自变量的值；–APPRULES求可应用的规则表；–FIRST从表中取表头的一个元素；–TAIL除去表头的一个元素后得到新表；–GEN调用规则生成新状态；–CONS在表头插入新元素，构造新表；–BACKTRACK(RDATA)递归过程作用于新状态。递归过程BACKTRACK(DATA)1.ifTERM(DATA),returnNIL；//当DATA满足终止条件时，返回空表.2.ifDEADEND(DATA),renturnFAIL；//当DATA状态不合法时，必须回溯。3.RULES←APPRULES(DATA)//DATA状态的可用规则加入规则集合序列表。4.LOOP:ifNULL(RULES),returnFAIL；//如果规则集合序列表空，必须回溯。5.R←FIRST(RULES)；//读规则集合序列表的第一条规则到变量R。6.RULES←TAIL(RULES)；//从规则集合序列表删除被选中的规则。7.RDATA←GEN（R，DATA）；//被选中的规则作用于当前状态。8.PATH←BACKTRACK(RDATA)；//对新状态递归调用本过程9.ifPATH=FAIL,goLOOP；//如果递归失败，则用另一条规则10.returnCONS(R,PATH)；//否则把R加在解路径表中，向上传递成功的规则表，过程返回解路径规则表（或局部解路径子表）举例综合数据库：DATA=L(表)，L的元素用{ij}表示，i，j的值域为{1，2，3，4}。即L的元素表示棋子所在的行和列。图3-3中的状态ae分别记为（12243143）、（13213442）、（1121）、（1122）、（112331）。QQQQQQQQQQQQQQQabcde四皇后问题：在一个4*4的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不能相互俘获。图3-3棋盘的几种状态共16条规则，规则Rij表示满足前提条件下，在ij处放一个棋子。当规则序列以R11、R12、R13、R14、R21、…、R44这种固定排序方式调用BACKTRACK时，四皇后问题的搜索如图3-4所示，共回溯22次，过程结束时返回规则表（R12、R24、R31、R43）。规则集：ijRif1i4andlengthDATAi1thenAPPENDDATAij1j4：()Q(11)R11(*,21)R21Q①(*,22)Q②(*,23)Q(*,*,31)Q③(*,*,32)Q④(*,*,33)Q⑤(*,*,34)Q⑥⑦(*,24)Q(*,*,31)⑧(*,*,32)(*,*,*,41)Q⑨(*,*,*,42)Q⑩(*,*,*,43)Q⑾(*,*,*,44)Q⑿⒀(*,*,*,33)⒁(*,*,*,34)⒂⒃⒄(12)Q(*,21)⒅(*,22)⒆(*,23)⒇(*,24)(12,24,31)(*,*,*,41)(21)(*,*,*,42)(22)(12,24,31,43)(11,23,31)()(11)(11,24)(11,23)(11,22)(11,21)(*,*,31)(12)(12,24)(12,23)(12,22)(12,21)(12,24,31)R12R24R31R43(11,23,32)(11,23,33)(11,23,34)(*,*,32)(*,*,33)(*,*,34)(*,*,*,41)(*,*,*,42)(*,*,*,43)(*,*,*,44)(*,*,*,41)(*,*,*,42)(*,*,*,43)图3-4四皇后问题的固定排序搜索树作业1：•当规则序列以R11、R21、R31、R41、R12、R22、R32、…、R44这种固定排序方式调用BACKTRACK函数时，画出四皇后问题的搜索树，并标出所有回溯的先后顺序。规则集ijRif1j4andlengthDATAj1thenAPPENDDATAij1i4：利用问题相关信息对规则进行动态排序，可提高搜索效率。定义对角线函数Maxdiag(i,j)，计算ij单元格所在对角线的最大长度，通过比较Maxdiag(i,j)函数值决定Rij的排序。如果Maxdiag(i,k)Maxdiag(i,j)，则Rik优先于Rij，即对角线短的单元相应的规则排在前头，若相同，则维持原顺序。按此知识排列的规则序列为R12、R13、R11、R14、R21、R24、R22、R23、R31、R34、R32、R33、R42、R43、R41、R44。此时的搜索过程如图3-5所示，回溯2次即可找到目标。()(12)R12(12,21)R21①QQ(12,24)R24(12,24,31)(12,24,31,42)(12,24,31,43)②R31R42R43QQQQ图3-5四皇后问题的动态排序搜索树顺序:R12、R13、R11、R14、R21、R24、R22、R23、R31、R34、R32、R33、R42、R43、R41、R44对于可能出现重复状态且搜索深度无限的问题，必须设置深度范围限制及防止出现重复状态引起死循环这两个回溯点。改进的算法如下BACKTRACK1(DATALIST):•[1]DATAFIRST(DATALIST)•[2]ifMEMBER(DATA,TAIL(DATALIST)),returnFAIL//有环路，回溯•[3]ifTERM(DATA),returnNIL//到达目标，成功返回•[4]ifDEADEND(DATA),returnFAIL//到达不合理状态，回溯•[5]ifLENGTH(DATALIST)BOUND,returnFAIL//已到深度限制，回溯•[6]RUL