人工智能导论1

《人工智能导论1》由会员分享，可在线阅读，更多相关《人工智能导论1（142页珍藏版）》请在金锄头文库上搜索。

1、1,第一章 产生式系统,1943年Post首先在一种计算形式体系中提出 60年代开始，成为专家系统的最基本的结构 形式上很简单，但在一定意义上模仿了人类思考的过程,2,1.1 产生式系统的基本组成,组成三要素： 一个综合数据库存放信息 一组产生式规则知识 一个控制系统规则的解释或执行程序 （控制策略） （推理引擎）,3,规则的一般形式,IF THEN IF THEN 或者简写为： ,4,1.2 产生式系统的基本过程,过程PRODUCTION 1，DATA初始数据库 2，until DATA满足结束条件，do 3， 4， 在规则集中选择一条可应用于DATA 的规则R 5， DATA R应用到DA

2、TA得到的结果 6，,5,一个简单的例子,问题：设字符转换规则 ABC ACD BCG BEF DE 已知：A，B 求：F,6,一个简单的例子（续1）,一、综合数据库 x，其中x为字符 二、规则集,1，IF AB THEN C 2，IF AC THEN D 3，IF BC THEN G 4，IF BE THEN F 5，IF D THEN E,7,一个简单的例子（续2）,三、控制策略 顺序排队 四、初始条件 A，B 五、结束条件 Fx,8,求解过程,数据库 可触发规则 被触发规则,A，B,（1）,（1）,A，B，C,（2）（3）,（2）,A，B，C，D,（3）（5）,（3）,A，B，C，D，G

3、,（5）,（5）,A，B，C，D，G，E,（4）,（4）,A，B，C，D，G，E，F,1，IF AB THEN C 2，IF AC THEN D 3，IF BC THEN G 4，IF BE THEN F 5，IF D THEN E,9,1 .3 问题表示举例,例1：传教士与野人问题（M-C问题） 问题：N个传教士，N个野人，一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。 问：如何过河。 以N=3，k=2为例求解。,10,M-C问题（续1）,初始 目标 L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 1,11,M-C问题

4、（续2）,1，综合数据库 （m, c, b)， 其中：0m, c3, b 0, 1 2，初始状态 （3，3，1） 3，目标状态（结束状态） （0，0，0）,12,M-C问题（续3）,4，规则集 IF (m, c, 1) THEN (m-1, c, 0) IF (m, c, 1) THEN (m, c-1, 0) IF (m, c, 1) THEN (m-1, c-1, 0) IF (m, c, 1) THEN (m-2, c, 0) IF (m, c, 1) THEN (m, c-2, 0),13,M-C问题（续4）,IF (m, c, 0) THEN (m+1, c, 1) IF (m, c

5、, 0) THEN (m, c+1, 1) IF (m, c, 0) THEN (m+1, c+1, 1) IF (m, c, 0) THEN (m+2, c, 1) IF (m, c, 0) THEN (m, c+2, 1) 5，控制策略：（略）,14,M-C问题（第二种方法）,4，规则集： IF (m, c, 1) AND 1 i+j2 THEN (m-i, c-j, 0) IF (m, c, 0) AND 1 i+j2 THEN (m+i, c+j, 1),15,猴子摘香蕉问题,c a b,16,猴子摘香蕉问题（续1）,1，综合数据库 （M, B, Box, On, H） M：猴子的位置

6、 B：香蕉的位置 Box：箱子的位置 On=0：猴子在地板上 On=1：猴子在箱子上 H=0：猴子没有抓到香蕉 H=1：猴子抓到了香蕉,17,猴子摘香蕉问题（续2）,2，初始状态 （c, a, b, 0, 0） 3，结束状态 （x1, x2, x3, x4, 1） 其中x1x4为变量。,18,猴子摘香蕉问题（续3）,4，规则集 r1: IF (x, y, z, 0, 0) THEN (w, y, z, 0, 0) r2: IF (x, y, x, 0, 0) THEN (z, y, z, 0, 0) r3: IF (x, y, x, 0, 0) THEN (x, y, x, 1, 0) r4:

7、 IF (x, y, x, 1, 0) THEN (x, y, x, 0, 0) r5: IF (x, x, x, 1, 0) THEN (x, x, x, 1, 1) 其中x, y, z, w为变量,19,1.4 产生式系统的特点,数据驱动 知识的无序性 控制系统与问题无关 数据、知识和控制相互独立,20,1.5 产生式系统的类型,正向、逆向、双向产生式系统 可交换的产生式系统 可分解的产生式系统,21,第二章 产生式系统的搜索策略,内容： 状态空间的搜索问题。 搜索方式： 盲目搜索 启发式搜索 关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。,22,产生式系统的搜索策略（续1

8、）,S0,Sg,23,产生式系统的搜索策略（续2）,讨论的问题： 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。,24,2.1 回溯策略,例：皇后问题,25,( ),26,( ),Q,(1,1),27,( ),Q,Q,(1,1),(1,1) (2,3),28,( ),Q,(1,1),(1,1) (2,3),29,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),30,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),Q,(1,1) (2,4) (3.2),31,( ),Q,Q

9、,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),32,( ),Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),33,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),34,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),35,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4)

10、,36,( ),(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),37,( ),(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),38,递归的思想,当前状态,目标状态g,39,一个递归的例子,int ListLenght(LIST *pList) if (pList = NULL) re

11、turn 0; else return ListLength(pList-next)+1; ,40,回溯搜索算法,BACKTRACK（DATA） DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,41,回溯搜索算法,递归过程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, R

12、ULES:=TAIL(RULES); 7, RDATA:=GEN(R, DATA); 8, PATH:=BACKTRACK(RDATA); 9, IF PATH=FAIL GO LOOP; 10, RETURN CONS(R, PATH);,42,存在问题及解决办法,解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径,问题： 深度问题,死循环问题,43,回溯搜索算法1,BACKTRACK1（DATALIST） DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,44,回溯搜索算法1,1, DATA:=FIRST(

13、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);,45,回溯搜索算法1（续）,9, RULES:=TAIL(RULES); 10, RDATA:=GEN(R, DA

14、TA); 11, RDATALIST:=CONS(RDATA, DATALIST); 12, PATH:=BACKTRCK1(RDATALIST) 13, IF PATH=FAIL GO LOOP; 14, RETURN CONS(R, PATH);,46,一些深入的问题,失败原因分析、多步回溯,47,一些深入问题（续）,回溯搜索中知识的利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的。,48,2.2 图搜索策略,问题的引出 回溯搜索：只保留从初始状态到当前状态的一条路径。 图搜索：保留所有已经搜索过的路径。,49,一些基本概念,节点深度： 根节点深度=0 其它节点深度=

15、父节点深度+1,0,1,2,3,50,一些基本概念（续1）,路径 设一节点序列为(n0, n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。 路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。,51,一些基本概念（续1）,扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,52,一般的图搜索算法,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);,