人工智能chapter5heuristic

DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring第五章启发式搜索启发式搜索和估价函数状态空间的启发式搜索A算法和A*算法与或树的启发式搜索博弈树搜索2DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring启发式搜索“启发”(heuristic)是关于发现和发明规则及方法的研究。在状态空间搜索中,启发式被定义成一系列规则,它从状态空间中选择最有希望到达问题解的路径。有信息的搜索策略——是一种在问题本身的定义之外还利用问题的特定知识的策略。3DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring启发性信息启发性信息的种类有效地帮助确定扩展节点的信息；有效的帮助决定哪些后继节点应被生成的信息；能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。启发性信息的作用启发信息的启发能力越强，扩展的无用结点越少。4DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring启发式搜索在两种情况下运用启发式策略:一个问题由于在问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断,视觉系统可运用启发式策策略选择最有可能解释。一个问题(如国际象棋)可能有确定解,但是求解过程中的计算机代价令人难以接受。穷尽式搜索策略,在一个给定的时空内很可能得不到最终的解。启发式策略通过指导搜索向最有希望的方向前进降低了复杂性。消除组合爆炸,并得到令人能接受的解。然而,启发式策略也是极易出错的。由于启发式搜索只有有限的信息,可能得到一个次最佳解,也可能一无所获。启发式策略及算法设计一直是AI的核心问题。ES视其为问题求解的重要部分。5DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring5.1启发式搜索和估价函数启发式策略及算法设计一直是人工智能的核心问题。博弈和定理证明是两个最古老的应用，二者都需要启发式知识来剪枝以减少状态空间。应用启发式减少搜索耗散。启发式算法通常由两部分组成：方法和使用该方法搜索状态空间的算法。6DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring例：一字棋游戏选择“最好优先”算法每种状态都标记了启发值简化了搜索过程7DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring启发式搜索和估价函数在智能活动中使用最多的不是具有完备性的算法，而是不一定完备的启发式方法。对问题空间进行搜索时，提高搜索效率需要有和解有关的大量控制性知识作为搜索的辅助性策略。控制信息反映在估价函数中。估价函数的任务就是估计待搜索结点的重要程度。()()()fngnhn从初始结点到n的实际代价从n到目标的最佳路径的估计代价8DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring5.2启发式搜索算法5.2.1局部择优搜索（瞎子爬山法HillClimbing)它由深度优先搜索法演变而来。搜索每到达一个结点后，其后继结点的选择不是预定的或盲目的，而是在它的所有子结点中，按估价函数f(x)选择最优者。犹如瞎子爬山一样，故名瞎子爬山法。在局部择优搜索法中，OPEN表可以取消，每次扩展后保留一个最优子结点N’，而将其他子结点全部丢掉。N’就是下一次扩展的结点，可直接放入CLOSED表中。9DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpringfunctionHill-Climbing(problem)returnastatethatisalocalmaximuminputs:problem,aproblemlocalvariables:current,anodeneighbor,anodeCurrent-MAKE-NODE(INITIAL-STATE[problem])loopdoneighborahighest-valuedsuccessorofcurrentIfVALUE[neighbor]=VALUE[current]thenreturnSTATE[current]currentneighbor爬山法搜索策略10DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring优点：方法简单、占用内存空间少，速度快，在多数情况下有效，主要是在单因素、单极值情况下使用。缺点：在多因素、多极值情况下会遇到许多困难，找不到最佳解。由于它只考虑了局部择优，有片面性，甚至会使搜索失败。局部择优搜索11DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring状态空间地形图目标函数状态空间全局最大值局部极大值爬山法经常会遇到以下问题：局部极大值山脊高原12DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring爬山法的变形随机爬山法首选爬山法随机重新开始爬山法13DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring5.2.2最好优先搜索法定义：Best-firstSearch(OrderedSearch)在AI图解搜索中，结点扩展的顺序是根据待扩展结点的评价函数值f(x)来决定，即将评价函数值最佳的结点最先扩展，搜索方法是靠f值指导搜索顺序的。14DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring估计函数(评价函数)f(x):估计函数的任务就是估计OPEN表中各结点的重要程度并给它们排定次序，估计函数f(x)可以是任意一种函数：有的定义它是结点X处于最佳路径上的概率。或者是结点X和目标结点之间的距离。或者是X格句的得分等等。一般来说，估计一个结点的价值，必须考虑两方面因素：已经付出的代价和将要付出的代价。我们把估计函数f(n)定义为从初始结点经过n结点到达目标结点的最小代价估计值。5.2.2最好优先搜索法15DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring一般形式为：f(n)=g(n)+h(n)其中：g(n)是从初始结点到n的实际代价；h(n)是从n到目标结点的估计代价。h(n)体现了搜索的启发信息。因为实际代价g(n)可以根据已生成的搜索树计算出来，而估计代h(n)有赖于某种经验估计，它来源于我们对问题的解的某些特性的认识，这些特性可以帮助我们更快的找到问题的解。如果h(n)=0，g(n)=d(n)时，就是广度优先搜索法。一般讲在f(n)中，g(n)的比重越大，越倾向于广度优先搜索；h(n)的比重越大，越倾向于深度优先搜索。有了f(n)，就可以对各个待扩展结点的价值进行估计，从OPEN表中选择出最有希望的结点扩展。5.2.2最好优先搜索法16DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring搜索的过程：有序搜索中的数据结构不同于广度优先搜索使用的队，也不同于深度优先搜索使用的栈，而是一个按结点的f值的大小为序排列的一个表，有时也称为“优先队”。进入优先队的结点不是简单地排在队末尾，而是根据其f值的大小插入队中合适的位置。每次从队中优先取出f值最小的结点加以扩展。5.2.2最好优先搜索法17DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring例：一个结点有多条通道的搜索树的有序搜索过程：(a)AJIHDCBEGF设g为已搜索的路程代价h为将要付出的估计代价初始结点目标结点h=3h=1h=0h=1h=2h=2h=2h=3h=3h=418DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring(c)(b)Ag=0h=3f=3g=1h=4f=5g=1h=2f=3g=1h=3f=4优先队：FBHFHBA设g为已搜索的路程代价h为将付出的估计代价算出f值对OPEN表重排序，5.2.2最好优先搜索法19DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring(d)g=1h=4f=5g=2h=1f=3g=1h=3f=4DHBA优先队：DBHF算出f值对OPEN表重排序，最好优先搜索法20DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpringg=1h=4f=5g=3h=0f=3g=1h=3f=4EHBADFGg=3h=1f=4目标结点(e)最好优先搜索法21DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring从上图可知，当搜索开始时，树根结点进入优先队中，因为队中只有一个结点，故无序可排。接着扩展树根，它有三个可能的通道，通向F、B、H三个结点。显然，这三个结点的g值皆为1。图中的h值虽标为精确值，实际上应为估算值。算出三个结点的f值分别为3、4和5。将这三个结点按f的大小送入优先队中。下一个要扩展的结点是队中f值最小的结点，即结点F。它只有一个后继结点D,其结点值f等于3，由于结点F已被充分扩展，故变为闭结点，而将f值最小的结点D插入队首，接着再扩展D，如此继续，直到出现目标结点E时为止。最好优先搜索法22DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring有序搜索方法的流程图启动把So放入OPEN表计算f(So)取OPEN头N放CLOSED中扩展N，用f(x)估值Ni,将{Ni}并入OPEN，按f(x)重排序NOPEN=NIL?N=SgN可扩展NY失败成功YYN23DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntell