清华大学《人工智能导论》课程电子教案143

1第一章产生式系统1943年Post首先在一种计算形式体系中提出60年代开始，成为专家系统的最基本的结构形式上很简单，但在一定意义上模仿了人类思考的过程21.1产生式系统的基本组成组成三要素：–一个综合数据库——存放信息–一组产生式规则——知识–一个控制系统——规则的解释或执行程序（控制策略）（推理引擎）3规则的一般形式IF前提THEN结论IF条件THEN行动或者简写为：前提－结论条件－行动41.2产生式系统的基本过程过程PRODUCTION1，DATA←初始数据库2，untilDATA满足结束条件，do3，{4，在规则集中选择一条可应用于DATA的规则R5，DATA←R应用到DATA得到的结果6，}5一个简单的例子问题：设字符转换规则A∧B→CA∧C→DB∧C→GB∧E→FD→E已知：A，B求：F6一个简单的例子（续1）一、综合数据库{x}，其中x为字符二、规则集1，IFA∧BTHENC2，IFA∧CTHEND3，IFB∧CTHENG4，IFB∧ETHENF5，IFDTHENE7一个简单的例子（续2）三、控制策略顺序排队四、初始条件{A，B}五、结束条件F∈{x}8求解过程数据库可触发规则被触发规则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，IFA∧BTHENC2，IFA∧CTHEND3，IFB∧CTHENG4，IFB∧ETHENF5，IFDTHENE91.3问题表示举例例1：传教士与野人问题（M-C问题）问题：N个传教士，N个野人，一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。问：如何过河。以N=3，k=2为例求解。10M-C问题（续1）初始目标LRLRm30m03c30c03B10B0111M-C问题（续2）1，综合数据库（m,c,b)，其中：0≤m,c≤3,b∈{0,1}2，初始状态（3，3，1）3，目标状态（结束状态）（0，0，0）12M-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)13M-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，控制策略：（略）14M-C问题（第二种方法）4，规则集：IF(m,c,1)AND1≤i+j≤2THEN(m-i,c-j,0)IF(m,c,0)AND1≤i+j≤2THEN(m+i,c+j,1)15猴子摘香蕉问题cab16猴子摘香蕉问题（续1）1，综合数据库（M,B,Box,On,H）M：猴子的位置B：香蕉的位置Box：箱子的位置On=0：猴子在地板上On=1：猴子在箱子上H=0：猴子没有抓到香蕉H=1：猴子抓到了香蕉17猴子摘香蕉问题（续2）2，初始状态（c,a,b,0,0）3，结束状态（x1,x2,x3,x4,1）其中x1～x4为变量。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: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为变量191.4产生式系统的特点数据驱动知识的无序性控制系统与问题无关数据、知识和控制相互独立201.5产生式系统的类型正向、逆向、双向产生式系统可交换的产生式系统可分解的产生式系统21第二章产生式系统的搜索策略内容：状态空间的搜索问题。搜索方式：–盲目搜索–启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。22产生式系统的搜索策略（续1）S0Sg23产生式系统的搜索策略（续2）讨论的问题：–有哪些常用的搜索算法。–问题有解时能否找到解。–找到的解是最佳的吗？–什么情况下可以找到最佳解？–求解的效率如何。242.1回溯策略例：皇后问题QQQQ25()26()Q((1,1))27()QQ((1,1))((1,1)(2,3))28()Q((1,1))((1,1)(2,3))29()QQ((1,1))((1,1)(2,3))((1,1)(2,4))30()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))31()QQ((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))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递归的思想当前状态目标状态g39一个递归的例子intListLenght(LIST*pList){if(pList==NULL)return0;elsereturnListLength(pList-next)+1;}NULLpLIST12340回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。41回溯搜索算法递归过程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:=APPRULES(DATA);4,LOOP:IFNULL(RULES)RETURNFAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAILGOLOOP;10,RETURNCONS(R,PATH);42存在问题及解决办法解决办法：–对搜索深度加以限制–记录从初始状态到当前状态的路径当前状态问题：–深度问题–死循环问题43回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。44回溯搜索算法11,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);45回溯搜索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);46一些深入的问题失败原因分析、多步回溯QQ47一些深入问题（续）回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ3223482.2图搜索策略问题的引出–回溯搜索：只保留从初始状态到当前状态的一条路径。–图搜索：保留所有已经搜索过的路径。49一些基本概念节点深度：根节点深度=0其它节点深度=父节点深度+1012350一些基本概念（续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:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);53一般的图搜索算法（续）7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；54节点类型说明…...…...…...…...…...mjmkml55修改指针举例123456s56修改指针举例（续1）123456s57123456修改指针举例（续2）s58123456修改指针举例（续3）s592.3无信息图搜索过程深度优先搜索宽度优先搜索60深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;61231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标62深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法63宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIR