清华大学《人工智能导论》课程电子教案143.pptx
第一章 产生式系统l 1943年Post 首先在一种计算形式体系中提出l 60年代开始，成为专家系统的最基本的结构l 形式上很简单，但在一定意义上模仿了人类思考的过程11.1 产生式系统的基本组成l 组成三要素：一个综合数据库存放信息 一组产生式规则知识 一个操作系统规则的解释或执行程序（操作策略）（推理引擎）2规则的一般形式l IF THEN l IF THEN l 或者简写为：31.2 产生式系统的基本过程过程PRODUCTION1，DATA 初始数据库2，until DATA 满足结束条件，do3，4，在规则集中选择一条可应用于DATA 的规则R5，DATA R 应用到DATA 得到的结果6，4一个简单的例子l 问题：设字符转换规则A BCA CDB CGB EFDE已知：A，B求：F5一个简单的例子（续1）一、综合数据库x，其中x为字符二、规则集1，IF A B THEN C2，IF A C THEN D3，IF B C THEN G4，IF B E THEN F5，IF D THEN E6一个简单的例子（续2）三、操作策略顺序排队四、初始条件A，B五、结束条件F x7求解过程数据库 可触发规则 被触发规则A，B（1）（1）A，B，C（2）（3）（2）A，B，C，D（3）（5）（3）A，B，C，D，G（5）（5）A，B，C，D，G，E（4）（4）A，B，C，D，G，E，F1，IF A B THEN C 2，IF A C THEN D3，IF B C THEN G 4，IF B E THEN F5，IF D THEN E81.3 问题表示举例例1：传教士与野人问题（M-C 问题）问题：N 个传教士，N 个野人，一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。问：如何过河。以N=3，k=2 为例求解。9M-C 问题（续1）初始 目标 L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 110M-C 问题（续2）1，综合数据库（m,c,b)，其中：0m,c3,b 0,12，初始状态（3，3，1）3，目标状态（结束状态）（0，0，0）11M-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)12M-C 问题（续4）IF(m,c,0)THEN(m+1,c,1)IF(m,c,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，操作策略：（略）13M-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)14猴子摘香蕉问题 c a b15猴子摘香蕉问题（续1）1，综合数据库（M,B,Box,On,H）M：猴子的位置B：香蕉的位置Box：箱子的位置On=0：猴子在地板上On=1：猴子在箱子上H=0：猴子没有抓到香蕉H=1：猴子抓到了香蕉16猴子摘香蕉问题（续2）2，初始状态（c,a,b,0,0）3，结束状态（x1,x2,x3,x4,1）其中x1x4为变量。17猴子摘香蕉问题（续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: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 为变量181.4 产生式系统的特点l 数据驱动l 知识的无序性l 操作系统与问题无关l 数据、知识和操作相互独立191.5 产生式系统的类型l 正向、逆向、双向产生式系统l 可交换的产生式系统l 可分解的产生式系统20第二章 产生式系统的搜索策略l 内容：状态空间的搜索问题。l 搜索方式：盲目搜索 启发式搜索l 关键问题：如何利用知识，尽可能有效地找到问题的解（最正确解）。21产生式系统的搜索策略（续1）S0Sg22产生式系统的搜索策略（续2）l 讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最正确的吗？什么情况下可以找到最正确解？求解的效率如何。232.1 回溯策略l 例：皇后问题24()25()Q(1,1)26()QQ(1,1)(1,1)(2,3)27()Q(1,1)(1,1)(2,3)28()QQ(1,1)(1,1)(2,3)(1,1)(2,4)29()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)30()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)31()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)32()(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)Q(1,2)34()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)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)Q(1,2)(2,4)(3,1)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)Q(1,2)(2,4)(3,1)(4,3)37递归的思想当前状态目标状态g38一个递归的例子int ListLenght(LIST*pList)if(pList=NULL)return 0;else return ListLength(pList-next)+1;NULLpLIST1 2339回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。40回溯搜索算法递归过程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);41存在问题及解决方法l 解决方法：对搜索深度加以限制 记录从初始状态到当前状态的路径当前状态l 问题：深度问题 死循环问题42回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。43
