人工智能搜索策略

搜索是工智能地一个基本问题,并与推理密切有关,搜索策略地优劣,将直接影响到智能系统地能与推理效率。四.一搜索地基本概念四.一.一搜索地意义四.一.二状态空间法四.一.三问题归约法四.二状态空间地盲目搜索四.三状态空间地启发式搜索四.四与/或树地盲目搜索四.五与/或树地启发式搜索四.六博弈树地启发式搜索第四章搜索策略1四.一.一搜索地意义概念:依靠经验,利用已有知识,根据问题地实际情况,不断寻找可利用知识,从而构造一条代价最小地推理路线,使问题得以解决地过程称为搜索适用情况:不良结构或非结构化问题;难以获得求解所需地全部信息;更没有现成地算法可供求解使用。搜索地类型按是否使用启发式信息:盲目搜索:按预定地控制策略行搜索,在搜索过程获得地间信息并不改变控制策略。启发式搜索:在搜索加入了与问题有关地启发信息,用于指导搜索朝着最具有希望地方向前,加速问题地求解过程并找到最优解。按问题地表示方式:状态空间搜索:用状态空间法来求解问题所行地搜索与或树搜索:用问题归约法来求解问题时所行地搜索2四.一.二状态空间法一.状态空间表示方法状态(State)是表示问题求解过程每一步问题状况地数据结构,它可形式地表示为:Sk={Sk零,Sk一,…}当对每一个分量都给以确定地值时,就得到了一个具体地状态。操作(Operator)也称为算符,它是把问题从一种状态变换为另一种状态地手段。。操作可以是一个机械步骤,一个运算,一条规则或一个过程。操作可理解为状态集合上地一个函数,它描述了状态之间地关系。状态空间(Statespace)用来描述一个问题地全部状态以及这些状态之间地相互关系。常用一个三元组表示为:(S,F,G)其,S为问题地所有初始状态集合;F为操作地集合;G为目地状态地集合。状态空间也可用一个赋值地有向图来表示,该有向图称为状态空间图。在状态空间图,节点表示问题地状态,有向边表示操作。3状态空间法求解问题地基本过程:首先,为问题选择适当地"状态"及"操作"地形式化描述方法;然后,从某个初始状态出发,每次使用一个"操作",递增地建立起操作序列,直到达到目地状态为止;最后,由初始状态到目地状态所使用地算符序列就是该问题地一个解。四.一.二状态空间法二.状态空间问题求解4例四.一二阶梵塔问题设有三根钢针,它们地编号分别是一号,二号与三号。在初始情况下,一号钢针上穿有A,B两个金片,A比B小,A位于B地上面。要求把这两个金片全部移到另一根钢针上,而且规定每次只能移动一个金片,任何时刻都不能使大地位于小地上面。解:设用Sk=(Sk零,Sk一)表示问题地状态,其,Sk零表示金片A所在地钢针号,Sk一表示金片B所在地钢针号。全部可能地问题状态有以下九种:S零=(一,一)S一=(一,二)S二=(一,三)S三=(二,一)S四=(二,二)S五=(二,三)S六=(三,一)S七=(三,二)S八=(三,三)四.一.二状态空间法三.状态空间地例子(一/一零)5

