《人工智能搜索策略优秀PPT.ppt》由会员分享，可在线阅读，更多相关《人工智能搜索策略优秀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无信息引导的搜寻策略l不考虑给定问题的特定学问或阅历学问l系统依据
2、事先设定好的搜寻方法，依据固定的套路，依次或随机地从规则库（或学问库）中选取规则l规则的选取或调用相对比较死板，有确定“盲目性”，简洁导致“组合爆炸”状况的发生l有信息引导的搜寻策略l接受了问题领域的“启发式”信息l可以动态地确定对规则的运用依次l能够有效地削减搜寻时间l可防止或避开“组合爆炸”现象l“启发式”信息能进一步增加AI搜寻策略的效能，达到“锦上添花”的目的l“启发式”信息与恰当的限制策略的协作运用，是解决困难问题的有效方法5具体搜寻方法l求任一解路的搜寻策略l回溯法Backtracking有信息引导l爬山法HillClimbing有信息引导l宽度优先法Breadth-firstl深
3、度优先法Depth-firstl限定范围搜寻法BeamSearchl好的优先法（A策略）Best-firstSearch有信息引导l求最佳解路的搜寻策略l分支界限法BranchandBoundl动态规划法DynamicProgrammingl最佳图搜寻法（A*策略)-好的优先、分支界限与动态规划方法的综合l求与或关系解图的搜寻策略l一般与或图搜寻法（AO*)l微小极大法（MinMax)l-剪枝法（Alpha-BetaPruning)l启发式剪枝法（Heuristic-Pruning)6回溯策略 Backtracking Strategiesl说明：取单个自变量DATA，表示综合数据库的当前状态
4、。若算法成功，则返回一张规则表作为输出，代表问题的求解步骤。若无解，则返回FAIL，失败退出。l1.递归过程BACKTRACK(DATA)lIFTERM(DATA),RETURNNIL;TERM取真即找到目标，过程返回NILlIFDEADEND(DATA),RETURNFAIL;回溯点lRULES:=APPLES(DATA);计算DATA的可用规则集，依某种原则（随意排列或按启发式准则）排列后赋给RULESlLOOP:IFNULL(RULES),RETURNFAIL;回溯点lR:=FIRST(RULES);取出RULES中的第一条规则lRULES:=TAIL(RULES);删去RULES中的头
5、条规则，削减可用规则表的长度lRDATA:=GEN(R,DATA);调用规则R作用于当前状态，产生新的状态，赐予RDATAlPATH:=BACKTRACK(RDATA);以新状态RDATA为参数递归调用BACKTRACK过程lIFPATH=FAIL，GOLOOP；lRETURNCONS(R,PATH);过程返回解路径规则表（或局部解路径子表）7应用实例-四皇后问题l问题描述：l在一个44的国际象棋棋盘上，一次一个地排布四枚皇后棋子，要求满足每行、每列和对角线上只允许出现一枚棋子。即棋子之间不允许相互俘获。8QQQQQQQQQQQQQQQSUCCESSDEADEND9l综合数据库lDATA=L（
6、表）或集合lL的元素ij，其中1i,j4l当表DATA非空时，其表中元素表示棋子所在的行和列，由于只有四个棋子，故表DATA中最多有4个元素。l如：初始状态DATA=（）；l成功状态DATA=（12243143）l或DATA=（13213442）l规则库lIF1i4ANDlength(DATA)=i-1lTHENAPPEND(DATA,ij);l其中i代表行数，j代表列数（1j4）l可知，实际共有44=16条规则，分别表示在满足前提条件的基础上，在ij处放一个棋子。如规则R11R44。l限制策略-BACKTRACK过程10l假定四皇后问题的规则集，其规则排列依次为固定的依次，如R11，R12，
7、R13，R14，R21，R22，R44，则运用以上BACKTRACK过程时，其搜寻空间示意图如下图表示。l回溯次数为22次。l主过程结束时返回规则表：lPATH=（R12R24R31R43）l解的路径为（）（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利用问题的有关信息（启发式信息
8、）对规则集中的规则进行动态排序l定义一个对角线函数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过程本身进行
9、改进l以上BACKTRACK过程仅有2个回溯点，对于求解四皇后问题，已经足够解决。但对于“八数码游戏”则有所限制，主要表现在“八数码游戏”可能存在搜寻深度较深，而且还可能出现重复状态，因此应当再增加两个回溯点，即“深度范围”限制，以及防止出现“重复状态”引起的死循环的回溯点。15有四个回溯点的递归过程l过程BACKTRACK1（DATALIST）lDATA=FIRST(DATALIST);lIFMEMBER(DATA,TAIL(DATALIST),RETURNFAIL;回溯点lIFTERM(DATA),RETURNNIL;TERM取真即找到目标，过程返回NILlIFDEADEND(DATA),
10、RETURNFAIL;回溯点lIFLENGTH(DATALIST)BOUND,RETURNFAIL;回溯点lRULES:=APPLES(DATA);计算DATA的可用规则集，依某种原则（随意排列或按启发式准则）排列后赋给RULESlLOOP:IFNULL(RULES),RETURNFAIL;回溯点lR:=FIRST(RULES);取出RULES中的第一条规则lRULES:=TAIL(RULES);删去RULES中的头条规则，削减可用规则表的长度lRDATA:=GEN(R,DATA);调用规则R作用于当前状态，产生新的状态，赐予RDATAlRDATALIST:=CONS(RDATA,DATALI
11、ST);lPATH:=BACKTRACK1(RDATALIST);以新状态RDATALIST为参数递归调用BACKTRACK1过程lIFPATH=FAIL，GOLOOP；lRETURNCONS(R,PATH);过程返回解路径规则表（或局部解路径子表）16对以上对回溯过程的进一步改进l过程BACKTRACK1（DATALIST）的回溯思想：当第n层调用失败，则该过程返回到第n-1层接着搜寻，即每次只回溯1层。l实际应用：造成深层搜寻失败的缘由往往由较浅的层引起，可以通过利用具体问题领域的启发式信息，分析失败的缘由，再回溯到合适的层次上-实现多层回溯，进一步改进过程过程BACKTRACK(DATA
12、)或BACKTRACK1（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这段路径的耗
13、散值l扩展一个节点-对当前节点应用规则，生成后继节点（新状态），并给出连接弧线的耗散值（相当于运用该条规则的代价），这个过程扩展一个节点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)
14、,REMOVE(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表中的节点按某种原则重新排序
15、9)GOLoop;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)GOLoo
16、p;21l宽度优先：过程BREADTH-FIRST-SEARCHlG:=G0(G0=S),OPEN:=(S)，CLOSED:=();lLoop:IFOPEN=(),THENEXIT(FAIL);ln:=FIRST(OPEN)；lIFGOAL(n),THENEXIT(SUCCESS);lREMOVE(n,OPEN),ADD(n,CLOSED);lEXPAND(n)mi,G:=ADD(mi,G);lADD(mj,OPEN),并标记mj到n的指针；l把不在OPEN表或CLOSED表中的节点mj放在OPEN表的最终面，使深度浅的节点可优先扩展；lGOLoop;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引入启发式评估函数：lf(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,mi)
20、是从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,mi
21、)h(mi)f(n,mi)min的子节点28好的优先搜寻策略应用实例-八数码游戏l启发式评估函数：lf(n)=g(n)+h(n)l其中：lg(n)=d(n),d(n)为节点n的深度，即假设路径Sn的每一段均为单位耗散的状况，或每走一步的代价值都是一样的。lh(n)=w(n),w(n)表示节点n的不在位将牌数。lf(n)=g(n)+h(n)，可估计出通向目标节点的希望程度292831647528316475283164758321476528314765283147652831476528371465231847652341876523418765123487651823476517234865
22、(S,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,
23、5)(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)爬山法的主要求解步骤:n:=S;Lo
24、op:IFGOAL(n)THENEXIT(SUCCESS);EXPAND(n)mi,计算h(mi),nextn:=m(minh(mi)的节点);IFh(n)h(nextn)THENEXIT(FAIL);n:=nextn;GoLoop;说明:爬山法的启发式评估函数:f(n)=h(n)即只关切当前节点与目标(或”山顶”)之间的高度(或距离)大小.例如,”八数码游戏”便可以用爬山法来求解,此时h(n)=w(n),即用不在位将牌数来表示当前节点与目标之间的距离”差异”.32分支界限法(Branch Bound)l启发式评估函数：f(n)=g(n)l优先扩展具有最小耗散值的分支路径，不考虑h(n),即h
25、(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-n,QU
26、EUE),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方法：选取Sm
27、的具有最小耗散值的路径，其余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);排序：若QUEUE中有
28、多条到达某一公共节点的路径，则只保留耗散值最小的那条路径，其余均删去，然后重新排序，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)其中：启发式评估函数：f(n)=g(n)+h(n)h*(n)是路径nt的实际耗散值在最佳图搜寻A*策略中，要求路径n
29、t的估计耗散值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迷宫问题-搜寻策略l接受A*策略，以便求得最佳解l假定每搜寻一步为单位耗散，则可定义：h(n)=|XG-Xn|+|YG-Yn|l其中：（XG，YG）为目标坐标，即出口点。(Xn,Yn)为随意一节点n的坐标。l依据以上关于h(n)的定义，可知：lh(n)h*(n)l取g(n)=d(n
32、),则启发式评估函数lf(n)=g(n)+h(n)l=d(n)+h(n)l并假设搜寻过程在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)