华工人工智能老师上课幻灯片第一章

《华工人工智能老师上课幻灯片第一章》由会员分享，可在线阅读，更多相关《华工人工智能老师上课幻灯片第一章（102页珍藏版）》请在金锄头文库上搜索。

1、1,第一章 搜索问题,内容： 状态空间的搜索问题。 搜索方式： 盲目搜索 启发式搜索 关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。,2,搜索问题（续1）,S0,Sg,3,搜索问题（续2）,讨论的问题： 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。,4,1.1 回溯策略,例：皇后问题,5,( ),6,( ),Q,(1,1),7,( ),Q,Q,(1,1),(1,1) (2,3),8,( ),Q,(1,1),(1,1) (2,3),9,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),

2、10,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),Q,(1,1) (2,4) (3.2),11,( ),Q,Q,(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,(

3、),(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,递归的思想

4、,19,递归的思想（续）,当前状态,目标状态g,20,一个递归的例子,int ListLenght(LIST *pList) if (pList = NULL) return 0; else return ListLength(pList-next)+1; ,21,回溯搜索算法,BACKTRACK（DATA） DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,22,回溯搜索算法,递归过程BACKTRACK(DATA) 1, IF TERM(DATA) RETURN NIL; 2, IF DEADEND(DATA) RETURN FAIL; 3, R

5、ULES:=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);,23,存在问题及解决办法,解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径,问题： 深度问题,死循环问题,24,回溯搜索算法1,BACKTRACK1（DATALIST） DATA

6、LIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,25,回溯搜索算法1,1, 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

7、FAIL; 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, IF PATH=FAIL GO LOOP; 14, RETURN CONS(R, PATH);,27,一些深入的问题,失败原因分析、多步回溯,28,一些深入问题（续）,回溯搜索中知识的利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的。,29,1.2 图搜索

8、策略,问题的引出 回溯搜索：只保留从初始状态到当前状态的一条路径。 图搜索：保留所有已经搜索过的路径。,30,一些基本概念,节点深度： 根节点深度=0 其它节点深度=父节点深度+1,0,1,2,3,31,一些基本概念（续1）,路径 设一节点序列为(n0, n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。 路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。,32,一些基本概念（续1）,扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节

9、点”。,33,一般的图搜索算法,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);,34,一般的图搜索算法（续）,7, 标记和修改指针： ADD(mj, OPEN), 并标记mj到n的指针； 计算是否要修改mk、ml到n的指针； 计算是否要修改ml到其后继

10、节点的指针； 8, 对OPEN中的节点按某种原则重新排序； 9, GO LOOP；,35,节点类型说明,.,.,.,.,.,mj,mk,ml,36,修改指针举例,1,2,3,4,5,6,s,37,修改指针举例（续1）,1,2,3,4,5,6,s,38,1,2,3,4,5,6,修改指针举例（续2）,s,39,1,2,3,4,5,6,修改指针举例（续3）,s,40,1.3 无信息图搜索过程,深度优先搜索 宽度优先搜索,41,深度优先搜索,1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( ); 2, LOOP: IF OPEN=( ) THEN EXIT (FAIL); 3,

11、 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;,42,2 3 1 8 4 7 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,43,深度优先搜索的性质,一般不能保证找到最优解 当深度限制

12、不合理时，可能找不到解，可以将算法改为可变深度限制 最坏情况时，搜索空间等同于穷举 与回溯法的差别：图搜索 是一个通用的与问题无关的方法,44,宽度优先搜索,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 EX

13、IT(SUCCESS); 8, ADD(OPEN, mj), 并标记mj到n的指针; 9, GO LOOP;,45,2 3 1 8 4 7 6 5,1,2,5,6,7,3,目标,8,4,46,宽度优先搜索的性质,当问题有解时，一定能找到解 当问题为单位耗散值，且问题有解时，一定能找到最优解 方法与问题无关，具有通用性 效率较低 属于图搜索方法,47,渐进式深度优先搜索方法,目的 解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。 思想 首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。,48,1.4 启发式图搜索,利用知识来引导搜索，达到减少搜索范围

14、，降低问题复杂度的目的。 启发信息的强度 强：降低搜索工作量，但可能导致找不到最 优解 弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解,49,希望：,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,50,基本思想,定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,51,1，启发式搜索算法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)的估计值,53,A算法,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, m