《人工智能导论-第一章(自学)》由会员分享，可在线阅读，更多相关《人工智能导论-第一章(自学)（112页珍藏版）》请在金锄头文库上搜索。
1、1第一章第一章 搜索问题搜索问题l内容： 状态空间的搜索问题。l搜索方式：盲目搜索启发式搜索l关键问题： 如何利用知识，尽可能有效地找到问题 的解（最佳解）。2搜索问题（续搜索问题（续1 1）S0Sg3搜索问题（续搜索问题（续2 2）l讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。41.1 1.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
2、,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
3、,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：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示）
4、或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, PA
5、TH);21存在问题及解决办法存在问题及解决办法l解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态l问题：深度问题死循环问题22回溯搜索算法回溯搜索算法1 1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向 ） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。23回溯搜索算法回溯搜索算法1 11, DATA:=FIRST(DATALIST) 2, IF MENBER(DATA, TAIL(DATALIST)RETURN FAIL; 3, IF TERM(DATA) RETURN NIL; 4, IF DEADEND(
6、DATA) RETURN FAIL; 5, IF LENGTH(DATALIST)BOUNDRETURN FAIL; 6, RULES:=APPRULES(DATA); 7, LOOP: IF NULL(RULES) RETURN FAIL; 8,R:=FIRST(RULES);24回溯搜索算法回溯搜索算法1 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;
7、 14,RETURN CONS(R, PATH);25一些深入的问题一些深入的问题l失败原因分析、多步回溯QQ26一些深入问题（续）一些深入问题（续）l回溯搜索中知识的利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的 。QQQQ3 2 2 3271.2 1.2 图搜索策略图搜索策略l问题的引出回溯搜索：只保留从初始状态到当前状态的 一条路径。图搜索：保留所有已经搜索过的路径。28一些基本概念一些基本概念l节点深度： 根节点深度=0 其它节点深度=父节点深度+1012329一些基本概念（续一些基本概念（续1 1）l路径 设一节点序列为(n0, n1,nk)，对于i=1,k
8、，若节点ni-1具有一个后继节点ni，则该序 列称为从n0到nk的路径。l路径的耗散值 一条路径的耗散值等于连接这条路径各节 点间所有耗散值的总和。用C(ni, nj)表示从 ni到nj的路径的耗散值。30一些基本概念（续一些基本概念（续1 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
9、, 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）s
10、37123456修改指针举例（续3）s381.3 1.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);
11、8, IF 目标在mi中 THEN EXIT(SUCCESS); 9, ADD(mj, OPEN), 并标记mj到n的指针; 10, GO LOOP;402 3 1 8 4 7 6 52 3 1 8 4 7 6 52 8 3 1 4 7 6 52 3 1 8 4 7 6 52 8 3 1 4 7 6 52 8 3 1 6 4 7 52 8 31 4 7 6 52 8 3 1 6 4 7 52 8 3 1 6 47 52 8 3 7 1 46 58 3 2 1 4 7 6 52 8 1 4 3 7 6 52 8 3 1 4 5 7 6 1 2 3 7 8 46 51 2 3 8 4 7 6 52
12、 8 36 4 1 7 52 8 3 1 6 7 5 48 3 2 1 4 7 6 52 8 3 7 1 4 6 52 8 1 4 3 7 6 52 8 3 1 4 5 7 6123456789abcd 1 2 38 4 7 6 5目标41深度优先搜索的性质深度优先搜索的性质l一般不能保证找到最优解l当深度限制不合理时，可能找不到解， 可以将算法改为可变深度限制l最坏情况时，搜索空间等同于穷举l与回溯法的差别：图搜索l是一个通用的与问题无关的方法42宽度优先搜索1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( ); 2, LOOP: IF OPEN=( ) THEN E
13、XIT (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 3 1 8 4 7 6 52 3 1 8 4 7 6 52 8 3 1 4 7 6 52 3 1 8 4 7 6 52 8 3 1 4 7 6 52 8 3 1 6 4 7 5
14、2 8 31 4 7 6 52 8 3 1 6 4 7 52 8 3 1 6 47 52 8 3 7 1 46 58 3 2 1 4 7 6 52 8 1 4 3 7 6 52 8 3 1 4 5 7 6 1 2 3 7 8 46 51 2 3 8 4 7 6 51256731 2 38 4 7 6 5目标82 3 4 1 8 7 6 5444宽度优先搜索的性质宽度优先搜索的性质l当问题有解时，一定能找到解l当问题为单位耗散值，且问题有解时， 一定能找到最优解l方法与问题无关，具有通用性l效率较低l属于图搜索方法45渐进式回溯策略渐进式回溯策略l目的解决宽度优先方法的空间问题和回溯方法不 能找到最优解的问题。l思想 首先给回溯法一个比较小的深度限制，然后逐 渐增加深度限制，直到找到解或找遍所以分支 为止。l过程ITERATIVE-DEEPENING-BACKTRACK(DATA0) ；DATA0为初始状态lBOUND := 1；