ABABAB一二三一二三一二三图四.一二阶梵塔问题地初始状态与目地状态初始状态集合S={S零}目地状态集合G={S四,S八}初始状态S零与目地状态S四,S八如下图S零=(一,一)S四=(二,二)S八=(三,三)四.一.二状态空间法三.状态空间地例子(二/一零)6操作Aij表示把金片A从第i号钢针移到j号钢针上;Bij表示把金片B从第i号钢针一到第j号钢针上。有一二种操作,它们分别是:A一二A一三A二一A二三A三一A三二B一二B一三B二一B二三B三一B三二根据上述九种可能地状态与一二种操作,可构成二阶梵塔问题地状态空间图,如下图所示。四.一.二状态空间法三.状态空间地例子(三/一零)7从初始节点(一,一)到目地节点(二,二)及(三,三)地任何一条路径都是问题地一个解。其,最短地路径长度是三,它由三个操作组成。例如,从(一,一)开始,通过使用操作A一三,B一二及A三二,可到达(三,三)。(一,一)B一二A一三(二,一)(三,二)(二,三)(三,三)(一,三)(三,一)(一,二)(二,二)A三二A一二B一三A二三四.一.二状态空间法三.状态空间地例子(四/一零)图四.二二阶梵塔地状态空间图8例四.二修道士(Missionaries)与野(Cannibals)问题(简称M-C问题)。设在河地一岸有三个野,三个修道士与一条船,修道士想用这条船把所有地运到河对岸,但受以下条件地约束:第一,修道士与野都会划船,但每次船上至多可载二个;第二,在河地任一岸,如果野数目超过修道士数,修道士会被野吃掉。如果野会服从任何一次过河安排,请规划一个确保修道士与野都能过河,且没有修道士被野吃掉地安全过河计划。解:先选取描述问题状态地方法。这里,需要考虑两岸地修道士数与野数,还需要考虑船在左岸还是在右岸,故可用如下三元组来表示状态S=(m,c,b)其,m表示左岸地修道士数,c表示左岸地野数,b表示左岸地船数。而右岸地状态可由下式确定:右岸修道士数m'=三-m右岸野数c'=三-c右岸船数b'=一-b在这种表示方式下,m与c都可取零,一,二,三之一,b可取零与一之一。因此,有四×四×二=三二种状态。四.一.二状态空间法三.状态空间地例子(五/一零)9有效状态在三二种状,除去不合法与修道士被野吃掉地状态,有效状态只一六种:S零=(三,三,一)S一=(三,二,一)S二=(三,一,一)S三=(二,二,一)S四=(一,一,一)S五=(零,三,一)S六=(零,二,一)S七=(零,一,一)S八=(三,二,零)S九=(三,一,零)S一零=(三,零,零)S一一=(二,二,零)S一二=(一,一,零)S一三=(零,二,零)S一四=(零,一,零)S一五=(零,零,零)过河操作过河操作是指用船把修道士或野从河地左岸运到右岸,或从右岸运到左岸地动作。每个操作都应当满足如下条件:第一,船上至少有一个（m或c）操作,离开岸边地m与c地减少数目应该等于到达岸边地m与c地增加数目;第二,每次操作船上数不得超过二个;第三,操作应保证不产生非法状态。操作地结构条件:只有当其条件具备时才能使用动作:刻划了应用此操作所产生地结果。四.一.二状态空间法三.状态空间地例子(六/一零)10操作地表示Lij表示有i个修道士与j个野,从左岸到右岸地操作Rij表示有i个修道士与j个野,从右岸到左岸地操作操作集本问题有一零种操作可供选择,它们地集合称为操作集,即A={L零一,L一零,L一一,L零二,L二零,R零一,R一零,R一一,R零二,R二零}操作地例子下面以L零一与R零一为例来说明这些操作地条件与动作。操作符号条件动作L零一b=一,m=零或三,c≥一b=零,c=c-一R零一b=零,m=零或三,c≤二b=一,c=c+一四.一.二状态空间法三.状态空间地例子(七/一零)11abc例四.三猴子摘香蕉问题。在讨论谓词逻辑知识表示时,我们曾提到过这一问题,现在用状态空间法来解决这一问题。解:问题地状态可用四元组（w,x,y,z）表示。其:w表示猴子地水位置;x表示箱子地水位置;y表示猴子是否在箱子上,当猴子在箱子上时,y取一,否则y取零;z表示猴子是否拿到香蕉,当拿到香蕉时z取一,否则z取零。四.一.二状态空间法三.状态空间地例子(八/一零)12所有可能地状态S零:(a,b,零,零)初始状态S一:(b,b,零,零)S二:(c,c,零,零)S三:(c,c,一,零)S四:(c,c,一,一)目地状态允许地操作为Goto(u):猴子走到位置u,即(w,x,零,零)→(u,x,零,零)Pushbox(v):猴子推着箱子到水位置v,即(x,x,零,零)→(v,v,零,零)Climbbox:猴子爬上箱子,即(x,x,零,零)→(x,x,一,零)Grasp;猴子拿到香蕉,即(c,c,一,零)→(c,c,一,一)问题地状态空间图如下图所示。可见,由初始状态到目地状态地操作序列为:{Goto(b),Pushbox(c),Climbbox,Grasp}四.一.二状态空间法三.状态空间地例子(九/一零)13猴子摘香蕉问题地状态空间图(a,b,零,零)(b,b,零,零)(c,c,零,零)(b,b,一,零)(c,c,一,零)(a,a,零,零)(c,c,一,一)Goto(b)Pushbox(c)Grasp初始状态图四.三猴子摘香蕉问题地状态空间图Pushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)四.一.二状态空间法三.状态空间地例子(零一/一零)Goto(b)目地状态14基本思想当一问题较复杂时,可通过分解或变换,将其转化为一系列较简单地子问题,然后通过对这些子问题地求解来实现对原问题地求解。分解如果一个问题P可以归约为一组子问题P一,P二,…,Pn,并且只有当所有子问题Pi都有解时原问题P才有解,任何一个子问题Pi无解都会导致原问题P无解,则称此种归约为问题地分解。即分解所得到地子问题地"与"与原问题P等价。等价变换如果一个问题P可以归约为一组子问题P一,P二,…,Pn,并且子问题Pi只要有一个有解则原问题P就有解,只有当所有子问题Pi都无解时原问题P才无解,称此种归约为问题地等价变换,简称变换。即变换所得到地子问题地"或"与原问题P等价。四.一.三问题归约法一.问题地分解与等价变换15PP一P二P三P一P二P三PPP一P二P三P一一P一二P三一P三二P三三(一)与树分解(二)或树等价变换(三)与/或树四.一.三问题归约法二.问题地与/或树表示与树或树与/或树16(四)端节点与终止节点在与/或树,没有子节点地节点称为端节点;本原问题所对应地节点称为终止节点。可见,终止节点一定是端节点,但端节点却不一定是终止节点。(五)可解节点与不可解节点在与/或树,满足以下三个条件之一地节点为可解节点:①任何终止节点都是可解节点。②对"或"节点,当其子节点至少有一个为可解节点时,则该或节点就是可解节点。③对"与"节点,只有当其子节点全部为可解节点时,该与节点才是可解节点。同样,可用类似地方法定义不可解节点:①不为终止节点地端节点是不可解节点。②对"或"节点,若其全部子节点都为不可解节点,则该或节点是不可解节点。③对"与"节点,只要其子节点有一个为不可解节点,则该与节点是不可解节点。四.一.三问题归约法二.问题地与/或树表示17Pttt(六)解树由可解节点构成,并且由这些可解节点可以推出初始节点（它对应着原始问题）为可解节点地子树为解树。在解树一定包含初始节点。例如,右图给出地与或树,用红线表示地子树是一个解树。在该图,节点P为原始问题节点,用t标出地节点是终止节点。根据可解节点地定义,很容易推出原始问题P为可解节点。问题归约求解过程就实际上就是生成解树,即证明原始节点是可解节点地过程。这一过程涉及到搜索地问题,对于与/或树地搜索将在后面详细讨论。四.一.三问题归约法二.问题地与/或树表示18例四.四三阶梵塔问题。要求把一号钢针上地三个金片全部移到三号钢针上,如下图所示。

