人工智能导论：第一章 搜索问题

1第一章 搜索问题l内容：状态空间的搜索问题。l搜索方式：盲目搜索启发式搜索l关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。2产生式系统的搜索策略（续1）S0Sg3产生式系统的搜索策略（续2）l讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。41.1 回溯策略l例：皇后问题5()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递归的思想当前状态目标状态g19回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。20回溯搜索算法递归过程BACKTRACK(DATA)1,IF TERM(DATA)RETURN NIL;2,IF DEADEND(DATA)RETURN FAIL;3,RULES:=APPRULES(DATA);4,LOOP:IF NULL(RULES)RETURN FAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);21存在问题及解决办法l解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态l问题：深度问题死循环问题22回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。23回溯搜索算法11,DATA:=FIRST(DATALIST)2,IF MENBER(DATA,TAIL(DATALIST)RETURN FAIL;3,IF TERM(DATA)RETURN NIL;4,IF DEADEND(DATA)RETURN FAIL;5,IF LENGTH(DATALIST)BOUND RETURN FAIL;6,RULES:=APPRULES(DATA);7,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);24回溯搜索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);25一些深入的问题l失败原因分析、多步回溯QQ26一些深入问题（续）l回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ3 2 2 3271.2 图搜索策略l问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。28一些基本概念l节点深度：根节点深度=0其它节点深度=父节点深度+1012329一些基本概念（续1）l路径设一节点序列为(n0,n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。l路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。30一些基本概念（续1）l扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。31一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IF OPEN=()THEN EXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IF GOAL(n)THEN EXIT(SUCCESS);6,EXPAND(n)mi,G:=ADD(mi,G);32一般的图搜索算法（续）7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GO LOOP；33节点类型说明.mjmkml34修改指针举例123456s35修改指针举例（续1）123456s36123456修改指针举例（续2）s37123456修改指针举例（续3）s381.3 无信息图搜索过程l深度优先搜索l宽度优先搜索39深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IF DEPTH(n)Dm GO LOOP;7,EXPAND(n)mi,G:=ADD(mi,G);8,IF 目标在mi中 THEN EXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GO LOOP;402 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目标41深度优先搜索的性质l一般不能保证找到最优解l当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制l最坏情况时，搜索空间等同于穷举l与回溯法的差别：图搜索l是一个通用的与问题无关的方法42宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)mi,G:=ADD(mi,G);7,IF 目标在mi中 THEN EXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GO LOOP;432 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标82 3 41 8 7 6 5444宽度优先搜索的性质l当问题有解时，一定能找到解l当问题为单位耗散值，且问题有解时，一定能找到最优解l方法与问题无关，具有通用性l效率较低l属于图搜索方法45渐进式回溯策略l目的解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。l思想首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。l过程ITERATIVE-DEEPENING-BACKTRACK(DATA0)；DATA0为初始状态lBOUND:=1；lPATH:=FAIL;lWhile (PATH!=FAIL)l DATALIST:=LIST(DATA0)；用初始状态组成一个表l PATH:=BACKTRACK1(DATALIST，BOUND)；调用回溯过程，如果PATH等于FAIL表示没有搜索到目标，否则PATH得到一条从初始节点到目标节点的路径l BOUND:=BOUND+1;加大一层搜索深度lEnd While；lRETURN PATH；返回解路径46计算时间分析l设在一个满b叉树上搜索，最佳解的深度为dl可以认为算法的运行时间与产生的节点数成正比l宽度优先产生的节点数：47l渐进式回溯策略产生的节点数：48l由于b2，有49b2345678910 时间比 2 1.5 1.33 1.25 1.2 1.17 1.14 1.13 1.11渐进式回溯策略的特点：l节省空间l有时间限制的搜索l比如计算机博弈、规划等50511.4 启发式图搜索l利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。l启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解52希望：l引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。53基本思想l定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。541，启发式搜索算法A（A算法）l评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数h(n)：启发函数55符号的意义lg*(n)：从s到n的最短路径的耗散值lh*(n)：从n到g的最短路径的耗散值lf*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值lg(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值l用f(n)对待扩展节点进行评价56A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)mi,计算f(n,mi):=g(n,mi)+h(mi);57A算法（续）ADD(mj,OPEN),标记mj到n的指针；IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),标记mk到n的指针；IF f(n,ml)其中为大于0的常数l几个等式 f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。69A*算法的性质（续1）定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则