人工智能 第三章 基本的问题求解方法

第三章基本的问题求解方法问题求解的过程：1）知识表示；2）针对问题，分析特征，选择合适的方法来求解（包括搜索和推理）方法：1）基于状态图方法-搜索；2）基于谓词逻辑方法-推理；3）基于结构化的知识表示方法来求解问题；本章介绍搜索技术搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。A.Newell和H·A·Simon-LT程序A·Newell和H·A·Simon-GPS(GeneralProblemSolver)R.Fikes和N.Nilsson-STRIPS(StanfordResearchInstituteProblemSolver)现在,搜索技术渗透在各种人工智能系统中,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博奕都广泛使用。搜索(search)路径状态序列搜索寻找从初始状态到目标状态的路径;S0Sg搜索的必要性AI为什么要研究search?问题没有直接的解法;解方程组;定理证明;需要探索地求解;搜索与检索的区别状态是否动态生成;检索:静态;在数据库中检索某人的纪录;搜索:动态生成;下棋几个问题目标状态是否确定?确定:定理证明,eight-puzzle不确定:求积分,下棋;确定目标的性质;问题的解:路径(解路径)/目标状态;需要路径:下棋不需要路径:电路设计需要/不需要:诊病约束条件目标状态不确定时,用来约束目标状态的性质;X+Y=4:非整数解/整数解几个问题(续1)多解性;X+Y=4:整数解最优解评价标准/判断准则;min(x*y)北京-上海:时间最短/费用最少最优解是否唯一?下棋搜索问题状态空间2375148612384765搜索不是检索2375148612384765难点2375148612384765启发式方法2375148612384765搜索方法的评价标准搜索问题是AI核心理论问题之一。一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：(1)搜索空间小;(2)解最佳。搜索分类搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。到目前为止,AI领域中已提出许多具体的搜索方法,概括起来有：(1)求任一解路的搜索策略回溯法；爬山法(HillClimbing)；宽度优先法(Breadth-first)；深度优先法(Depth-first)(2)求最佳解路的搜索策略大英博物馆法(BritishMuseum)；最佳图搜索法(A*)(3)求与或关系解图的搜索法一般与或图搜索法(AO*)；极小极大法(Minimax)剪枝法(Alpha-betaPruning)；启发式剪枝法(HeuristicPruning)TOPICS回溯策略（Backtracking）图搜索（GRAPHSEARCH）无信息搜索启发式搜索TOPIC1BacktrackingN1N0N2N3N4N5•回溯策略例：四皇后问题QQQQ()()Q((1,1))()QQ((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))QQQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))存在问题及解决办法问题和解决方法：深度问题对搜索深度加以限制死循环问题状态重复:A→B，B→C,C→A记录从初始状态到当前状态的路径TOPIC2GRAPHSEARCH图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。N5N1N0N2N3N4一些基本概念图：一个节点的集合。节点由弧连接起来。有向图：弧是一个节点指向另一个节点的图，称为有向图。后继/父亲：如果有一条弧从ni指向nj，则nj称为ni的后继，ni称为nj的父辈（父亲）；一些基本概念(续1)路径：如果存在一个节点序列（ni0，ni1，……，nik），nij是nij-1是的后继，j=1，……，k，则称这个序列是从节点ni0到节点nik的一条路径，长度为k。祖先/后裔：如果存在一条从ni到nj的路径，则称nj是ni的后裔，ni称为nj的祖先。树：每个节点最多只有一个父辈。没有父辈的节点称为根节点。没有后继的节点称为叶节点。一些基本概念(续2)节点深度：根节点深度=0其它节点深度=父节点深度+10123一些基本概念（续3）扩展一个节点生成出该节点的所有后继节点。弧的费用有一条弧连接ni和nj两个节点,用C(ni,nj)表示使用规则从ni到nj的费用(耗散值)。玉泉路---天安门路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。GRAPHSEARCH的思路OPEN表已经生成但未扩展节点CLOSED表已扩展节点扩展节点i生成节点j指针调整指针图搜索（GraphSearch）的一般过程1、建立一个只有起始节点S的搜索图G，把S放入一个叫open的未扩展节点表；2、建立已扩展节点表closed，初始为空；3、LOOP；若open为空，则失败退出；4、选open表中的第一个节点，设为n，移入closed表；5、若n为目标节点，则成功退出，该问题的解即是G中沿S指向n的路径；6、若不是目标节点，则扩展n，生成不是n的祖先的那些后继节点的集合m，把m的成员作为n的后继加入G中；7、对未曾在G中出现过的m成员，设一通向n的指针，把它们加入open表。对已在closed或open表上的m成员，确定是否要更改到n的指针方向，对已在closed上的m成员，确定是否要更改G中通向每个后裔节点的指针方向。8、按某一方式（深度优先、宽度优先、A*算法）重排open表9、GOLOOP例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}例：右图中黑节点表示已扩展，白节点表示未扩展，问题：先扩展6号节点生成m1={4，7}，然后扩展节点1，生成m2={2}，按算法第七步重新修改原图。612453难点！！！算法中第七步7扩展节点6生成m1={4，7}的调整61245371235467×再扩展节点1生成m2={2}的调整12354671235467××最终结果61245371235467图搜索与回溯算法的区别扩展节点:回溯算法:生成一个儿子节点.图搜索:扩展节点,生成所有儿子节点.候选节点:回溯算法:一个.图搜索:多个.回溯:回溯算法:返回父亲节点.图搜索:不一定返回父亲节点.TOPIC3无信息搜索如果在GRAPHSEARCH中，对节点的排序不使用与问题相关的信息，则称为无信息图搜索（盲目搜索）宽度优先和深度优先1、breadth-firstsearch宽度优先搜索：如果搜索是以接近起始节点的程度依次扩展节点的。搜索逐层进行；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。算法12345678910111213141516171819★21222324★26272829303112345678910111213141516171819★234567891011121314151617181912345678910123456789搜索演示★已扩展节点正在扩展节点扩展的子节点未扩展节点目标宽度优先法应用示例宽度优先法求九宫重排问题231847651238476523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。一定能找到解找到的解一定是最佳解(在每个路径消耗是同样的意义上)搜索的空间大、慢。分析深度优先搜索：首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。特点：扩展最深的节点,使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。算法：与宽度优先相似，不同在于：(5)把n的所有后继节点放到OPEN表的前端2、depth-firstsearch3456789101112131415161718192021★2324★26272829303112活结点表1121124224844816881616817881717884944918991818919919194425225105510209991010202010211010212110105115511★演示例九宫重排问题2831647■5初始状态1238■4765目标状态应用示例231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目标分析①不一定能找到解。②解不一定是最佳解。3、其他方法含有深度界限的深度优先搜索算法：基于代价树的搜索算法：TOPIC4heuristicsearch盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的