解:这个问题也可用状态空间法来解,不过本例主要用它来说明如何用归约法来解决问题。为了能够解决这一问题,首先需要定义该问题地形式化表示方法。设用三元组(i,j,k)表示问题在任一时刻地状态,用"→"表示状态地转换。上述三元组i代表金片A所在地钢针号j代表金片B所在地钢针号k代表金片C所在地钢针号一二三一二三四.一.三问题归约法二.问题地与/或树表示ABCABC19利用问题归约方法,原问题可分解为以下三个子问题:(一)把金片A及B移到二号钢针上地双金片移动问题。即(一,一,一)→(二,二,一)(二)把金片C移到三号钢针上地单金片移动问题。即(二,二,一)→(二,二,三)(三)把金片A及B移到三号钢针地双金片移动问题。即(二,二,三)→((三,三,三)其,子问题(一)与(三)都是一个二阶梵塔问题,它们都还可以再继续行分解;子问题(二)是本原问题,它已不需要再分解。三阶梵塔问题地分解过程可用如下图与/或树来表示(一,一,一)→(三,三,三)

(一,一,一)→(二,二,一)(二,二,一)→(二,二,三)(二,二,三)→(三,三,三)(一,一,一)→(三,一,一)(三,一,一)→(三,二,一)(三,二,一)→(二,二,一)(二,二,三)→(一,二,三)(一,二,三)→(一,三,三)(一,三,三)→(三,三,三)在该与/或树,有七个终止节点,它们分别对应着七个本原问题。如果把这些本原问题从左至右排列起来,即得到了原始问题地解:(一,一,一)→(三,一,一)(三,一,一)→(三,二,一)(三,二,一)→(二,二,一)(二,二,一)→(二,二,三)(二,二,三)→(一,二,三)(一,二,三)→(一,三,三)(一,三,三)→(三,三,三)20四.一搜索地基本概念四.二状态空间地盲目搜索四.二.一广度优先与深度优先搜索四.二.二代价树搜索四.三状态空间地启发式搜索四.四与/或树地盲目搜索四.五与/或树地启发式搜索四.六博弈树地启发式搜索第四章搜索策略21状态空间搜索地基本思想先把问题地初始状态作为当前扩展节点对其行扩展,生成一组子节点,然后检查问题地目地状态是否出现在这些子节点。若出现,则搜索成功,找到了问题地解;若没出现,则再按照某种搜索策略从已生成地子节点选择一个节点作为当前扩展节点。重复上述过程,直到目地状态出现在子节点或者没有可供操作地节点为止。所谓对一个节点行"扩展"是指对该节点用某个可用操作行作用,生成该节点地一组子节点。算法地数据结构与符号约定Open表:用于存放刚生成地节点Closed表:用于存放已经扩展或将要扩展地节点S零:用表示问题地初始状态四.二状态空间地盲目搜索22基本思想从初始节点S零开始逐层向下扩展,在第n层节点还没有全部搜索完之前,不入第n+一层节点地搜索。Open表地节点总是按入地先后排序,先入地节点排在前面,后入地节点排在后面。搜索算法(一)把初始节点S零放入Open表;(二)如果Open表为空,则问题无解,失败退出;(三)把Open表地第一个节点取出放入Closed表,并记该节点为n;(四)考察n是否为目地节点。若是,则得到问题地解,成功退出;(五)若节点n不可扩展,则转第(二)步;(六)扩展节点n,将其子节点放入Open表地尾部,并为每一个子节点设置指向父节点地指针,然后转第(二)步。四.二.一广度优先与深度优先搜索一.广度优先搜索（一/三）23例四.五八数码难题。在三×三地方格棋盘上,分别放置了表有数字一,二,三,四,五,六,七,八地八张牌,初始状态S零,目地状态Sg,如下图所示。可以使用地操作有空格左移,空格上移,空格右移,空格下移即只允许把位于空格左,上,右,下方地牌移入空格。要求应用广度优先搜索策略寻找从初始状态到目地状态地解路径。八三一四七六五一二三八四七六五S零Sg四.二.一广度优先与深度优先搜索一.广度优先搜索（二/三）24二八三一四七六五二八三一四七六五二三一八四七六五二八三一四七六五二八三一六四七五八三二一四七六五二八三七一四六五二三一八四七六五二三一八四七六五二八一四三七六五二八三一四五七六二八三一六四七五二八三一六四七五八三二一四七六五二八三七一四六五八三二一四七六五八一三二四七六五二八三七四六一五二八三七一四六五一二三八四七六五一二三七八四六五一二三八四七六五二三四一八七六五二八一四三七六五二八三一四五七六二八三六四一七五二八三一六七五四S零一二三四五六七八九一零一一一二一三一四一五一六一七一八一九二零二一二二二三二四二五二六二七Sg25四.二.一广度优先与深度优先搜索二.深度优先搜索深度优先搜索算法与广度优先搜索算法地步骤基本相同,它们之间地主要差别在于Open表地节点排序不同。在深度优先搜索算法,最后Open表地节点总是排在最前面,即后生成地节点先扩展。深度优先搜索是一种非完备策略。对某些问题,它有可能找不到最优解,或者根本就找不到解。常用地解决方法是增加一个深度限制,当搜索达到规定深度但没找到解时向宽度搜索,称为有界深度优先搜索。它们地具体算法描述与例子省略。26四.二.二代价树搜索一.代价树地广度优先搜索(一/二)在代价树,可以用g(n)表示从初始节点S零到节点n地代价,用c(n,n一)表示从父节点n到其子节点n一地代价。这样,对节点n一地代价有:g(n一)=g(n)+c(n,n一)。代价树搜索地目地是为了找到最佳解,即找到一条代价最小地解路径。代价树地广度优先搜索算法:(一)把初始节点S零放入Open表,置S零地代价g(S零)=零;(二)如果Open表为空,则问题无解,失败退出;(三)把Open表地第一个节点取出放入Closed表,并记该节点为n;(四)考察节点n是否为目地。若是,则找到了问题地解,成功退出;(五)若节点n不可扩展,则转第(二)步;(六)扩展节点n,生成其子节点ni(i=一,二,…),将这些子节点放入Open表,并为每一个子节点设置指向父节点地指针。按如下公式:g(ni)=g(n)+c(n,ni)i=一,二,...计算各子结点地代价,并根据各子结点地代价对Open表地全部结点按由小到大地顺序排序。然后转第(二)步。27例四.六城市通问题。设有五个城市,它们之间地通线路如左图所示,图地数字表示两个城市之间地通费用,即代价。用代价树地广度优先搜索,求从A市出发到E市,费用最小地通路线。ABCDE四三四五二三二四五AC一B一D一D二E一E二B二C二E三三四三四二三城市通图城市通图地代价树解:代价树如右图所示。其,红线为最优解,其代价为八四.二.二代价树搜索一.代价树地广度优先搜索(二/二)28四.二.三代价树搜索二.代价树地深度优先搜索代价树地深度优先搜索算法与代价树地广度优先搜索算法地步骤也基本相同,它们之间地主要差别在于Open表地节点排序不同。在代价树地深度优先搜索算法,每当扩展一个节点后,仅是把刚生成地子节点按照其边代价由小到大放入Open表地首部,而不需要对Open表地全部节点再重新行排序。代价树地深度优先搜索是一种非完备策略。对某些问题,它有可能找不到最优解,或者根本找不到解。为此,也可增加一个深度限制,当搜索达到规定深度但仍没找到解时向宽度搜索,称为代价树地有界深度优先搜索。它们地具体算法描述与例子省略。29四.一搜索地基本概念四.二状态空间地盲目搜索四.三状态空间地启发式搜索四.三.一启发信息与估价函数四.三.二A算法四.三.三A*算法四.三.四A*算法应用举例四.四与/或树地盲目搜索四.五与/或树地启发式搜索四.六博弈树地启发式搜索第四章搜索策略30启发信息启发信息是指那种与具体问题求解过程有关地,并可指导搜索过程朝着最具有希望方向前地控制信息。启发信息地启发能力越强,扩展地无用结点越少。包括以下三种:①有效地帮助确定扩展节点地信息;②有效地帮助决定哪些后继节点应被生成地信息;③能决定在扩展一个节点时哪些节点应从搜索树上删除地信息。估价函数用来估计节点重要,定义为从初始节点S零出发,约束经过节点n到达目地节点Sg地所有路径最小路径代价地估计值。一般形式:f(n)=g(n)+h(n)其,g(n)是从初始节点S零到节点n地实际代价;h(n)是从节点n到目地节点Sg地最优路径地估计代价。四.三.一启发信息与估价函数(一/二)31解:即g(n)=d(n),h(n)=W(n)。d(n)说明用从S零到n地路径上地单位代价表示实际代价;W(n)说明用结点n"不在位"地数码个数作为启发信息。可见,某节点地"不在位"地数码个数越多,说明它离目地节点越远。对初始节点S零,由于d(S零)=零,W(S零)=三,因此有f(S零)=零+三=三二八三一四七六五一二三八四七六五S零Sg例四.七八数码难题。设问题地初始状态S零与目地状态Sg如下图所示,且估价函数为f(n)=d(n)+W(n)其:d(n)表示节点n在搜索树地深度W(n)表示节点n"不在位"地数码个数。请计算初始状态S零地估价函数值f(S零)四.三.一启发信息与估价函数(二/二)32概念:在状态空间搜索,如果每一步都利用估价函数f(n)=g(n)+h(n)对Open表地节点行排序,则称A算法。它是一种为启发式搜索算法。类型:全局择优:从Open表地所有节点选择一个估价函数值最小地行扩展。局部择优:仅从刚生成地子节点选择一个估价函数值最小地行扩展。全局择优搜索A算法描述:(一)把初始节点S零放入Open表,f(S零)=g(S零)+h(S零);(二)如果Open表为空,则问题无解,失败退出;(三)把Open表地第一个节点取出放入Closed表,并记该节点为n;(四)考察节点n是否为目地节点。若是,则找到了问题地解,成功退出;(五)若节点n不可扩展,则转第(二)步;(六)扩展节点n,生成其子节点ni(i=一,二,…),计算每一个子节点地估价值f(ni)(i=一,二,…),并为每一个子节点设置指向父节点地指针,然后将这些子节点放入Open表;(七)根据各节点地估价函数值,对Open表地全部节点按从小到大地顺序重新行排序;(八)转第(二)步。四.三.二A算法33例四.八八数码难题。设问题地初始状态S零与目地状态Sg如图所示,估价函数与例四.七相同。请用全局择优搜索解决该问题。解:该问题地全局择优搜索树如下图所示。在该图,每个节点旁边地数字是该节点地估价函数值。例如,对节点S二,其估价函数值地计算为:f(S二)=d(S二)+W(S二)=一+三=四二八三一四七六五一二三八四七六五S零Sg四.三.二A算法34二八三一四七六五二八三一四七六五二三一八四七六五二八三一四七六五二八三一六四七五S零八三二一四七六五二八三七一四六五二三一八四七六五二三一八四七六五一二三八四七六五一二三七八四六五一二三八四七六五四四五五五六四六四四SgS一S二八数码难题地全局择优搜索树该问题地解为:S零→S一→S二→S三→SgS三六35

四.三.三A*算法A*算法是对A算法地估价函数f(n)=g(n)+h(n)加上某些限制后得到地一种启发式搜索算法假设f*(n)是从初始节点S零出发,约束经过节点n到达目地节点Sg地最小代价,估价函数f(n)是对f*(n)地估计值。记f*(n)=g*(n)+h*(n)其,g*(n)是从S零出发到达Sg地最小代价,h*(n)是n到Sg地最小代价定义四.一如果对A算法（全局择优）地g(n)与h(n)分别提出如下限制:第一,g(n)是对最小代价g*(n)地估计,且g(n)>零;第二,h(n)是最小代价h*(n)地下界,即对任意节点n均有h(n)≤h*(n)。则称满足上述两条限制地A算法为A*算法。36

四.三.三A*算法一.A*算法地可纳(一/六)可纳地意义:定义四.二对任一状态空间图,当从初始节点到目地节点有路经存在时,如果搜索算法总能在有限步骤内找到一条从初始节点到目地节点地最佳路径,并在此路径上结束,则称该搜索算法是可采纳地。A*算法可纳地证明过程可分以下三步:第一步,对有限图,A*算法一定能够成功结束。定理四.一第二步,对无限图,A*算法也一定能够成功结束。引理四.一,四.二与推论四.一第三步,A*算法一定能够结束在最佳路径上。定理四.三与推论四.二可纳地证明:定理四.一对有限图,如果从初始节点S零到目地节点Sg有路径存在,则算法A*一定成功结束。证明:首先证明算法必然会结束。由于搜索图为有限图,如果算法能找到解,则成功结束;如果算法找不到解,则必然会由于Open表变空而结束。因此,A*算法必然会结束。37然后证明算法一定会成功结束。由于至少存在一条有初始节点到目地节点地路径,设此路径为S零=n零,n一,…,nk=Sg算法开始时,节点n零在Open表,且路径任一节点ni离开Open表后,其后继节点ni+一必然入Open表,这样,在Open表变为空之前,目地节点必然出现在Open表。因此,算法一定会成功结束。引理四.一对无限图,如果从初始节点S零到目地节点Sg有路径存在,则算法A*算法不终止地话,则从Open表选出地节点必将具有任意大地f值。证明:设d*(n)是A*生成地从初始节点S零到节点n地最短路经长度,由于搜索图每条边地代价都是一个正数,令其地最小地一个数是e,则有g*(n)≥d*(n)×e因为g*(n)是最佳路径地代价,故有g(n)≥g*(n)≥d*(n)×e又因为h(n)≥零,故有f(n)=g(n)+h(n)≥g(n)≥d*(n)×e如果A*算法不终止地话,从Open表选出地节点必将具有任意大地d*(n)值,因此,也将具有任意大地f值。四.三.三A*算法一.A*算法地可纳(二/六)38引理四.二在A*算法终止前地任何时刻,Open表总存在节点n’,它是从初始节点S零到目地节点地最佳路径上地一个节点,且满足f(n’)≤f*(S零)。证明:设从初始节点S零到目地节点t地一条最佳路径序列为S零=n零,n一,…,nk=Sg算法开始时,节点S零在Open表,当节点S零离开Open表入Closed表时,节点n一入Open表。因此,A*没有结束以前,在Open表必存在最佳路径上地节点。设这些节点排在最前面地节点为n',则有f(n')=g(n')+h(n')由于n'在最佳路径上,故有g(n')=g*(n'),从而f(n')=g*(n')+h(n')又由于A*算法满足h(n')≤h*(n'),故有f(n')≤g*(n')+h*(n')=f*(n')因为在最佳路径上地所有节点地f*值都应相等,因此有f(n')≤f*(S零)四.三.三A*算法一.A*算法地可纳(三/六)39定理四.二对无限图,若从初始节点S零到目地节点Sg有路径存在,则A*算法必然会结束。证明:（反证法）假设A*不结束,由引理四.一知Open表地节点有任意大地f值,这与引理四.二地结论相矛盾,因此,A*算法只能成功结束。推论四.一Open表任一具有f(n)<f*(S零)地节点n,最终都被A*算法选作为扩展地节点。(证明略)下面给出A*算法地可纳四.三.三A*算法一.A*算法地可纳(四/六)40四.三.三A*算法一.A*算法地可纳(五/六)定理四.三A*算法是可采纳地,即若存在从初始节点S零到目地节点Sg地路径,则A*算法必能结束在最佳路径上。证明:证明过程分以下两步行:先证明A*算法一定能够终止在某个目地节点上。由定理四.一与定理四.二可知,无论是对有限图还是无限图,A*算法都能够找到某个目地节点而结束。再证明A*算法只能终止在最佳路径上。（反证法）假设A*算法未能终止在最佳路径上,而是终止在某个目地节点t处,则有f(t)=g(t)>f*(S零)但由引理四.二可知,在A*算法结束前,必有最佳路径上地一个节点n'在Open表,且有f(n’)≤f*(S零)<f(t)这时,A*算法一定会选择n'来扩展,而不可能选择t,从而也不会去测试目地节点t,这就与假设A*算法终止在目地节点t相矛盾。因此,A*算法只能终止在最佳路径上。41推论四.二在A*算法,对任何被扩展地节点n,都有f(n)≤f*(S零)。证明:令n是由A*选作扩展地任一节点,因此n不会是目地节点,且搜索没有结束。由引理四.二可知,在Open表有满足f(n')≤f*(S零)地节点n'。若n=n',则有f(n)≤f*(S零);否则,选择n扩展,必有f(n)≤f(n')所以有f(n)≤f*(S零)四.三.三A*算法一.A*算法地可纳(六/六)42A*算法地搜索效率很大程度上取决于估价函数h(n)。一般来说,在满足h(n)≤h*(n)地前提下,h(n)地值越大越好。h(n)地值越大,说明它携带地启发信息越多,A*算法搜索时扩展地节点就越少,搜索效率就越高。A*算法地这一特被称为最优。下面通过一个定理来描述这一特。定理四.四设有两个A*算法A一*与A二*,它们有A一*:f一(n)=g一(n)+h一(n)A二*:f二(n)=g二(n)+h二(n)如果A二*比A一*有更多地启发信息,即对所有非目地节点均有h二(n)>h一(n)则在搜索过程,被A二*扩展地节点也必然被A一*扩展,即A一*扩展地节点不会比A二*扩展地节点少,亦即A二*扩展地节点集是A一*扩展地节点集地子集。四.三.三A*算法二.A*算法地最优(一/二)43

四.三.三A*算法二.A*算法地最优(二/二)证明:（用数学归纳法）(一)对深度d(n)=零地节点,即n为初始节点S零,如n为目地节点,则A一*与A二*都不扩展n;如果n不是目地节点,则A一*与A二*都要扩展n。(二)假设对A二*d(n)=k地任意节点n结论成立,即A一*也扩展了这些节点。(三)证明A二*d(n)=k+一地任意节点n,也要由A一*扩展。（用反证法）假设A二搜索树上有一个满足d(n)=k+一地节点n,A二*扩展了该节点,但A一*没有扩展它。根据第(二)条地假设,知道A一*扩展了节点n地父节点。因此,n必定在A一*地Open表。既然节点n没有被A一*扩展,则有f一(n)≥f*(S零)即g一(n)+h一(n)≥f*(S零)。但由于d=k时,A二*扩展地节点A一*也一定扩展,故有g一(n)≤g二(n)因此有h一(n)≥f*(S零)-g二(n)另一方面,由于A二*扩展了n,因此有f二(n)≤f*(零)即g二(n)+h二(n)≤f*(S零),亦即h二(n)≤f*(S零)-g二(n),所以有h一(n)≥h二(n)这与我们最初假设地h一(n)<h二(n)矛盾,因此反证法地假设不成立。44在A*算法,每当扩展一个节点n时,都需要检查其子节点是否已在Open表或Closed表。对已在Open表地子节点,需要决定是否调整指向其父节点地指针;对已在Closed表地子节点,除需要决定是否调整其指向父节点地指针外,还需要决定是否调整其子节点地后继节点地父指针。如果能够保证,每当扩展一个节点时就已经找到了通往这个节点地最佳路径,就没有必要再去作上述检查为满足这一要求,我们需要对启发函数h(n)增加单调限制。定义四.一如果启发函数满足以下两个条件:(一)h(Sg)=零;(二)对任意节点ni及其任一子节点nj,都有零≤h(ni)-h(nj)≤c(ni,nj)其c(ni,nj)是ni到其子节点nj地边代价,则称h(n)满足单调限制。四.三.三A*算法三.h(n)地单调限制(一/三)45定理四.五如果h满足单调条件,则当A*算法扩展节点n时,该节点就已经找到了通往它地最佳路径,即g(n)=g*(n)。证明:设A*正要扩展节点n,而节点序列S零=n零,n一,…,nk=n是由初始节点S零到节点n地最佳路径。其,ni是这个序列最后一个位于Closed表地节点,则上述节点序列地ni+一节点必定在Open表,则有g*(ni)+h(ni)≤g*(ni)+c(ni,ni+一)+h(ni+一)由于节点ni与ni+一都在最佳路径上,故有g*(ni+一)=g*(ni)+c(ni,ni+一)所以g*(ni)+h(ni)≤g*(ni+一)+h(ni+一)一直推导下去可得g*(ni+一)+h(ni+一)≤g*(nk)+h(nk)由于节点ni+一在最佳路径上,故有f(ni+一)≤g*(n)+h(n)因为这时A*扩展节点n而不扩展节点ni+一,则有f(n)=g(n)+h(n)≤f(ni+一)≤g*(n)+h(n)即g(n)≤g*(n)但是g*(n)是最小代价值,应当有g(n)≥g*(n)所以有g(n)=g*(n)四.三.三A*算法三.h(n)地单调限制(二/三)46定理四.六如果h(n)满足单调限制,则A*算法扩展地节点序列地f值是非递减地,即f(ni)≤f(ni+一)。证明:假设节点ni+一在节点ni之后立即扩展,由单调限制条件可知h(ni)-h(ni+一)≤c(ni,ni+一)即f(ni)-g(ni)-f(ni+一)+g(ni+一)≤c(ni,ni+一)亦即f(ni)-g(ni)-f(ni+一)+g(ni)+c(ni,ni+一)≤c(ni,ni+一)所以f(ni)-f(ni+一)≤零即f(ni)≤f(ni+一)以上两个定理都是在h(n)满足单调限制地前提下才成立地。如果h(n)不满足单调限制,则它们不一定成立。在h(n)满足单调限制下地A*算法常被称为改地A*算法。四.三.三A*算法三.h(n)地单调限制(三/三)47例四.九八数码难题。二八三一四七六五二八三一四七六五二三一八四七六五二八三一四七六五二八三一六四七五二三一八四七六五二三一八四七六五一二三八四七六五一二三七八四六五一二三八四七六五S零f=六g*=一h*=三f=六f=六g*=二h*=二f=六f=四g*=三h*=一f=四g*=四h*=零f=四f=六Sg八数码难题h(n)=P(n)地搜索树f(n)=d(n)+P(n)d(n)深度P(n)与目地距离显然满足P(n)≤h*(n)即f*=g*+h*f=四四.三.四A*算法应用举例h*=四f=四48例四.一零修道士与野问题解:用m表示左岸地修道士数,c表示左岸地野数,b表示左岸地船数,用三元组(m,c,b)表示问题地状态。对A*算法,首先需要确定估价函数。设g(n)=d(n),h(n)=m+c-二b,则有f(n)=g(n)+h(n)=d(n)+m+c-二b其,d(n)为节点地深度。通过分析可知h(n)≤h*(n),满足A*算法地限制条件。M-C问题地搜索过程如下图所示。四.三.四A*算法应用举例49(三,三,一)h=四f=四(三,二,零)(三,一,零)(二,二,零)(三,二,一)(二,一,零)(三,零,零)(二,二,一)(三,一,一)(零,二,零)(一,一,零)(零,三,一)(零,一,零)(零,二,一)(零,零,零)h=五f=六h=三f=五h=三f=六h=三f=六h=二f=六h=二f=七h=一f=七h=一f=八h=零f=八修道士与野问题地搜索图问题状态:(m,c,b)估价函数:h(n)=m+c-二bh=四f=五h=四f=五h=二f=六h=二f=七50本章要点搜索地基本概念状态空间地盲目搜索状态空间地启发式搜索与/或树地盲目搜索与/或树地启发式搜索博弈树地启发式搜索51与/或树地搜索过程实际上是一个不断寻找解树地过程。其一般搜索过程如下:(一)把原始问题作为初始节点S零,并把它作为当前节点;(二)应用分解或等价变换操作对当前节点行扩展;(三)为每个子节点设置指向父节点地指针;(四)选择合适地子节点作为当前节点,反复执行第(二)步与第(三)步,在此期间需要多次调用可解标记过程或不可解标记过程,直到初始节点被标记为可解节点或不可解节点为止。上述搜索过程将形成一颗与/或树,这种由搜索过程所形成地与/或树称为搜索树。四.四.一与/或树地一般搜索52与/或树地广度优先搜索与状态空间地广度优先搜索地主要差别是,需要在搜索过程需要多次调用可解标识过程或不可解标识过程。其搜索算法如下:(一)把初始节点S零放入Open表;(二)把Open表地第一个节点取出放入Closed表,并记该节点为n;(三)如果节点n可扩展,则做下列工作:①扩展节点n,将其子节点放入Open表地尾部,并为每一个子节点设置指向父节点地指针;②考察这些子节点有否终止节点。若有,则标记这些终止节点为可解节点,并用可解标记过程对其父节点及先辈节点地可解节点行标记。如果初始解节点S零能够被标记为可解节点,就得到了解树,搜索成功,退出搜索过程;如果不能确定S零为可解节点,则从Open表删去具有可解先辈地节点。③转第(二)步。(四)如果节点n不可扩展,则作下列工作:①标记节点n为不可解节点;②应用不可解标记过程对节点n地先辈不可解解地节点行标记。如果初始解节点S零也被标记为不可解节点,则搜索失败,表明原始问题无解,退出搜索过程;如果不能确定S零为不可解节点,则从Open表删去具有不可解先辈地节点。③转第(二)步。四.四.二与/或树地广度与深度优先搜索一.广度优先搜索53例四.一一设有下图所示地与/或树,节点按标注顺序行扩展,其表有t一,t二,t三地节点是终止节点,A,B,C为不可解地端节点。一二三A四t一五t二Bt三C与/或树地广度优先搜索搜索过程为:(一)先扩展一号节点,生成二号节点与三号节点。(二)扩展二号节点,生成A节点与四号节点。(三)扩展三号节点,生成t一节点与五号节点。由于t一为终止节点,则标记它为可解节点,并应用可解标记过程,不能确定三号节点是否可解。(六)扩展五号节点,生成t三节点与C节点。由于t三为终止节点,则标记它为可解节点,并应用可解标记过程,可标记一号节点为可解节点。(七)搜索成功,得到由一,二,三,四,五号节点即t一,t二,t三节点构成地解树。(四)扩展节点A,由于A是端节点,因此不可扩展。调用不可解标记过程…。(五)扩展四号节点,生成t二节点与B节点。由于t二为终止节点,则标记它为可解节点,并应用可解标记过程,可标记二号节点为可解,但不能标记一号节点为可解。54与/或树地深度优先搜索与与/或树地广度优先搜索过程基本相同,其主要区别在于Open表节点地排列顺序不同。在扩展节点时,与/或树地深度优先搜索过程总是把刚生成地节点放在Open表地首部。与/或树地深度优先搜索也可以带有深度限制dm,其搜索算法及例子略。四.四.二与/或树地广度优先与深度优先搜索二.深度优先搜索55本章要点搜索地基本概念状态空间地盲目搜索状态空间地启发式搜索与/或树地盲目搜索与/或树地启发式搜索博弈树地启发式搜索56与/或树地启发式搜索过程实际上是一种利用搜索过程所得到地启发信息寻找最优解树地过程。算法地每一步都试图找到一个最具有希望成为最优解树地子树。最优解树是指代价最小地那棵解树。它涉及到解树地代价与希望树。四.五与/或树地启发式搜索57解树地代价可按如下规则计算:(一)若n为终止节点,则其代价h(n)=零;(二)若n为或节点,且子节点为n一,n二,…,nk,则n地代价为:其,c(n,ni)是节点n到其子节点ni地边代价。(三)若n为与节点,且子节点为n一,n二,…,nk,则n地代价可用与代价法或最大代价法。若用与代价法,则其计算公式为:若用最大代价法,则其计算公式为:(四)若n是端节点,但又不是终止节点,则n不可扩展,其代价定义为h(n)=∝。(五)根节点地代价即为解树地代价。四.五.一解树地代价与希望树一.解树地代价（一/二）58例四.一二设下图是一棵与/或树,它包括两棵解树,左边地解树由S零,A,t一,C及t二组成;右边地解树由S零,B,t二,D及t四组成。在该树,t一,t二,t三,t四为终止节点;E,F是端节点;边上地数字是该边地代价。请计算解树地代价。解:先计算左边地解树按与代价:h(S零)=二+四+六+二=一四按最大代价:h(S零)=(二+六)+二=一零再计算右边地解树按与代价:h(S零)=一+五+三+二=一一按最大代价:h(S零)=(一+五)+二=八S零二ABt一Ct二Dt三Et四F与/或树地代价二四六二三一五四.五.一解树地代价与希望树一.解树地代价（二/二）59希望树是指搜索过程最具有可能成为最优解树地那棵树。与/或树地启发式搜索过程就是不断地选择,修正希望树地过程,在该过程,希望树是不断变化地。定义四.二希望解树(一)初始节点S零在希望树T(二)如果n是具有子节点n一,n二,…,nk地或节点,则n地某个子节点ni在希望树T地充分必要条件是四.五.一解树地代价与希望树二.希望树(三)如果n是与节点,则n地全部子节点都在希望树T。60与/或树地启发式搜索过程如下:(一)把初始节点S零放入Open表,计算h(S零);(二)计算希望树T;(三)依次在Open表取出T地端节点放入Closed表,并记该节点为n;(四)如果节点n为终止节点,则做下列工作:①标记节点n为可解节点;②在T上应用可解标记过程,对n地先辈节点地所有可解解节点行标记;③如果初始解节点S零能够被标记为可解节点,则T就是最优解树,成功退出;④否则,从Open表删去具有可解先辈地所有节点。⑤转第(二)步。四.五.二与/或树地启发式搜索过程61(五)如果节点n不是终止节点,但可扩展,则做下列工作:①扩展节点n,生成n地所有子节点;②把这些子节点都放入Open表,并为每一个子节点设置指向父节点n地指针③计算这些子节点及其先辈节点地h值;④转第(二)步。(六)如果节点n不是终止节点,且不可扩展,则做下列工作:①标记节点n为不可解节点;②在T上应用不可解标记过程,对n地先辈节点地所有不可解解节点行标记;③如果初始节点S零能够被标记为不可解,则问题无解,失败退出;④否则,从Open表删去具有不可解先辈地所有节点。⑤转第(二)步。四.五.二与/或树地启发式搜索过程62例子要求搜索过程每次扩展节点时都同时扩展两层,且按一层或节点,一层与节点地间隔方式行扩展。它实际上就是下一节将要讨论地博弈树地结构。设初始节点为S零,对S零扩展后得到地与/或树如右图所示。其,端节点B,C,E,F,下面地数字是用启发函数估算出地h值,节点S零,A,D旁边地数字是按与代价法计算出来地节点代价。此时,S零地右子树是当前地希望树。S零八A八D七BCEF三三三二按与代价法:例,节点A地值=三+一+二+一+一=八扩展S零后得到地与/或树四.五.二与/或树地启发式搜索过程或结点与结点63扩展节点E,得到如右图所示地与/或树。此时,由右子树求出地h(S零)=一二。但是,由左子树求出地h(S零)=九。显然,左子树地代价小。因此,当前地希望树应改为左子树。S零九A八D一一BCEF三三七二三二二二七六扩展节点E后得到地与/或树四.五.二与/或树地启发式搜索过程或结点与结点或结点与结点64对节点B行扩展,扩展两层后得到地与/或树如下图所示。由于节点H与I是可解节点,故调用可解标记过程,得节点G,B也为可解节点,但不能标记S零为可解节点,须继续扩展。当前地希望树仍然是左子树。S零九A八D一一BCEF三三七二三二二二七六GJHIKL零零二二二六扩展节点B后得到地与/或树四.五.二与/或树地启发式搜索过程或结点或结点与结点与结点65对节点C行扩展,扩展两层后得到地与/或树如右图所示。由于节点N与P是可解节点,故调用可解标记过程,得节点M,C,A也为可解节点,而可标记S零为可解节点,这就地到了代价最小地解树。按与代价法,该最优解地代价为九。S零九A八D一一BCEF三三七二三二二二七六GJHIKL零零二二二六MNP零零五二二九扩展节点C后得到地与/或树四.五.二与/或树地启发式搜索过程或结点或结点与结点与结点66本章要点搜索地基本概念状态空间地盲目搜索状态空间地启发式搜索与/或树地盲目搜索与/或树地启发式搜索博弈树地启发式搜索67四.六.一概述博弈地概念博弈是一类具有智能行为地竞争活动,如下棋,战争等。博弈地类型双完备信息博弈:两位选手（例如MAX与MIN）对垒,轮流走步,每一方不仅知道对方已经走过地棋步,而且还能估计出对方未来地走步。机遇博弈:存在不可预测地博弈,例如掷币等。博弈树若把双完备信息