人工智能搜索问题102

1第一章搜索问题•内容：状态空间的搜索问题。•搜索方式：–盲目搜索–启发式搜索•关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。2搜索问题（续1）S0Sg3搜索问题（续2）•讨论的问题：–有哪些常用的搜索算法。–问题有解时能否找到解。–找到的解是最佳的吗？–什么情况下可以找到最佳解？–求解的效率如何。41.1回溯策略•例：皇后问题QQQQ5()6()Q((1,1))7()QQ((1,1))((1,1)(2,3))8()Q((1,1))((1,1)(2,3))9()QQ((1,1))((1,1)(2,3))((1,1)(2,4))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))11()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))15()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))16()((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))17()((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))Q((1,2)(2,4)(3,1)(4,3))18递归的思想从前有座山……从前有座山……从前有座山……19递归的思想（续）当前状态目标状态g20一个递归的例子intListLenght(LIST*pList){if(pList==NULL)return0;elsereturnListLength(pList-next)+1;}NULLpLIST12321回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。22回溯搜索算法递归过程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:=APPRULES(DATA);4,LOOP:IFNULL(RULES)RETURNFAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAILGOLOOP;10,RETURNCONS(R,PATH);23存在问题及解决办法•解决办法：–对搜索深度加以限制–记录从初始状态到当前状态的路径当前状态问题：–深度问题–死循环问题24回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。25回溯搜索算法11,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);26回溯搜索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);27一些深入的问题•失败原因分析、多步回溯QQ28一些深入问题（续）•回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ3223291.2图搜索策略•问题的引出–回溯搜索：只保留从初始状态到当前状态的一条路径。–图搜索：保留所有已经搜索过的路径。30一些基本概念•节点深度：根节点深度=0其它节点深度=父节点深度+1012331一些基本概念（续1）•路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。•路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。32一些基本概念（续1）•扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。33一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);34一般的图搜索算法（续）7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；35节点类型说明…...…...…...…...…...mjmkml36修改指针举例123456s37修改指针举例（续1）123456s38123456修改指针举例（续2）s39123456修改指针举例（续3）s401.3无信息图搜索过程•深度优先搜索•宽度优先搜索41深度优先搜索1,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,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;42231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标43深度优先搜索的性质•一般不能保证找到最优解•当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制•最坏情况时，搜索空间等同于穷举•与回溯法的差别：图搜索•是一个通用的与问题无关的方法44宽度优先搜索1,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,IF目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;4523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标823418765446宽度优先搜索的性质•当问题有解时，一定能找到解•当问题为单位耗散值，且问题有解时，一定能找到最优解•方法与问题无关，具有通用性•效率较低•属于图搜索方法47渐进式深度优先搜索方法•目的–解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。•思想首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。481.4启发式图搜索•利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。•启发信息的强度–强：降低搜索工作量，但可能导致找不到最优解–弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解49希望：•引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。50基本思想•定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。511，启发式搜索算法A（A算法）•评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数h(n)：启发函数52符号的意义•g*(n)：从s到n的最短路径的耗散值•h*(n)：从n到g的最短路径的耗散值•f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值•g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值53A算法1,OPEN:=(s),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);54A算法（续）ADD(mj,OPEN),标记mj到n的指针；IFf(n,mk)f(mk)THENf(mk):=f(n,mk),标记mk到n的指针；IFf(n,ml)f(ml,)THENf(ml):=f(n,ml),标记ml到n的指针,ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；55…...…...…...…...…...mjmkmlnab56Closed表Open表57一个A算法的例子定义评价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数283164751238476558h计算举例h(n)=42831647512345768592831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目标123456602，最佳图搜索算法A*（A*算法）•在A算法中，如果满足条件：h(n)≤h*(n)则A算法称为A*算法。61A*条件举例•8数码问题–h1(n)=“不在位”的将牌数–h2(n)=将牌“不在位”的距离和2831647512345768将牌1：1将牌2：1将牌6：1将牌8：262A*算法的性质•A*算法的假设设n