欢迎大家学习人工智能导论

欢迎大家学习人工智能导论计算机系马少平自我介绍•姓名：马少平•单位：智能技术与系统国家重点实验室•电话：62782266--8407•E-mail：[e-mail]绪论•人工智能（ArtificialIntelligence）简称AI•起源于美国1956年的一次夏季讨论会•什么是AI？计算——算计•图灵实验•AI的本质问题研究如何制造出人造的智能机器或系统，来模拟人类智能活动的能力，以延伸人们智能的科学。AI的历史回顾•第一阶段（40年代中～50年代末）神经元网络时代–双层网络–M-P模型、感知器模型等–问题：XOR问题不能解决–Minsky的著作：《Perceptions》（感知器）AI的历史回顾（续1）•第二阶段（50年代中～60年代中）通用方法时代–物理符号系统–主要研究的问题：GPS、游戏、翻译等–对问题的难度估计不足，陷入困境AI的历史回顾（续2）•一个笑话（英俄翻译）：Thespiritiswillingbutthefleshisweek.（心有余而力不足）Thevodkaisstrongbutmeatisrotten.（伏特加酒虽然很浓，但肉是腐烂的）AI的历史回顾（续3）•出现这样的错误的原因：Spirit：1）精神2）烈性酒•结论：必须理解才能翻译，而理解需要知识AI的历史回顾（续4）•第三阶段（60年代中～80年代初）知识工程时代–专家系统–知识工程–知识工程席卷全球–各国发展计划：•美国星球大战计划•英国ALVEY计划•法国UNIKA计划•日本五代机计划•中国“863”计划AI的历史回顾（续5）•第四阶段（80年代中～90年代初）新的神经元网络时代–BP网（算法），解决了多层网的学习问题–Hopfield网，成功求解了货郎担问题–存在问题：•理论依据•解决大规模问题的能力–新的动向——构造化方法螺旋线分类问题AI的历史回顾（续6）•第五阶段（90年代初～现在）数据与网络时代–网络给AI带来无限的机会–知识发现与数据挖掘–AI走向实用化AI的研究内容•搜索技术•知识表示•规划方法•机器学习•认知科学AI的研究内容（续1）•自然语言理解与机器翻译•专家系统与知识工程•定理证明•博弈•机器人•数据挖掘与知识发现AI的研究内容（续2）•多Agent系统•复杂系统•足球机器人–两个组织：RoboCup和FIRA–模拟组与机器人组–控制方式：FIRA采用集中控制，而RoboCup采用分布式控制•人机交互技术IBM的“深蓝”北京时间1997年5月12日凌晨4点50分，美国纽约公平大厦，当IBM公司的“深蓝”超级电脑将棋盘上的一个兵走到C4的位置上时，国际象棋世界冠军卡斯帕罗夫对“深蓝”的人机大战落下帷幕，“深蓝”以3.5：2.5的总比分战胜卡斯帕罗夫。IBM的“深蓝”（续1）•96年2月第一次比赛结果：“深蓝”：胜、负、平、平、负、负•97年5月第二次比赛结果：“深蓝”：负、胜、平、平、平、胜IBM的“深蓝”（续2）•“深蓝”的技术指标：–32个CPU–每个CPU有16个协处理器–每个CPU有256M内存–每个CPU的处理速度为200万步/秒本课主要学习的内容•产生式系统•搜索技术–盲目搜索方法–启发式搜索方法–与/或图搜索方法–博弈树搜索方法•AI中的谓词演算及应用•知识表示简介•AI中的其它技术介绍第一章产生式系统•1943年Post首先在一种计算形式体系中提出•60年代开始，成为专家系统的最基本的结构•形式上很简单，但在一定意义上模仿了人类思考的过程1.1产生式系统的基本组成•组成三要素：–一个综合数据库——存放信息–一组产生式规则——知识–一个控制系统——规则的解释或执行程序（控制策略）（推理引擎）1.2产生式系统的基本过程过程PRODUCTION1，DATA←初始数据库2，untilDATA满足结束条件，do3，{4，在规则集中选择一条可应用于DATA的规则R5，DATA←R应用到DATA得到的结果6，}一个简单的例子•问题：设字符转换规则A∧B→CA∧C→DB∧C→GB∧E→FD→E已知：A，B求：F一个简单的例子（续1）一、综合数据库{x}，其中x为字符二、规则集1，IFA∧BTHENC2，IFA∧CTHEND3，IFB∧CTHENG4，IFB∧ETHENF5，IFDTHENE一个简单的例子（续2）三、控制策略顺序排队四、初始条件{A，B}五、结束条件F∈{x}求解过程数据库可触发规则被触发规则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，IFDTHENE1.3问题表示举例例1：传教士与野人问题（M-C问题）问题：N个传教士，N个野人，一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。问：如何过河。以N=3，k=2为例求解。M-C问题（续1）左岸右岸LRLRm30m03c30c03B10B01M-C问题（续2）1，综合数据库（m,c,b)，其中：0≤m,c≤3,b∈{0,1}2，初始状态（3，3，1）3，目标状态（结束状态）（0，0，0）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)M-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，控制策略：（略）M-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,0)猴子摘香蕉问题abc猴子摘香蕉问题（续1）1，综合数据库（M,B,Box,On,H）M：猴子的位置B：香蕉的位置Box：箱子的位置On=0：猴子在地板上On=1：猴子在箱子上H=0：猴子没有抓到香蕉H=1：猴子抓到了香蕉猴子摘香蕉问题（续2）2，初始状态（c,a,b,0,0）3，结束状态（x1,x2,x3,x4,1）其中x1～x4为变量。猴子摘香蕉问题（续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为变量1.4产生式系统的特点•数据驱动•知识的无序性•控制系统与问题无关1.5产生式系统的类型•正向、逆向、双向产生式系统•可交换的产生式系统•可分解的产生式系统第二章产生式系统的搜索策略•内容：状态空间的搜索问题。•搜索方式：–盲目搜索–启发式搜索•关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。产生式系统的搜索策略（续1）S0Sg产生式系统的搜索策略（续2）•讨论的问题：–有哪些常用的搜索算法。–问题有解时能否找到解。–找到的解是最佳的吗？–什么情况下可以找到最佳解？–求解的效率如何。2.1回溯策略•例：皇后问题QQQQ()()Q((1,1))()QQ((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((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))()((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))递归的思想从前有座山……从前有座山……从前有座山……递归的思想（续）当前状态目标状态g一个递归的例子intListLenght(LIST*pList){if(pList==NULL)return0;elsereturnListLength(pList-next)+1;}回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。回溯搜索算法递归过程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);存在问题及解决办法•问题：–深度问题–死循环问题•解决办法：–对搜索深度加以限制–记录从初始状态到当前状态的路径回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。回溯搜索算法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);回溯搜索算法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);一些深入的问题•失败原因分析、多步回溯QQ一些深入问题（续）•回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。QQQQ43342.2图搜索策略•问题的引出–回溯搜索：只保留从初始状态到当前状态的一条路径。–图搜索：保留所有已经搜索过的路径。一些基本概念•节点深度：根节点深度=0其它节点深度=父节点深度+10123一些基本概念（续1）•路径设一节点序列为(n0,n1,…,nk)，对于i=1,…