人工智能第二章产生式系统课件

知识表示l知识知识是一切智能行为的基础，也是软件智能化的重要是一切智能行为的基础，也是软件智能化的重要研究对象。要使软件具有智能，就必须使它具有知识，研究对象。要使软件具有智能，就必须使它具有知识，而要使软件具有知识，首先必须解决知识的表示问题。而要使软件具有知识，首先必须解决知识的表示问题。l所谓所谓知识表示知识表示实际上就是对知识的一种描述，即用一实际上就是对知识的一种描述，即用一些约定的符号把知识编码成一组计算机可以接受的数些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。据结构的过程。l一般来说，同一知识可以有多种不同的表示形式，而一般来说，同一知识可以有多种不同的表示形式，而不同表示形式所产生的效果又可能不一样。不同表示形式所产生的效果又可能不一样。5/22/20241常用的知识表示方法l非结构化方法非结构化方法逻辑表示法 QA3,STRIPS,DART,MOMO产生式系统 DENDRAL，MYCINl结构化方法结构化方法框架语义网络l过程式知识表示法过程式知识表示法5/22/20242第二章第二章 产生式系统产生式系统 2.1 产生式系统概述产生式系统概述 一、产生式系统的定义一、产生式系统的定义 产生式系统是人工智能系统中常用的一种程序结构，是一种知识表示系统。通常由以下三部分组成：通常由以下三部分组成：综合数据库综合数据库 产生式规则集产生式规则集 控制系统控制系统5/22/20243综合数据库综合数据库：存放问题的状态描述的数据结构。：存放问题的状态描述的数据结构。Note:综合数据库不是常规意义的数据库，是一种数据结构。综合数据库不是常规意义的数据库，是一种数据结构。一般数据库所存数据的结构很简单，通常只有数值与字一般数据库所存数据的结构很简单，通常只有数值与字符串；综合数据库的数据可以很复杂，其中状态描述可符串；综合数据库的数据可以很复杂，其中状态描述可以为常规的各种数据结构，如表、数组、字符串、集合、以为常规的各种数据结构，如表、数组、字符串、集合、矩阵、矩阵、树、图树、图等等。等等。综合数据库是动态变化的。综合数据库是动态变化的。一、产生式系统的定义一、产生式系统的定义5/22/20244产生式规则形式：产生式规则形式：IF 前提条件前提条件 THEN 操作操作 当规则的前提条件被某一状态描述满足时，当规则的前提条件被某一状态描述满足时，就对该状态施行规则所指出的操作。就对该状态施行规则所指出的操作。一、产生式系统的定义一、产生式系统的定义5/22/20245 控制系统：控制系统：（1）选择规则：）选择规则：对同一个状态的多个可用规则排序。对同一个状态的多个可用规则排序。（2）检验状态描述是否满足终止条件。）检验状态描述是否满足终止条件。如果满足终止条件，则终止产生式系统的运行，如果满足终止条件，则终止产生式系统的运行，并用使用过的规则序列构造出问题的解。并用使用过的规则序列构造出问题的解。一、产生式系统的定义一、产生式系统的定义5/22/20246二、产生式系统的例二、产生式系统的例 八数码难题八数码难题 由由8个标有个标有18的棋子和一个的棋子和一个33的棋盘组的棋盘组成。把成。把8个棋子放在棋盘里，形成一个初始状态，然后个棋子放在棋盘里，形成一个初始状态，然后移动棋子，想办法达到规定的目标状态。在移动棋子时，移动棋子，想办法达到规定的目标状态。在移动棋子时，只能把棋子移进相邻的空格中。只能把棋子移进相邻的空格中。图图2.1 八数码难题的初始状态与目标状态八数码难题的初始状态与目标状态28316475123847655/22/20247八数码难题的产生式系统表示八数码难题的产生式系统表示综合数据库：综合数据库：以状态为节点的有向图。以状态为节点的有向图。状态描述：状态描述：33矩阵矩阵产生式规则：产生式规则：IFThen；IFThen ；IFThen ；IFThen 。控制系统：控制系统：选择规则选择规则:按左、上、右、下的顺序移动空格。按左、上、右、下的顺序移动空格。终止条件：匹配成功。终止条件：匹配成功。5/22/20248三、产生式系统的基本过程三、产生式系统的基本过程Procedure PRODUCTION1.DATA初始状态描述初始状态描述2.until DATA 满足终止条件，满足终止条件，do：3.begin4.在规则集合中，选出一条可用于在规则集合中，选出一条可用于DATA的规则的规则R5.DATA把把R应用于应用于DATA所得的结果所得的结果6.End5/22/20249 步骤步骤4是不确定的，只要求选出一条可用的规则是不确定的，只要求选出一条可用的规则R，至于这条规则如何选取，却没有具体说明。，至于这条规则如何选取，却没有具体说明。选取规则所依据的原则称为控制策略。选取规则所依据的原则称为控制策略。多数人工智能系统控制策略的信息并不足以在多数人工智能系统控制策略的信息并不足以在第第4步选出最合用的规则，因此，控制策略便成了一步选出最合用的规则，因此，控制策略便成了一个搜索过程。个搜索过程。高效的系统需要被求解问题足够的知识，以便在高效的系统需要被求解问题足够的知识，以便在步骤步骤4选出一条最合用的规则。选出一条最合用的规则。第三章，第四章第三章，第四章三、产生式系统的基本过程三、产生式系统的基本过程5/22/202410产生式系统的特点产生式系统的特点一、模块性强。综合数据库、规则集和控制系统相一、模块性强。综合数据库、规则集和控制系统相 对独立，程序的修改更加容易。对独立，程序的修改更加容易。二、各产生式规则相互独立，不能互相调用，增加二、各产生式规则相互独立，不能互相调用，增加 一些或删去一些产生式规则都十分方便。一些或删去一些产生式规则都十分方便。三、产生式规则的形式与人们推理所用的逻辑形式三、产生式规则的形式与人们推理所用的逻辑形式 十分接近，人们具有的知识转换成产生式规则十分接近，人们具有的知识转换成产生式规则 很容易，产生式规则也容易被人们读懂。很容易，产生式规则也容易被人们读懂。DENDRAL和和MYCIN都采用了产生式系统的结构。都采用了产生式系统的结构。5/22/2024112.2 控制策略控制策略 产生式系统的控制策略分为两类：产生式系统的控制策略分为两类：不可撤回的控制策略不可撤回的控制策略 试探性控制策略：回溯方式和图搜索方式试探性控制策略：回溯方式和图搜索方式5/22/202412一、不可撤回的控制策略（瞎子爬山法）一、不可撤回的控制策略（瞎子爬山法）基本思想基本思想 采采用用不不可可撤撤回回控控制制方方式式的的解解题题过过程程类类似似于于盲盲人人爬爬山山过过程程，是是利利用用关关于于每每一一个个状状态态的的局局部部知知识识构构造造全全局局性性解解的的过过程程。在在盲盲人人爬爬山山过过程程中中，无无论论爬爬到到哪哪一一点点，他他总总沿沿着着坡坡度度最最陡陡的的方方向向向向上上爬爬，这这是是局局部部性性的的知知识识，尽尽管管他他事事先先对对爬爬山山路路线线并并不不了了解解，但但只只要要按按照照这这个个原原则则向向上上爬爬，就就一一定定能能爬爬到到某某一一山山顶顶，于于是是确确定定了了一一条条从从山山脚脚到到山山顶顶的的爬爬山山路路线线，也也可可以以说说构构造造出出一一个个具具有有某某种种意意义义下下全全局性的解。局性的解。5/22/202413一、不可撤回的控制策略一、不可撤回的控制策略爬山函数：爬山函数：定义在整个综合数据库上的实数值函数，定义在整个综合数据库上的实数值函数，目标状态有最大的函数值。目标状态有最大的函数值。目目 标：标：爬到山顶。爬到山顶。控制策略：控制策略：应用爬山函数选一规则，使得所选下一状态的应用爬山函数选一规则，使得所选下一状态的爬山函数值不减少且最大（有两个相同的最大值时任选一爬山函数值不减少且最大（有两个相同的最大值时任选一个；若无这样的规则，则终止爬山过程）。个；若无这样的规则，则终止爬山过程）。5/22/202414设爬山函数设爬山函数设爬山函数设爬山函数CF(S)CF(S)：不在目不在目不在目不在目标标位的数位的数位的数位的数码码个数的个数的个数的个数的负值负值。初始状态初始状态初始状态初始状态S S0 0 目标状态目标状态目标状态目标状态S Sg g CF(S CF(S0 0)-4 -4 CF(SCF(Sg g)0 0 状态描述状态描述状态描述状态描述S S：3 3阶方阵阶方阵阶方阵阶方阵4条产生式规则使用顺序：条产生式规则使用顺序：空格左、上、右、下移。空格左、上、右、下移。2831647512384765例：例：八数码难题，不可撤回式控制八数码难题，不可撤回式控制5/22/202415控制策略：控制策略：处于任一状态处于任一状态S，系统根据爬，系统根据爬山函数选择一条规则使得这条规则作用山函数选择一条规则使得这条规则作用于于 S 时，获得的下一状态爬山函数不减时，获得的下一状态爬山函数不减少且最大（亦即距离目标状态最少）。少且最大（亦即距离目标状态最少）。例：例：八数码难题，不可撤回式控制八数码难题，不可撤回式控制5/22/202416 2 8 31 6 4752 8 3147 6 5231 8 47 6 52 31 8 47 6 51 2 38 47 6 51 2 3847 6 5例：八数码难题例：八数码难题 不可撤回式控制不可撤回式控制-4-3-3-1-205/22/202417不可撤回控制策略的优点不可撤回控制策略的优点1.只记录当前一个节点，空间复杂性很低。只记录当前一个节点，空间复杂性很低。2.若能找到解，则速度很快。若能找到解，则速度很快。5/22/202418不可撤回控制策略的局限性不可撤回控制策略的局限性多数情况下找不到解。原因：多数情况下找不到解。原因：(a)爬山函数有多个局部极大值爬山函数有多个局部极大值 例如：例如：目标目标 0 初始初始 -2(b)爬山函数具有爬山函数具有“平顶值平顶值”解决方法：解决方法：设计更好的爬山函数；选多余规则设计更好的爬山函数；选多余规则12374865125748635/22/202419二、回溯控制策略二、回溯控制策略 回溯方式回溯方式是一种试探性的控制策略。（类似深度优先）是一种试探性的控制策略。（类似深度优先）基本思想基本思想 控制系统先选用一条规则，如果发现这条规则的选控制系统先选用一条规则，如果发现这条规则的选用不能导致产生解，则系统用不能导致产生解，则系统“忘掉忘掉”选用规则所涉及选用规则所涉及的步骤和产生的状态，然后选用另外一条规则，重的步骤和产生的状态，然后选用另外一条规则，重新进行试探。新进行试探。5/22/202420回溯方法特点回溯方法特点1.只存储初始节点到当前节点的路径，占用空间较小。只存储初始节点到当前节点的路径，占用空间较小。2.总的时间复杂性无法定论总的时间复杂性无法定论:最好情况复杂性很低：当控制系统掌握较多的有关解的最好情况复杂性很低：当控制系统掌握较多的有关解的知识时，则回溯次数大为减少，效率高。知识时，则回溯次数大为减少，效率高。最坏情况复杂性很高：当控制系统一点也没掌握有关解最坏情况复杂性很高：当控制系统一点也没掌握有关解的知识时，则规则选取是任意的，回溯次数高，效率低。的知识时，则规则选取是任意的，回溯次数高，效率低。为了避免进入无限的境地，设置回溯深度限制强行回溯，为了避免进入无限的境地，设置回溯深度限制强行回溯，问题：太深：效率低；太浅：可能找不到解。问题：太深：效率低；太浅：可能找不到解。3.当深度限制可变时，通常能找到解，是实际用得多、应当深度限制可变时，通常能找到解，是实际用得多、应用最广的一种搜索策略。用最广的一种搜索策略。5/22/202421四条规则使用顺序：左、上、右、下（可加入启发式信息，如使用爬山函数四条规则使用顺序：左、上、右、下（可加入启发式信息，如使用爬山函数安排规则的顺序）安排规则的顺序）深度：深度：6控制策略：回溯式控制策略：回溯式回溯条件：回溯条件：产生了一个上溯到初始状态的路径上出现过的状态时（产生了祖先节点）。产生了一个上溯到初始状态的路径上出现过的状态时（产生了祖先节点）。无可用的规则。无可用的规则。达深度未得解。达深度未得解。2831647512384765八数码难题的初始状态与目标状态八数码难题的初始状态与目标状态例：八数码难题例：八数码难题 回溯式回溯式5/22/2024222 8 31 6 47 5 8 32 6 41 7 58 32 6 41 7 52 8 31 6 4 7 58 32 6 41 7 58 3 42 61 7 58 32 6 41 7 58 6 32 41 7 52 8 3 6 41 7 58 32 6 41 7 58 6 3 2 41 7 5 8 32 6 41 7 58 32 6 41 7 5 八数码问题回溯控制八数码问题回溯控制 8 32 6 41 7 5 （1）（5）（6）（5）（2）（6）（7）（6）（3）（7）（7）（4）（5）（6）5/22/202423三、图搜索控制策略三、图搜索控制策略基本思想：基本思想：从初始状态开始，使用全部可用规则序列。对从初始状态开始，使用全部可用规则序列。对所有的下一步状态每一个再用全部可用的规则，直到目标所有的下一步状态每一个再用全部可用的规则，直到目标状态为止。（类似广度优先搜索策略）状态为止。（类似广度优先搜索策略）搜索树：记录规则的应用和所产生的状态的树结构。搜索树：记录规则的应用和所产生的状态的树结构。树根：初始状态树根：初始状态 有向弧：规则的使用有向弧：规则的使用 除根以外的其它各节点：规则应用的结果除根以外的其它各节点：规则应用的结果 图搜索控制方式不断地扩展搜索树，直到它包括了满足终图搜索控制方式不断地扩展搜索树，直到它包括了满足终止条件的节点为止。止条件的节点为止。5/22/202424图搜索控制策略的特点图搜索控制策略的特点1.不再选择规则，而是使用所有可用的规则，下不再选择规则，而是使用所有可用的规则，下一步选择节点来扩展。一步选择节点来扩展。2.存储所有产生的节点，占用空间大。存储所有产生的节点，占用空间大。3.有解一定能找到（相当于穷举）。有解一定能找到（相当于穷举）。4.平均时间复杂性高，系统效率低。平均时间复杂性高，系统效率低。5/22/202425例：八数码难题例：八数码难题 图搜索式图搜索式2831647512384765八数码难题的初始状态与目标状态八数码难题的初始状态与目标状态书中图：按照深度小的排在前面、优先选择左节点。书中图：按照深度小的排在前面、优先选择左节点。5/22/202426四、产生式系统的工作方式四、产生式系统的工作方式 1.正向产生式系统（数据驱动控制）正向产生式系统（数据驱动控制）：综合数据库：用状态描述综合数据库：用状态描述 产生式规则：产生式规则：F规则规则-状态产生新状态状态产生新状态 从初始状态出发，不断地应用从初始状态出发，不断地应用F规则，直到产生规则，直到产生目标状态为止。目标状态为止。适用条件：初始节点数适用条件：初始节点数目标节点数目标节点数5/22/2024272.反（逆）向产生式系统（目标驱动控制）反（逆）向产生式系统（目标驱动控制）：综合数据库：用目标描述综合数据库：用目标描述 产生式规则：产生式规则：B规则规则 目标产生子目标目标产生子目标 从目标状态出发，利用反向的产生式规则（从目标状态出发，利用反向的产生式规则（B规则规则）不断地产生子目标，直到产生出与初始状态相同的）不断地产生子目标，直到产生出与初始状态相同的子目标为止。子目标为止。适用条件：初始节点数适用条件：初始节点数目标节点数目标节点数5/22/2024283.双向产生式系统：双向产生式系统：正向产生式系统和反向产生式系统结合正向产生式系统和反向产生式系统结合.综合数据库：既有初始状态描述，又有目标状态描述。综合数据库：既有初始状态描述，又有目标状态描述。产生式规则集：既有产生式规则集：既有F规则，又有规则，又有B规则。规则。正向产生式规则用在初始方向的状态描述上，反向产生式规则用在目标描述上。正向产生式规则用在初始方向的状态描述上，反向产生式规则用在目标描述上。控制系统控制系统:判断选判断选F规则还是规则还是B规则；规则；判断已经产生的状态和目标是否能以某种方式匹配，判断已经产生的状态和目标是否能以某种方式匹配，从而满足从而满足结束条件结束条件。结束条件：中间汇合时的状态。结束条件：中间汇合时的状态。适用条件：初始节点数与目标节点数都很多。适用条件：初始节点数与目标节点数都很多。特点：特点：效率高；复杂效率高；复杂。5/22/2024292.3 特殊的产生式系统特殊的产生式系统一、可交换产生式系统一、可交换产生式系统 在某些产生式系统中。规则应用的次序对产在某些产生式系统中。规则应用的次序对产生的状态无影响，即从初始状态到目标状态不依生的状态无影响，即从初始状态到目标状态不依赖规则次序，因此可应用不可撤回式控制策略，赖规则次序，因此可应用不可撤回式控制策略，从而提高了产生式系统的效率，这类产生式系统从而提高了产生式系统的效率，这类产生式系统就是可交换的产生式系统。就是可交换的产生式系统。例：例：基于归结方法的产生式系统基于归结方法的产生式系统5/22/202430 一个产生式系统称为可交换的，如果对任意状态描一个产生式系统称为可交换的，如果对任意状态描述述D具有如下性质：具有如下性质：(a)设设RD是可应用于是可应用于D的规则集，任取的规则集，任取r RD，r作用作用于于D得得 D，设为，设为D=r(D)，则，则r对对D 可用可用(即：设即：设D的可用规则集为的可用规则集为RD，则，则r RD，即，即RD RD)；（每一条对（每一条对D可应用的规则，对于对可应用的规则，对于对D应用一条可应用一条可应用的规则后所产生的状态描述仍是可应用的）应用的规则后所产生的状态描述仍是可应用的）（可应用性）（可应用性）可交换产生式系统定义可交换产生式系统定义5/22/202431(b)设设D满足目标条件，满足目标条件，D的可用规则集为的可用规则集为RD，任，任取取 r RD，用，用r作用到作用到D产生状态产生状态D，D满足满足目标条件。目标条件。（如果（如果D满足目标条件，则对满足目标条件，则对D应应用任何一条可应用的规则所产生的状态描述也用任何一条可应用的规则所产生的状态描述也满足目标条件）满足目标条件）（可满足性）。（可满足性）。5/22/202432（c）设D的可用的可用规则集集为RD，任取，任取 r1,r2,rn RD，依据（，依据（a）将）将r1,r2,rn依次作用到依次作用到D及及产生的状生的状态上，得状上，得状态Dn；设r1,r2,rn 是是 r1,r2,rn的任意一个排列，用的任意一个排列，用r1,r2,rn依次作用到依次作用到D及及产生的状生的状态上，得状上，得状态Dn，则Dn=Dn（对（对D应用一个由可应用于应用一个由可应用于D的规的规则所构成的规则序列所产生的状态描述不因序则所构成的规则序列所产生的状态描述不因序列的次序不同而改变）列的次序不同而改变）(无次序性）。无次序性）。5/22/202433R1R3R1S12S11S0S13S3S2SGS1R3R2R1R2R3R1R2R3R2R1R3R3R2R1R2R3R1可交换的产生式系统例可交换的产生式系统例 R2R3R2R15/22/202434可可交交换换产产生生式式系系统统优优点点：从从初初始始状状态态到到目目标标状状态态不不依依赖赖规规则则次次序序，不不必必探探查查等等价价路路径径，可可以以使用不可撤回策略。使用不可撤回策略。Note：产产生生式式系系统统的的可可交交换换性性并并不不意意味味着着整整个个规规则则序序列列的的次次序序可可以以改改变变。只只是是最最初初作作用用于于给给定状态的那些规则使用起来与次序无关。定状态的那些规则使用起来与次序无关。5/22/202435设产生式系统设产生式系统P：综合数据库，一组规则，图搜索策略：综合数据库，一组规则，图搜索策略造另一可交换的产生式系转换造另一可交换的产生式系转换P如下：如下：1.综合数据库：综合数据库：初始状态：初始状态：P的整个搜索树的整个搜索树 目标状态：只剩解路目标状态：只剩解路转换转换 可用如下方法将一产生式系转换为可交换的可用如下方法将一产生式系转换为可交换的：5/22/202436转换转换 可用如下方法将一产生式系转换为可交换的：可用如下方法将一产生式系转换为可交换的：2.规规则则Ri：若若综综合合数数据据库库中中第第i层层节节点点n不不是是解解路路P上上的的点，则从综合数据库中删除节点点，则从综合数据库中删除节点n。3.控制策略：控制策略：不可撤回式不可撤回式 将将P转换为转换为P，P是可交换的产生式系统是可交换的产生式系统 综综合合数数据据库库变变复复杂杂；规规则则数数目目少少，但但操操作作复复杂杂（如如何判断何判断n不是解路不是解路P上的点）；控制策略简单。上的点）；控制策略简单。5/22/202437二、可分解的产生式系统二、可分解的产生式系统 可交换产生式系统可以避免搜索多余路径可交换产生式系统可以避免搜索多余路径，可，可以使用不可撤回策略。避免搜索多余路径的另一以使用不可撤回策略。避免搜索多余路径的另一种方法是种方法是可分解的产生式系统。可分解的产生式系统。5/22/202438可分解的产生式系统可分解的产生式系统例:字符串重写综合数据库：综合数据库：串节点的有向图串节点的有向图 状态：状态：字符串（或用表）字符串（或用表）初始状态：初始状态：(C,B,Z)产生式规则：产生式规则：R1:IFTHEN （重写规则）（重写规则）R2:IFTHEN R3:IFTHEN R4:IFTHEN 控制系统：控制系统：选择规则：选择规则：用图搜索控制策略用图搜索控制策略 终止条件：终止条件：状态描述仅有状态描述仅有M组成的符号串。组成的符号串。5/22/202439重写问题的解序列（不完整）重写问题的解序列（不完整）R3R3R3R3R3R4R4R3R3R3R2R1R4（C，B，Z）(M,M,M,B,Z)(M,M,M,M,M,Z)(M,M,M,M,M,B,B,M)(M,M,M,M,M,M,M,B,M)(M,M,M,M,M,M,M,M,M,M)(C,B,B,B,M)(B,M,B,B,B,M)(M,M,M,B,B,B,M)(D,L,B,Z)(D,L,M,M,Z)(D,L,M,M,B,B,M)(D,L,M,M,M,M,B,M)(D,L,M,M,M,M,M,M,M)R2R3(B,M,B,Z)5/22/202440Note:1.按照图搜索控制方式在产生终止状态时可能会探索许多完全等价的路径,导致系统的低效。2.从失败路径上浪费很多工作。3.节点的内容之间存在着大量的符号冗余。5/22/202441观察：观察：该产生式系统的该产生式系统的初始状态初始状态可以可以分解分解成成 C,B和和Z，然后把然后把产生式规则分解产生式规则分解使得可应用于这些组成部分：使得可应用于这些组成部分：R1:(C)(D,L)R2:(C)(B,M)R3:(B)(M,M)R4:(Z)(B,B,M)应用规则后所得的结果状态又可以进一步分裂，这样应用规则后所得的结果状态又可以进一步分裂，这样不断地分解，不断地应用规则，直到所产生的状态是不断地分解，不断地应用规则，直到所产生的状态是M字字符为止，即符为止，即终止条件分解终止条件分解为一个为一个M字符作成的状态。字符作成的状态。5/22/202442 重写问题的与重写问题的与/或树或树(C,B,Z)CBZ(D,L)(B,M)(M,M)(B,B,M)DLBM(M,M)MMMMBMB(M,M)(M,M)MMMM R1 R2 R3 R4 R3 R3 R35/22/202443 定义定义 能够把产生式系统综合数据库的能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且规则可以分别用在各组成部分上，并且整个系统的终止条件可以用在各组成部整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统，分的终止条件表示出来的产生式系统，称为称为可分解的产生式系统可分解的产生式系统。可分解的产生式系统可分解的产生式系统5/22/202444Note:对分解出的独立分量的处理方式：对分解出的独立分量的处理方式：可并行处理可并行处理 也可也可串行处理（一般情况下）：串行处理（一般情况下）：（1）按产生的时间排序；）按产生的时间排序；（2）在处理过程中动态排序。）在处理过程中动态排序。5/22/202445可分解的产生式系统的基本过程可分解的产生式系统的基本过程Procedure SPLIT1.DATA 初始状态描述初始状态描述2.Di DATA的分解结果；每个的分解结果；每个Di看成是独立的状态描述看成是独立的状态描述3.until 对所有的对所有的Di Di，Di都满足终止条件，都满足终止条件，do:4.begin 5.在在Di中选择一个不满足终止条件的中选择一个不满足终止条件的D*6.从从Di中删除中删除D*7.从规则集合中选出一个可应用于从规则集合中选出一个可应用于D*的规则的规则R8.D 把把R应用于应用于D*的结果的结果9.di D的分解结果的分解结果10.把把di加入加入Di中中11.end5/22/202446 SPLIT的控制策略：的控制策略：在步骤在步骤5中如何选取中如何选取D*，在步骤，在步骤7如何选取如何选取R。Note：PRODUCTION和和SPLIT是两个比较重要的算法，是两个比较重要的算法，本课的重点之一。本课的重点之一。PRODUCTION的步骤的步骤4：控制策略控制策略 可分解的产生式系统的基本过程可分解的产生式系统的基本过程5/22/202447可分解产生式系统的例子可分解产生式系统的例子 符号积分符号积分SAINT系统，系统，1961年年Slagle提出，提出，1963年对年对SAINT进行改进行改进，达到优秀大学生水平，是一个可分解产生式系统。进，达到优秀大学生水平，是一个可分解产生式系统。输入：不定积分题目；输出：积分的结果函数输入：不定积分题目；输出：积分的结果函数 综合数据库：综合数据库：以字符串以字符串为节点的与或点的与或图 状状态：字符串：字符串 初始状初始状态：用字符串表示的不定：用字符串表示的不定积分分题目（被目（被积函数）函数）产生式规则：产生式规则：分步分步积分分规则、代数替、代数替换、三角替、三角替换等等等等 例如：例如：IFTHEN 控制系统：控制系统：选择规则：选择规则：图搜索搜索 终止条件：终止条件：与系与系统内部保存的基本内部保存的基本积分表中的函数具有相同的形式分表中的函数具有相同的形式。如：如：udu=u2/2 5/22/202448三角恒等式三角 恒等式z=z=z=用分母除分子-z=5/22/202449学科前沿讲座学科前沿讲座皇帝的新脑还是人类的终结皇帝的新脑还是人类的终结5/22/202450 一、关于人工智能一、关于人工智能5/22/202451 一、关于人工智能一、关于人工智能5/22/202452l从数值计算文字、图像等多媒体信息处理初步实现了Leibniz提出的“将人的思维机器化”的思想l让机器拥有人的心智成为计算机专家梦寐以求的理想！1956年，M.L.Minsky，C.Shanon，J.McCarthy(人工智能之父)等在美国达德茅斯大学召开第一届人工智能学术会议。会上首次使用“人工智能”这一术语。标志着人工智能学科的诞生。一、关于人工智能一、关于人工智能5/22/2024531950年，W.格雷.瓦尔特，可以自己充电的“乌龟”1960年，K.M.柯尔，模拟了一个精神病疗法专家电脑下棋方面，97年的“深蓝”(Deep Blue)，03年的“小深”(Deep Junior)一、关于人工智能一、关于人工智能5/22/202454l医生：我可以为你效劳吗l病人：我不知道l医生：请告诉我一些情形l病人：不l医生：请你说得仔细些l病人：今天我厌烦得很l医生：你知道这是什么原因l病人：是的我老了l医生：请继续讲l病人：仿佛任何事情都激不起我的兴致l医生：请更多地告诉我你的这种感觉l病人：我也有些知道为何我会这样感觉l医生：是吗l病人：我似乎在想有一个家l医生：什么东西使你有这样的想法l病人：它是一种挑战l医生：为什么那对你是重要的5/22/202455二、电脑能否实现人的智能？二、电脑能否实现人的智能？l机器ll体力l电脑ll计算速度和准确性l人脑ll思维l是否电脑能代替人脑实现智能？l一旦能够实现，这种被认为是特权的智能行为将受到挑战。5/22/202456 二、电脑能否实现人的智能？二、电脑能否实现人的智能？5/22/202457二、电脑能否实现人的智能？二、电脑能否实现人的智能？5/22/202458 二、电脑能否实现人的智能？二、电脑能否实现人的智能？l人真实地回答问题并试图说服质问者，他确实是人；l电脑被编好“说谎”的程序，试图说服质问者它是人。5/22/202459三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：5/22/202460三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：l爱因斯坦曾经将其比喻为“与上帝的对话”5/22/202461三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：5/22/202462 三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：5/22/202463四、对人工智能领域有影响的理论与书籍四、对人工智能领域有影响的理论与书籍5/22/202464 四、对人工智能领域有影响的理论与书籍四、对人工智能领域有影响的理论与书籍l推荐网址lhttp:/ 四、对人工智能领域有影响的理论与书籍四、对人工智能领域有影响的理论与书籍l镶嵌图案 埃舍尔的版画(1957)5/22/202466四、对人工智能领域有影响的理论与书籍四、对人工智能领域有影响的理论与书籍5/22/202467问题求解逻辑推理与定理证明自然语言理解自动程序设计专家系统机器学习神经网络机器人学五、目前人工智能的研究与应用领域五、目前人工智能的研究与应用领域模式识别机器视觉智能控制智能检索智能调度与指挥分布式人工智能与Agent计算智能与进化智能数据挖掘与知识发现5/22/202468 六、计算机视觉中的困惑六、计算机视觉中的困惑l这些与人类视觉活动相比，显得微不足道。l人类视觉中的视觉含义的把握以及主观经验在视觉中的作用，使机器不可能拥有的。5/22/2024695/22/202470六、计算机视觉中的困惑六、计算机视觉中的困惑5/22/202471六、计算机视觉中的困惑六、计算机视觉中的困惑5/22/202472 六、计算机视觉中的困惑六、计算机视觉中的困惑5/22/202473六、计算机视觉中的困惑六、计算机视觉中的困惑l著名的混沌理论“蝴蝶效应”：美国气象学家洛伦芝（Lorenz）于1960年代提出一篇论文，名叫一只蝴蝶拍一下翅膀会不会在德克萨斯州引起龙卷风？，他说，亚马逊流域的一只蝴蝶扇动翅膀，会掀起密西西比河流域的一场风暴。洛伦芝把这种现象戏称做蝴蝶效应，意思即一件表面上看来毫无关系、非常微小的事情，可能带来巨大的改变。5/22/202474六、计算机视觉中的困惑六、计算机视觉中的困惑l眼睛和大脑的组合并不只具有“摄像机”般的功能。l虽然，人们对“视觉理解”发生的机制还不太清楚，但可以肯定其中含有非线性突变的因素，而且导致某种结果的因素是不确定的。（即蝴蝶效应）l“视觉理解”中抹不去的主观因素不可能通过确定的算法给出。5/22/202475七、展望七、展望l在计算机上要实现人的心智，充满困境。l要冲破这一困境，必须有理论性的突破：l大自然的机理+算法5/22/202476 七、展望七、展望l问题的解决不依赖于复杂的逻辑运算，而是利用装置本身的复杂性功能。5/22/202477七、展望七、展望l大自然的机理+算法l目前，在计算原理和模式方面出现了一些新的尝试：p生物计算p量子计算p光子计算p5/22/202478