《人工智能(三)搜索策略.ppt》由会员分享，可在线阅读，更多相关《人工智能(三)搜索策略.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能Artificial Intelligence北京信息科技大学计算机学院李宝安2第三部分 AI的搜索策略l搜索策略或控制策略解决对规则的选取或调用方式，决定了AI的推理过程的实现，是AI系统的“三大件”之一l合理的搜索策略，可以缩小搜索空间，减少搜索的时间，提高AI问题求解的效率，并较快地找到“解的路径”lAI的搜索策略还可借助于具体问题领域的“启发式知识”，进一步提高推理效率，并避免出现推理过程中的“组合爆炸”问题3起始状态SoSg目标状态问题的全状态空间实际搜索空间空间解的路径AI搜索空间示意图4AI搜索策略的类别l无信息引导的搜索策略不考虑给定问题的特定知识或经验知识系统根据事先
2、设定好的搜索方法，依据固定的套路，顺序或随机地从规则库（或知识库）中选取规则规则的选取或调用相对比较死板，有一定“盲目性”，容易导致“组合爆炸”情况的发生l有信息引导的搜索策略采用了问题领域的“启发式”信息可以动态地确定对规则的使用顺序能够有效地减少搜索时间可防止或避免“组合爆炸”现象“启发式”信息能进一步增强AI搜索策略的效能，达到“锦上添花”的目的“启发式”信息与恰当的控制策略的配合使用，是解决复杂问题的有效方法5具体搜索方法l求任一解路的搜索策略回溯法Backtracking有信息引导爬山法HillClimbing有信息引导宽度优先法Breadth-first深度优先法Depth-fir
3、st限定范围搜索法BeamSearch好的优先法（A策略）Best-firstSearch有信息引导l求最佳解路的搜索策略分支界限法BranchandBound动态规划法DynamicProgramming最佳图搜索法（A*策略)-好的优先、分支界限与动态规划方法的综合l求与或关系解图的搜索策略一般与或图搜索法（AO*)极小极大法（MinMax)-剪枝法（Alpha-BetaPruning)启发式剪枝法（Heuristic-Pruning)6回溯策略 Backtracking Strategiesl说明：取单个自变量DATA，表示综合数据库的当前状态。若算法成功，则返回一张规则表作为输出，代表
4、问题的求解步骤。若无解，则返回FAIL，失败退出。l1.递归过程BACKTRACK(DATA)1)IFTERM(DATA),RETURNNIL;TERM取真即找到目标，过程返回NIL2)IFDEADEND(DATA),RETURNFAIL;回溯点3)RULES:=APPLES(DATA);计算DATA的可用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES4)LOOP:IFNULL(RULES),RETURNFAIL;回溯点5)R:=FIRST(RULES);取出RULES中的第一条规则6)RULES:=TAIL(RULES);删去RULES中的头条规则，减少可用规则表的长度7)
5、RDATA:=GEN(R,DATA);调用规则R作用于当前状态，产生新的状态，赋予RDATA8)PATH:=BACKTRACK(RDATA);以新状态RDATA为参数递归调用BACKTRACK过程9)IFPATH=FAIL，GOLOOP；10)RETURNCONS(R,PATH);过程返回解路径规则表（或局部解路径子表）7应用实例-四皇后问题l问题描述：在一个44的国际象棋棋盘上，一次一个地排布四枚皇后棋子，要求满足每行、每列和对角线上只允许出现一枚棋子。即棋子之间不允许相互俘获。8QQQQQQQQQQQQQQQSUCCESSDEADEND9l综合数据库DATA=L（表）或集合L的元素ij，其
6、中1i,j4当表DATA非空时，其表中元素表示棋子所在的行和列，由于只有四个棋子，故表DATA中最多有4个元素。如：初始状态DATA=（）；成功状态DATA=（12243143）或DATA=（13213442）l规则库IF1i4ANDlength(DATA)=i-1THENAPPEND(DATA,ij);其中i代表行数，j代表列数（1j4）可知，实际共有44=16条规则，分别表示在满足前提条件的基础上，在ij处放一个棋子。如规则R11R44。l控制策略-BACKTRACK过程10l假定四皇后问题的规则集，其规则排列顺序为固定的顺序，如R11，R12，R13，R14，R21，R22，R44，则使
7、用以上BACKTRACK过程时，其搜索空间示意图如下图表示。l回溯次数为22次。l主过程结束时返回规则表：PATH=（R12R24R31R43）解的路径为（）（12）（24）（31）（43）。11（31）（）（11）（12）（21）（22）（23）（24）（32）（33）（34）（31）（32）（33）（34）（41）（42）（43）（44）（21）（22）（23）（24）（31）（41）（42）（43）R12R24R31R43使用以上BACKTRACK过程的搜索空间示意图12对以上问题求解进行改进-引入启发式信息l利用问题的有关信息（启发式信息）对规则集中的规则进行动态排序l定义一个对角线函
8、数diag(i,j),负责计算通过棋盘上ij位置的最长对角线长度。l通过比较不同位置的diag(i,j)函数值，来决定规则Rij的排列顺序。将对角线短的位置，相应的规则排在前面。l根据以上的启发式信息，即对角线的长度，可以得出四皇后问题的规则集，其规则排列顺序为：R12，R13，R11，R14，R21，R24，R22，R23，R31，R34，R32，R33，R42，R43，R41，R4413引入启发式信息后BACKTRACK过程的搜索树（）（12）（21）（24）（31）（42）（43）R12R24R31R4314对BACKTRACK过程本身进行改进l以上BACKTRACK过程仅有2个回溯点，
9、对于求解四皇后问题，已经足够解决。但对于“八数码游戏”则有所限制，主要表现在“八数码游戏”可能存在搜索深度较深，而且还可能出现重复状态，因此应该再增加两个回溯点，即“深度范围”限制，以及防止出现“重复状态”引起的死循环的回溯点。15有四个回溯点的递归过程l过程BACKTRACK1（DATALIST）1)DATA=FIRST(DATALIST);2)IFMEMBER(DATA,TAIL(DATALIST),RETURNFAIL;回溯点3)IFTERM(DATA),RETURNNIL;TERM取真即找到目标，过程返回NIL4)IFDEADEND(DATA),RETURNFAIL;回溯点5)IFLE
10、NGTH(DATALIST)BOUND,RETURNFAIL;回溯点6)RULES:=APPLES(DATA);计算DATA的可用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES7)LOOP:IFNULL(RULES),RETURNFAIL;回溯点8)R:=FIRST(RULES);取出RULES中的第一条规则9)RULES:=TAIL(RULES);删去RULES中的头条规则，减少可用规则表的长度10)RDATA:=GEN(R,DATA);调用规则R作用于当前状态，产生新的状态，赋予RDATA11)RDATALIST:=CONS(RDATA,DATALIST);12)PATH
11、:=BACKTRACK1(RDATALIST);以新状态RDATALIST为参数递归调用BACKTRACK1过程13)IFPATH=FAIL，GOLOOP；14)RETURNCONS(R,PATH);过程返回解路径规则表（或局部解路径子表）16对以上对回溯过程的进一步改进l过程BACKTRACK1（DATALIST）的回溯思想：当第n层调用失败，则该过程返回到第n-1层继续搜索，即每次只回溯1层。l实际应用：造成深层搜索失败的原因往往由较浅的层引起，可以通过利用具体问题领域的启发式信息，分析失败的原因，再回溯到合适的层次上-实现多层回溯，进一步改进过程过程BACKTRACK(DATA)或BAC
12、KTRACK1（DATALIST）的搜索效果。17图搜索策略lAI系统在求解问题时，如果控制系统保留所有规则应用后生成并链接起来的综合数据库状态记录图，即记录搜索路径的搜索状态空间树或图，则称工作在这种方式下的控制系统使用了图搜索策略。l图搜索策略-实现从一个隐含图中，生成一部分确实含有一个目标节点的显式表示子图的搜索过程。18与图搜索策略有关的几个术语l节点深度-dn=dn父+1,根节点深度d0=0；l路径-节点序列（n0,n1,n2,ni,nk),其中的每一个节点ni-1都有一个后继节点ni，称做从n0nk长度为k的一条路径。l路径耗散值-C(ni,nj)为ni到nj这段路径的耗散值l扩展
13、一个节点-对当前节点应用规则，生成后继节点（新状态），并给出连接弧线的耗散值（相当于使用该条规则的代价），这个过程扩展一个节点lOPEN表-待扩展的节点，如(n,n父,f(n父,n),)lCLOSED表-已扩展的节点l每个节点的数据表包括三项：n-当前节点标识，n父-n的父节点标识，f(n父,n)-评估函数值（或者是耗散值C(n父,n)）。19一般图搜索过程1)G:=G0(G0=S),OPEN:=(S);G表示图，S为初始节点，初始化OPEN表2)CLOSED:=();初始化CLOSED表3)Loop:IFOPEN=(),THENEXIT(FAIL);4)n:=FIRST(OPEN),REMO
14、VE(n,OPEN),ADD(n,CLOSED);n为当前节点5)IFGOAL(n),THENEXIT(SUCCESS);成功退出，并返回由Sn的解的路径6)EXPAND(n)mi,G:=ADD(mi,G);对节点n进行扩展，子节点集mi不包含n的先辈节点7)标记和修改指针：其中mi=mjmkml,mj为OPEN和CLOSED表中均未出现过的子节点，ADD(mj,OPEN),并标记mj到n的指针；mk为已出现在OPEN表中的子节点，ml为在CLOSED表中的子节点，对于mk和ml计算是否要修改到n的指针（即是否将mk和ml的父节点修改为n）。8)对OPEN表中的节点按某种原则重新排序9)GOL
15、oop;20无信息的图搜索过程l深度优先：过程DEPTH-FIRST-SEARCH1)G:=G0(G0=S),OPEN:=(S)，CLOSED:=();2)Loop:IFOPEN=(),THENEXIT(FAIL);3)n:=FIRST(OPEN)；4)IFGOAL(n),THENEXIT(SUCCESS);5)REMOVE(n,OPEN),ADD(n,CLOSED);6)EXPAND(n)mi,G:=ADD(mi,G);7)ADD(mj,OPEN),并标记mj到n的指针；8)把不在OPEN表或CLOSED表中的节点mj放在OPEN表的最前面，使深度大的节点可优先扩展；9)GOLoop;21l
16、宽度优先：过程BREADTH-FIRST-SEARCH1)G:=G0(G0=S),OPEN:=(S)，CLOSED:=();2)Loop:IFOPEN=(),THENEXIT(FAIL);3)n:=FIRST(OPEN)；4)IFGOAL(n),THENEXIT(SUCCESS);5)REMOVE(n,OPEN),ADD(n,CLOSED);6)EXPAND(n)mi,G:=ADD(mi,G);7)ADD(mj,OPEN),并标记mj到n的指针；8)把不在OPEN表或CLOSED表中的节点mj放在OPEN表的最后面，使深度浅的节点可优先扩展；9)GOLoop;22启发式图搜索过程l启发式信息的
17、强、弱-能力度量l可降低搜索工作量，不必扩展过多节点l实际应用：最好满足降低工作量，但不牺牲找到最佳路径。l需研究获取启发式信息的方法，启发式信息与最佳解的关系问题！l一般地理想方法：路径耗散值+求得路径所需搜索的耗散值-其平均的组合耗散值最小l在实际中，上述指标很难做到，不必追求严格的比较结果！l经验方法如下：在启发式搜索过程中，对OPEN表进行排序，使最有希望通向目标节点的待扩展节点优先扩展。l常用方法-定义一个评价函数f（Evaluationfunction)以对各个节点进行动态的计算。23如何定义评价函数f（Evaluation function)？l参考原则：l-一个节点处在最佳路径
18、上的概率；l-求出任意一个节点与目标节点集之间的距离度量或差异度量；l-根据格局或状态的特点打分，如博弈、军事态势等24启发式搜索策略A-好的优先搜索法（Best First Search)l引入启发式评估函数：f(n)=g(n)+h(n)l其中g(n)表示从初始节点So出发，到达当前节点n，这段路径的耗散值，是一个可以定量计算的数值。lh(n)是从当前节点n出发，到达可能的目标节点Sg的估计耗散值，是一个估计的经验值。lf(n)综合了g(n)和h(n)，代表当前节点处在“好”的位置的程度，用它作为扩展各个节点的依据。一般情况下，f(n)较小的节点被优先扩展。即被放在OPEN表的前面。这也是“
19、好的优先”搜索策略的基本思想。25So初始节点n当前节点Sg目标节点g(n)h(n)f(n)26启发式搜索策略A-好的优先搜索法（Best First Search)l算法如下：1)OPEN:=(S)，CLOSED:=()，f(S)=g(S)+h(S);2)Loop:IFOPEN=(),THENEXIT(FAIL);3)n:=FIRST(OPEN)；4)IFGOAL(n),THENEXIT(SUCCESS);5)REMOVE(n,OPEN),ADD(n,CLOSED);6)EXPAND(n)mi,并计算f(n,mi)=g(n,mi)+h(mi);其中g(n,mi)是从Snmi的耗散值，f(n,
20、mi)是从Snmi目标节点耗散值的估计。其中mi=mjmkml,mj为OPEN和CLOSED表中均未出现过的子节点，ADD(mj,OPEN),并标记mj到n的指针；mk为已出现在OPEN表中的子节点，ml为在CLOSED表中的子节点，对于mk和ml计算是否要修改到n的指针（即是否将mk和ml的父节点修改为n），IFf(n,mk)f(mk)THENf(mk):=f(n,mk);IFf(n,ml)f(ml)THENf(ml):=f(n,ml),并且ADD(ml,OPEN),对ml重新进行扩展;7)对OPEN表中的节点按f值从小到大排序；8)GoLoop;27So初始节点n当前节点Sg目标节点g(n
21、,mi)h(mi)f(n,mi)min的子节点28好的优先搜索策略应用实例-八数码游戏l启发式评估函数：f(n)=g(n)+h(n)其中：g(n)=d(n),d(n)为节点n的深度，即假设路径Sn的每一段均为单位耗散的情况，或每走一步的代价值都是一样的。h(n)=w(n),w(n)表示节点n的不在位将牌数。f(n)=g(n)+h(n)，可估计出通向目标节点的希望程度292831647528316475283164758321476528314765283147652831476528371465231847652341876523418765123487651823476517234865(S
22、,4)(A,6)(B,4)(C,6)(D,5)(E,5)(F,6)(G,6)(H,7)(I,5)(J,7)(K,5)(L,5)(M,7)30八数码游戏-应用A策略OPEN表与CLOSED表的变化情况lOPEN表CLOSED表l初始:(S,4)()lLoop1:(B,4)(A,6)C(6)(S,4)lLoop2:(D,5)(E,5)(A,6)(C,6)(F,6)(S,4)(B,4)lLoop3:(E,5)(A,6)(C,6)(F,6)(G,6)(H,7)(S,4)(B,4)(D,5)lLoop4:(I,5)(A,6)(C,6)(F,6)(G,6)(H,7)(J,7)(S,4)(B,4)(D,5)
23、(E,5)lLoop5:(K,5)(A,6)(C,6)(F,6)(G,6)(H,7)(J,7)(S,4)(B,4)(D,5)(E,5)(I,5)lLoop6:(L,5)(A,6)(C,6)(F,6)(G,6)(H,7)(J,7)(M,7)(S,4)(B,4)(D,5)(E,5)(I,5)(K,5)lLoop7:GOAL(L,5)=TRUEA过程成功退出,根据(L,5)与CLOSED表,可得出解的路径:SBEIKLl补充说明:每个节点为三元式:(n,n父,f(n),采用这种结构较容易得到上面”loop7”中解的路径.31爬山法(Hill Climbing)爬山法的主要求解步骤:ln:=S;lLo
24、op:IFGOAL(n)THENEXIT(SUCCESS);lEXPAND(n)mi,计算h(mi),nextn:=m(minh(mi)的节点);lIFh(n)h(nextn)THENEXIT(FAIL);ln:=nextn;lGoLoop;说明:爬山法的启发式评估函数:f(n)=h(n)即只关心当前节点与目标(或”山顶”)之间的高度(或距离)大小.例如,”八数码游戏”便可以用爬山法来求解,此时h(n)=w(n),即用不在位将牌数来表示当前节点与目标之间的距离”差异”.32分支界限法(Branch Bound)l启发式评估函数：f(n)=g(n)l优先扩展具有最小耗散值的分支路径，不考虑h(n
25、),即h(n)=0l引入队列表：QUEUE，在QUEUE中存放当前已有从初始节点S出发的所有分支（或局部路径），如S-n,其中末节点n为搜索树的叶子节点。l在搜索时，优先扩展排在QUEUE队列表前面的分支的叶节点，QUEUE表中各分支依据g(n)的值从小到大排列。33分支界限法(Branch Bound)QUEUE:=(S-S),g(S)=0;Loop:IFQUEUE=()THENEXIT(FAIL);PATH:=FIRST(QUEUE),n:=LAST(PATH);IFGOAL(n)THENEXIT(SUCCESS);EXPAND(n)mi,计算g(mi)=g(n,mi),REMOVE(S-
26、n,QUEUE),ADD(S-mi,QUEUE);排序：QUEUE中局部路径g值最小的排在最前面；GoLoop;34城市地图网旅行问题-利用分支界限法来求解SDAEBCFt43245454335利用分支界限法求解旅行问题的搜索树SADBDAECEEBBFDFBFACtg=0g=3g=4g=7g=8g=9g=6g=11g=12g=10g=13g=11g=10g=14g=16g=15g=14g=15 g=15g=13SDAEBCFt43245454336动态规划法(Dynamic Programing)l-具有动态规划原理的分支界限法l-从QUEUE队列中去掉了多余的路径l可提高搜索的效率l方法：
27、选取Sm的具有最小耗散值的路径，其余Sm的路径均可删去。37Smt初始节点目标节点选取Sm的具有最小耗散值的路径，其余Sm的路径均删去中间节点38动态规划法(Dynamic Programing)l过程：Dynamic-ProgramingQUEUE:=(S-S),g(S):=0;Loop:IFQUEUE=()THENEXIT(FAIL);PATH:=FIRST(QUEUE),n:=LAST(PATH);IFGOAL(n)THENEXIT(SUCCESS);EXPAND(n)mi,计算g(mi)=g(n,mi),REMOVE(S-n,QUEUE),ADD(S-mi,QUEUE);排序：若QUE
28、UE中有多条到达某一公共节点的路径，则只保留耗散值最小的那条路径，其余均删去，然后重新排序，QUEUE中局部路径g值最小的排在最前面；GoLoop;39SADBDAECEtBFg=0g=3g=4g=7g=8g=9g=6g=11g=12g=11g=10动态规划法搜索树SDAEBCFt43245454340动态规划法具体应用领域l“GIS地理信息系统”l“GPS定位系统”l“旅行问题”l“调度问题”l“网络优化问题”l“寻找最短路径”l其它41最佳图搜索法A*（Optimal Search)其中：l启发式评估函数：f(n)=g(n)+h(n)lh*(n)是路径nt的实际耗散值l在最佳图搜索A*策略
29、中，要求路径nt的估计耗散值h(n)nt的实际耗散值，即须满足h(n)h*(n)。此时算法A（即好的优先）就变成了最佳图搜索方法A*；当问题有解时，可以找到最佳解。好的优先算法Ah(n)h*(n)+A*方法算法A分支界限法动态规划法42关于最佳图搜索法A*l特殊实例一：h(n)0，则A*一定能找到最佳解，如分支界限法和动态规划法l特殊实例二：h(n)0且g(n)=d(n)，如宽度优先法，也能找到最佳解，尽管比较耗时l但是：h(n)越接近h*(n),即h(n)h*(n)，则说明启发式知识多，需要扩展的节点数就会减少。l当h(n)=h*(n)，即f(n)=f*(n)，则不会扩展多余的节点，便可以找
30、到最佳解-为最理想的情况430h*(n)h(n)0h(n)h*(n)h(n)最好最差44最佳图搜索法A*应用实例-迷宫问题l求从迷宫入口出口的最短路径的走法.入口出口45入口出口YX0(1,1)(1,3)(2,3)(2,2)(2,1)(2,4)(1,4)(3,4)(3,3)(3,2)(4,3)(4,4)(3,1)(4,1)(4,2)(1,2)46迷宫问题求解-采用A*策略l综合数据库:问题的状态-即走迷宫所处的位置,以平面坐标值来表示.所处位置:(x,y),其中1x,yN(按所定义的用户坐标系)迷宫问题可归结为求(1,1)(4,4)的最短路径.其中(1,1)为入口位置(起始状态),(4,4)为
31、出口位置(即目标状态).47l迷宫问题规则库迷宫的走法规定为向东、南、西、北前进一步.因此有四条规则：Rule1:IF(x,y)THEN(x+1,y);向东走Rule2:IF(x,y)THEN(x,y-1);向南走Rule3:IF(x,y)THEN(x-1,y);向西走Rule4:IF(x,y)THEN(x,y+1);向北走48l迷宫问题-搜索策略采用A*策略，以便求得最佳解假定每搜索一步为单位耗散，则可定义：h(n)=|XG-Xn|+|YG-Yn|其中：（XG，YG）为目标坐标，即出口点。(Xn,Yn)为任意一节点n的坐标。根据以上关于h(n)的定义，可知：h(n)h*(n)取g(n)=d(
32、n),则启发式评估函数f(n)=g(n)+h(n)=d(n)+h(n)并假设搜索过程在OPEN表中，若f(n)值相等，则以深度优先进行排序，则根据“最佳图搜索A*搜索方法”，可得出以下迷宫问题搜索图：49(1,1)(2,3)(2,4)(2,2)(1,4)(3,4)(3,3)(4,3)(3,2)(4,4)(4,2)h=6f=6h=3f=6h=4f=8h=2f=6h=3f=8h=1f=6h=2f=8h=1f=8h=0f=8h=3f=10h=2f=103111111111迷宫问题搜索图入口出口YX0(1,1)(1,3)(2,3)(2,2)(2,1)(2,4)(1,4)(3,4)(3,3)(3,2)(4,3)(4,4)(3,1)(4,1)(4,2)(1,2)