《人工智能》复习大纲

1、人工智能应用技术复习大纲一、人工智能概述略二、谓词公式与逻辑推理定义2.1 命题(Proposition)，即具有真(T)假(F)意义的陈述性语句。定义2.2 所谓个体，是指可以独立存在的某个事物。 定义2.3 谓词：由定义的谓词名、变元，共同构成了具有陈述性表达的形式化语句，称为谓词。一个谓词可以有n（其中n=0,1,2, ）个变元，并称之为n元谓词。定义2.3 谓词中包含个体或变元的数目，称为谓词的元或谓词的目。定义2.4 谓词表达形式中所包容相叠加的含义层次数数目，称为谓词的阶。例2-2 比较下列谓词或谓词形式的命题：LIKE(john，mary)；ROBOT(john)；ROBOT(m

2、ary)； ADDQ(x，y，z)。试解释具体含义，并指出它们各是几元谓词。解：上述谓词意即“机器人约翰喜欢玛丽”；和都只有一个个体，称为一元谓词；相应则称为二元谓词；表示为表达式“x+y=z”，其中包含有3个变元，故称为三元谓词。依此类推，可推出关于n元谓词的概念。例2-3 为了说明谓词的阶，我们来比较下列谓词形式的命题：LIFELESS(outer-stars)；外星球没有智能生命。INCORRECT(lifeless(outer-stars)；说“外星球没有智能生命”是不确切的。解：在上述谓词形式的命题中，谓词只有一层含义，称为一阶谓词；谓词在前一层含义基础上，又增加了一层新意，共有二层

3、含义。故把谓词称为二阶谓词。依此类推，可推出关于n阶谓词的概念。注意：在谓词逻辑演算中，最重要的有三大类：即：命题逻辑演算、 一阶谓词逻辑演算和二阶谓词演算。 命题逻辑表示比较简单，只能表达具体固定的情况，命题是谓词逻辑特殊事例的生动描述，谓词逻辑可以灵活表现多种或变化的情况；谓词表达是命题逻辑的抽象与推广。总的看来，命题和谓词的知识表示形式可以相互转换，而谓词比命题有更强的表达能力。显而易见，谓词是一种描述个体群之间的相互关系、性质及其逻辑结构的数学表示。人们把采用这种表示的运算，又称为谓词逻辑。比较起来：命题逻辑演算太简单，只能解决具体容易的问题；二阶谓词演算又太复杂，以至迄今为止，尚未找

4、到最根本有效的算法。因此，在人工智能中，目前使用最多的还是一阶谓词逻辑演算。n 表2-1 连接词定义真值表 P Q ¬P PQ PQ PQ P«Q F F T F F T T F T T T F T ? F T F F T F F F T T F T T T T2.1.3命题和谓词逻辑举例 例： 小张既聪明，又勤奋，所以他的学习成绩一直很好。P：小张聪明Q：小张勤奋R：小张学习成绩一直很好n （ P Q） R小王总是在图书馆看书，除非他病了或图书馆不开门。P：小王病了Q：图书馆开门R：小王在图书馆看书n ¬ （ P ¬ Q） « R若张先生是小

5、张的父亲，则小张是王太太的儿子。解：先设定谓词，再设定变元，并将变元代之以常量，用连接词运算符连接并加以描述：设定谓词：FATHER (x,y)： x是y的父亲 SON (y,w)： y是w的儿子 常量： z 表示张先生；mz 表示小张；wtt王太太则可描述为： FATHER (z, mz) SON (mz, wtt)（2）若x是小张的父亲，且y是小张的兄弟，则x也是y的父亲。解：先设定谓词，再设定变元，并将变元代之以常量，用连接词运算符连接并加以描述：设定谓词：FATHER (x,y)： x是y的父亲 BROTHER (y,w)： y是w的兄弟 常量： mz 表示小张则可描述为： FATHE

6、R (x, mz) BROTHER (y, mz) FATHER (x, y) （3）*在那遥远的地方，有位好姑娘，人们走过她的身旁，都要回头留恋地张望。解： (彐x)好姑娘(x)居住的地方(z，x) 遥远的(z)("y)人(y)行走经过(y, z) 回头留恋地张望(y)例4.1 设已知下述事实：A；B；AC；BCD；DQ. 求证：Q为真。 证明： A，AC Þ C (P规则及假言推理) B，C Þ BC (引入合取) BC，BCD Þ D (T规则及假言推理) D，DQ Þ Q (T规则及假言推理) Q为真 (证毕)例4.2 设已知如下事实：

7、 （1）凡是容易的课程小王（Wang）都喜欢； （2）C班的课程都是容易的； （3）ds是C班的一门课程. 求证：小王喜欢ds这门课程. 证明：首先定义谓词： EASY（x）x是容易的课程； LIKE（x，y）x喜欢y课程； C（x）x是C班的一门课程.已知：EASY（x）LIKE（Wang，x） ("x)（C（x）EASY（x） C（ds） 求证：LIKE（Wang，ds） 证明：可应用推理规则进行推理证明。 由，得("x)(C(x)EASY(x) C(y)EASY(y) （全称固化） 由，得C(ds)，C(y)EASY(y) Þ EASY(ds) (P规则及假

8、言推理) EASY(ds),EASY(x)LIKE(Wang，x) Þ LIKE(Wang，ds) (T规则及假言推理) 即小王喜欢ds这门课程。 (证毕)例4.3 设已知 （1）凡是人喜欢吃的东西狗也喜欢； （2）jasper是一条狗； （3）有人喜欢啃骨头. 求证： jasper喜欢啃骨头. 证明：首先定义谓词： DOG（x）x是狗； xjasper，狗， LIKEEAT（y，z）y喜欢吃（啃）z ； yjasper，人， zbones，肉，鱼，则得已知条件： ("x)("z)LIKEEAT（人，z）DOG（x） LIKEEAT（ x ，z） DOG（jasp

9、er） LIKEEAT（人，bones） 求证： LIKEEAT（jasper，bones） 证明：代入得("z)LIKEEAT（人，z）DOG（jasper） LIKEEAT（jasper，z） （全称固化） 代入得LIKEEAT（人，bones）DOG（jasper） LIKEEAT（jasper，bones ） 由为真，得 LIKEEAT（人，bones）DOG（jasper） =T （引入合取词） 由为真，得 LIKEEAT（jasper，bones）= T (P规则及假言推理) 即jasper喜欢啃骨头.(证毕)谓词公式概念复习与扩充： 使用连接词和量词，把若干谓词连接组合

10、在一起，就得到了谓词逻辑公式(PLF：Predicate Logic Formula)的表达。下面我们给出谓词公式的相关各种概念与定义。定义2.5 仅能表达单一意义且不可再细划分的简单命题称为原子命题。例如，一阶零元(目)命题、一阶一元命题、一阶二元命题等都是原子命题。定义2.6 用连接词或者量词把若干原子命题联结组合在一起，就得到了命题公式(PF：Proposition Formula)，又称之为命题合式公式。定义2.7 采用参量变元来替代命题合式公式中的常量，就得到了原子谓词公式，又称之为谓词合式公式（PWFF：Predicate Well-Formed Formula），简称合式公式或W

11、FF。三、状态空间表示法 例1-1 设有三枚钱币，分别处在“正”、“反”、“正”状态。每次只能且必须翻一枚钱币。问连翻三次后能否达到三枚全朝上或全朝下的状态？首先应把问题形式化。设正面表示为1，反面表示为0，可引入一个三元组Q= (q0,q1,q2)来描述这三枚钱币的状态，每个qi的取值为0,1，因此共有23=8种不同的状态。这8种状态列举如下：；于是问题就变为如图1-4所示。图1-4 例1-1的问题示意接着应找出所有能改变状态的操作。这里翻动一枚钱币就称为一种操作，则共有3种操作，即F=a,b,c。其中，a表示将钱币q0翻转一次，b表示将钱币q1翻转一次，c表示将钱币q2翻转一次。如图1-5

12、所示是此问题的全部状态空间图。图1-5 三枚钱币的状态空间图图1-5中结点表示状态，有向边表示操作，双向箭头表示两个状态在同一操作下是可逆的，这样可以为三次操作提供方便。从图1-5中可以看出，从Qs=Q5出发，不可能通过三次操作到达Q0=Qg1，这说明从Q5到Q0之间没有所要求的解；而从Q5出发到达Qg2=Q7有7种操作序列，因而有7个解，它们是aab，aba，baa，bbb，bcc，cbc和ccb。例6-1设有分别由开关控制的一字排开的3盏信号灯，处在“亮、暗、亮”的初始状态。每次操作允许并必须扳动一只开关，问：如果连扳三次开关后，是否可以出现错“亮、亮、亮”或“暗、暗、暗”的状态？解:首先

13、将该问题形式化：设开关“off”灯为“暗”，以0表示；开关“on”灯为“亮”，以1表示；再分别用A、B、C标识3盏灯亮或暗的状态。这样，可引入一三元数组Sk=（A,B,C）来描述这3盏信号灯的总状态。全部可能的状态计有8种： S0 =（0,0,0）, S1 =（0,0,1）,S2 =（0,1,0）, S3 =（0,1,1）, S4 =（1,0,0）, S5 =（1,0,1）,S6 =（1,1,0）, S7=（1,1,1）. 这里，初始状态一个： S =S5=（1,0,1）；目标状态有2个： G =S0，S7=（0,0,0），（1,1,1）状态的操作数，共3个，F =a,b,c,分别表示把各灯开

14、关扳动一次 ；问题的状态空间可写成S5,a,b,c,S0，S7.教材中图6-3表示了全部可能的状态及其相互关系。 （0，0，0）（1，0，0）（0，0，1）（1，0，1）（1，1，0）（1，1，1）（0，1，0）（0，1，1）aaabbbbcccca其中S5是初始状态，S0和S7都是目标状态。从图中我们可以清楚地看出：从S5经过三步搜索不可能恰好到达S0，即不存在从S5到达S0的解；但从S5出发搜索，到达S7的路径有7条，它们的动作序列分别为aab、aba、baa、bbb、bcc、cbc和ccb等，共有七组解。 由上述利用状态空间图求解的举例，对具体问题搜索求解可总结为如下的思路和步骤：（1）

15、设定状态变量及确定值域；（2）确定状态组，分别列出初始状态集和目标状态集；（3）定义并确定操作集； （4）估计全部状态空间数，并尽可能列出全部状态空间或予以描述之；（5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。 例6-2 传教士和野人问题（The Missionaries and Cannibals Problem）。在河的左岸有三个传教士、一条船和三个野人，传教士们想用这条船将所有的成员都运过河去，但是受到以下条件的限制：传教士和野人都会划船，但船一次最多只能装运两个；在任何岸边野人数目都不得超过传教士，否则传教士就会遭遇危险：被野人攻击甚至被吃掉。此外

16、，假定野人会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。例1-2 修道士和野人问题。在河的左岸有3个修道士、3个野人和1条船，现在要渡河到右岸，但有如下限制条件：（1）船最多坐2人，修道士和野人都会划船。（2）在任何岸边野人人数都不能超过修道士人数，否则修道士就会被吃掉。请规划出一个安全的渡河方案。解：我们按上述步骤来进行求解分析。（1）设定状态变量及确定值域。为了建立这个问题的状态空间，设左岸传教士数为m，则 m =0,1,2,3；对应右岸的传教士数为3m； 左岸的野人数为c，则有 c =0,1,2,3； 对应右岸野人数为3c；左岸船数为b，故又有b=0,1，右岸的船数为1

17、b.（2）确定状态组，分别列出初始状态集和目标状态集。 问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即 Sk =（m,c,b），右岸的状态可以不必标出。初始状态一个： S0 =（3,3,1），初始状态表示全部成员在河的左岸；目标状态也只一个： Sg =（0,0,0），表示全部成员从河左岸渡河完毕。（3）定义并确定操作集。 仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中,第一下标i表示船载的传教士数, 第二下标j表示船载的野人数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。则共有10种操作，操作集为 F=P01，P10，P11，P02，P20，Q0

18、1，Q10，Q11，Q02，Q20（4）估计全部的状态空间数，并尽可能列出全部的状态空间或予以描述之。 在这个问题世界中，S0 =（3,3,1）为初始状态，S31 = Sg =（0,0,0）为目标状态。全部的可能状态共有32个，如表6-1所示。表6-1传教士和野人问题的全部可能状态状态m,c,b状态m,c,b状态m,c,b状态m,c,bS0 3 3 1 S8 1 3 1 S16 3 3 0 S24 1 3 0S1 3 2 1 S9 1 2 1 S17 3 2 0 S25 1 2 0S2 3 1 1 S10 1 1 1 S18 3 1 0 S26 1 1 0S3 3 0 1 S11 1 0 1

19、S19 3 0 0 S27 1 0 0S4 2 3 1 S12 0 3 1 S20 2 3 0 S28 0 3 0S5 2 2 1 S13 0 2 1 S21 2 2 0 S29 0 2 0S6 2 1 1 S14 0 1 1 S22 2 1 0 S30 0 1 0S7 2 0 1 S15 0 0 1 S23 2 0 0 S31 0 0 0注意：按题目规定条件，应划去非法状态，从而加快搜索效率。 1）首先可以划去左岸边野人数目超过传教士的情况，即S4、S8、S9、S20、S24、S25等6种状态是不合法的； 2）应划去右岸边野人数目超过修道士的情况，即S6、S7、S11、S22、S23、S27

20、等情况；3）应划去4种不可能出现状态：划去S15和S16船不可能停靠在无人的岸边；划去S3传教士不可能在数量占优势的野人眼皮底下把船安全地划回来；划去S28传教士也不可能在数量占优势的野人眼皮底下把船安全地划向对岸。可见，在状态空间中，真正符合题目规定条件的只有16个合理状态。 （5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。 根据上述分析，共有16个合法状态和允许的操作，可以划出传教士和食人者问题的状态空间图，如图6-4所示。300311110020221031010111000021011331310321220320S18 S24 S12 S10 S0

21、 S17 S1 S2 20 S29 02 S30 S14 S31S21 S19 S5 S13 图6-4 传教士和野人问题的状态空间图：四、搜索技术基本搜索策略主要分为四种类型：即1. 宽度优先搜索;2. 深度优先搜索;3. 有界搜索;4. 代价推进搜索。2.1 宽度优先搜索(Breadth-first Search)又称为广度优先搜索或横向优先搜索，顾名思义，即搜索任务是按照横向逐步扩展向前推进而完成的。图6-10 宽度优先搜索过程之一 为了用算法来实现其搜索过程，需要预先建立两个表，分别称为OPEN表及CLOSED表。OPEN表：只用来登记存放新生成并待扩展的节点，不保留已扩展及已被考察的节

22、点；CLOSED表：用来存放已扩展并已被考察的节点，即登记已经完成的搜索路径。一般对于不同的搜索策略，在OPEN表中节点排列的顺序是不同的。这里约定，OPEN表中按节点生成及进入的先后的顺序排列，先生成的节点排在前面，后生成的节点排在后面，并实行先进先出(FIFO)的算法来进行搜索。n 宽度优先搜索过程可用图6-11的工作流程来表示。其步骤为：开始把S0送入OPEN表OPEN空？ 把OPEN表的第一个节点（节点n）从表中移出，放入CLOSED表节点n为目标节点？节点n可扩展？扩展节点n，将其子节点放入OPEN表，并为每个子节点配置指向n的指针成功，退出失败，退出YNYNYN宽度优先搜索流程示意

23、图（1）把初始节点S0放入OPEN表；（2）如果OPEN表为空，则问题无解，退出。（3）把OPEN表的第一个节点（记为节点n）取出放入CLOSED表；（4）考察节点n是否为目标节点。若是，则求得了问题的解，退出。（5）若节点n不可扩展，则转第（2）步。（6）扩展节点n,将其子节点放入OPEN表，并为每一个子节点都配置指向父节点的指针，然后转第（2）步 其得到的搜索的路径为：S0S1S2S11S12S21S22S111S112S113S121S122（Sg.）n 算法特点：显然，宽度优先搜索法是一种遵循规则的盲目性搜索，它遍访了目标节点前的每一层次每一个节点，即检查了目标节点前的全部的状态空间点

24、，只要问题有解，它就能最终找到解，且最先得到的将是最小深度的解。可见，宽度优先搜索法很可靠。但是，当目标节点距离初始节点较远时将会产生许多无用的中间节点。因此，速度慢，效率低，尤其对于庞大的状态空间实用价值差。2.2 深度优先搜索(Depth-first Search)又称为纵向优先搜索，顾名思义，即搜索任务是按照纵深方向，逐级地向下跨越推进而完成的。深度优先搜索的基本方法为：从根节点S0开始，始终沿着纵深方向搜索，总是在其后继子节点中选择一节点来考察。若到达目标节点Sg，则搜索成功；若不是目标节点，则再在该节点的后继子节点中选一考察，一直如此向下搜索，直到搜索找到目标节点才停下来。若到达某个

25、子节点时，发现该节点既不是目标节点又不能继续扩展，就选择其兄弟节点再进行考察。依此类推，直到找到目标节点或全部节点考察完毕，搜索过程才可以终止或结束。 例6-5如图6-14所示，设法使用深度优先搜索过程算法，寻找出从S0到达Sg的搜索路径。 S0 S1 S2 S11 S12 S21 S22 S111 S112 S113 S121 S122 S211 S212 S221 S222S2212=Sg 解：假设图中所标记的是全部的搜索树。我们采用的一种深度优先搜索过程算法是：发生器函数Q(x)按照每一层节点从左至右的优先级，并按照“最晚生成的节点优先扩展”并优先考察搜索的原则。这里，就可获得一种先扩展

26、(包括括号内、外的节点)，再既而完成考察与搜索(不用括号的节点)，其路径为：S0(S1)S2(S21)S22(S221)S222 (S2221)S2222S2221S221(S2211)S2212=Sg. 针对教材中图6-12所示的重排九宫问题，按照上述“最晚生成的节点优先扩展”并优先考察搜索的原则，如图6-15所示，则得到的搜索路径是：S0=159132122，这里还只是搜索树的一部分，尚未到达目标Sg ；而沿着分枝S0=1361014= Sg路径的深度优先搜索，却可以高效率到达目标节点。可见深度优先搜索的效率将随着选择路径的不同而具有较大的区别。 看起来深度优先搜索算法流程与宽度优先搜索算

27、法过程几乎完全相同。其主要区别在于采用的OPEN表结构不同：深度优先搜索OPEN表，实行的是后进先出(LIFO) 的算法进行搜索；这与宽度优先搜索算法实行先进先出(FIFO)的算法不同。深度优先搜索的特点：方式灵活，规则易于实现，对于有限状态空间并有解时，必能找到解。例如，当搜索到某个分支时，若目标节点恰好在此分支上，则可较快地得到解。故在一定条件下，可实现较高求解效率。但是，在深度优先搜索中，一旦搜索进入某个分支，就将沿着该分支一直向下搜索。这时，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。可见，深度优先搜索算法不完备，风险大，易于掉入陷阱。因此，要使深度优先搜索算

28、法可用，必须加以改造。2.3 有界搜索为了避免深度优先搜索过程陷入无穷分支的死循环，人们又提出了有界深度优先搜索算法基本思想：设定一个搜索深度的界限dm ，当搜索深度达到dm ，而尚未出现目标节点时，可回朔换一个分支进行搜索，直到dm的深度内所有分支节点搜索完毕。有界深度优先搜索过程可概括为：（1）把初始节点S0放入OPEN表中，置S0的深度d(S0)=0；（2）如果OPEN表为空，则问题无解，退出。（3）把OPEN表中的第一个节点（记为节点Sn）取出放入CLOSED表；（4）考察节点Sn是否为目标节点。若是，则求得了问题的解，退出。（5）如果节点Sn的深度d（Sn）= dm 或节点Sn不可扩

29、展，则转到第（2）步；（6）扩展节点Sn，将其子节点放入OPEN表的首部，并为其配置指向父节点的指针，然后转到第（2）步。基本搜索策略的局限性及其特点 概括起来，广度优先搜索、深度优先搜索、有界深度优先搜索和代价推进搜索法等，它们的局限性及其特点为：基本搜索策略普遍适用于树状问题求解，控制性知识简单，容易编程在计算机上实现。但是，它表现出来的缺点也很突出：一般必须知道问题的全部状态空间，搜索效果差，求解能力弱，故常被称为弱方法。 它们都是依据某种固定规则运行的搜索，均属于非启发的强力搜索，没有表现出智能搜索的活跃性与灵活性。也就是说，问题搜索树的生成、扩展以及节点接受考察的次序等，都是由生硬死

30、板的搜索方法决定的，而不由具体问题状态信息引导与经验分析来决定；由于基本搜索策略疏忽了对给定问题的特有知识的分析,没有充分考虑所要求解问题的自身发展规律和特性，搜索完全是按事先确定好的固定排序来进行的，这是一种穷尽遍历的大海捞针式的策略，没有任何启发式信息引导，往往使得实际搜索效率很低，故又被称为盲目搜索。 2.4 启发式搜索所谓启发式搜索（Heuristic Search）策略,即利用与问题解有关的启发信息来作引导的搜索策略。搜索效率及其评价：有一种比较直观的评价搜索效率的方法，其定义公式为： P=L/T （6-4）L是从根节点到达目标节点的深度；T是在整个搜索过程中产生节点总数(不计根节点

31、)，因此，这里P反映的是朝着目标搜索时的搜索宽度。 讨论：搜索效率定义公式为： P=L/T一般情况下，P1 因为总有TL；）当L=T时，则 P=L/T=1，表示搜索过程中每次只生成一个节点，并且它恰好是解路径上的节点，表示了一种以单枝延伸的搜索树。这时，启发能力最强，效率最高，即所扩展的每一个节点都落在最佳路径上，称为最佳搜索。 当P=L/T1，几近于零，没有任何控制性知识作依据，搜索中的每一步都是完全随意而进行的，称为随机搜索；通常搜索总是介于01之间。因此，为了快速地找到问题的解，总是使搜索尽可能利用启发信息，努力使搜索路径的每一步都尽可能与最佳搜索路径重合一致，以便实现更高的搜索求解效率

32、。启发式搜索的主要特点是：由于充分考虑到问题求解所应用到的各种启发信息及知识，包括利用常识性推理和专家经验等信息与知识，启发式搜索能够动态地确定操作排序，优先调用较合适的操作规则，扩展、比较并选择最有希望的节点，使搜索尽可能以最快的速度，最短的距离，最小的代价，朝着最有利于达到目标节点的方向推进。即以智能思想调节搜索区，使尽量沿着最有希望找到解的路径方向上，纵向小范围地搜索前进。所谓估价函数，是指从问题树根节点到达目标节点的搜索中，所要耗费全部代价的一种估计值，记为f (n)。n 估价函数以数学公式形式可表达为： f(n)=g(n)+h(n) （6-5） 其公式中各部分表达的意义如下：n f

33、(n)：表示从根节点So出发，经过当前节点Sn，到达目标节点Sg已耗费及将要耗费代价总和的估计值。n g (n)：表示从根节点So，在到达目标节点Sg的搜索路径上，已到达当前节点Sn，g (n) 即表示从SoSn已耗费的代价。n h (n)：指从当前节点Sn，预测估计到达目标节点Sg，将要耗费的可能代价。也就是说，h（n）表示了SnSg这一路径搜索段上将要耗费代价的可能值。称之为启发函数。讨论：h(n)=0，则f(n)= g(n) 表示没有任何启发信息的作用，该搜索也就简化为基本搜索，又称为盲目搜索或“弱” 搜索方法。可见，从某种意义上来说，基本搜索亦是普通搜索的一种特例。 2.4.1 瞎子爬

34、山法n 瞎子爬山过程：每搜索到达一个节点，其随后选择的下一节点不是按规则预定的或盲目选定的，而是按经验进行智能处理，使用估计函数f(x)来搜索当前最优的节点。n 在实现瞎子爬山的局部择优搜索法中，可取消OPEN表，每次扩展后只保留符合估价函数f(x)的最优子节点N，而将其它子节点全部丢掉，N下一次扩展的节点，可直接放入CLOSED表中。依次步步为营，搜索求解，直到到达目标节点Sg为止。显而易见，局部择优搜索是对深度优先搜索方法的一种改进。由于它每次都只是在子节点的范围内选择下一个要考察的节点，范围较窄，所以称为局部择优搜索。n 估价函数: f(n)= g(n)+ h(n)，n 其中启发函数 h

35、(n)=grad H(r)，即为高度函数H(r)梯度的绝对值。n 其生成函数按选择方向深度搜索，逐点生成。瞎子爬山法的主要特点n 瞎子爬山法在许多情况下是有效的。n 优点:方法简单，由于取消了OPEN表，要处理的数据量减少了，所以占用内存空间少、速度快。n 缺点:但瞎子爬山法主要只在单因素，单极值的情况下使用，而在多极值情况下会遇到许多困难，导致找不到最佳解。n 例如在二维或三维的情况下，就会遇到“多峰”问题、“盆地”或“平台”、“山脊”问题等，使搜索失败（见图6-21）。 瞎子爬山法的局限性n 所谓“多峰”问题：数学多局部极值问题，即发现使一阶导数（或偏导数）为零的节点有好几个，导致瞎子有可

36、能只爬上某个次高峰而误以为是最高峰；n 所谓“盆地”或“平台”问题：指周围都是平地，使得导数处处为零，搜索无所适从而不知道选择那个前进方向才能获得最佳效果；n “山脊”问题：指搜索区域因断层而形成一条凸起连接，使得一阶导数不连续，前后左右遇到的都是斜率减小方向而误以为到达了目的地。2.4.2 全局择优搜索法n 进行全局择优搜索时，要求仍然保留OPEN表。在这种方法搜索中, 每当要选择一个节点进行考察时,首先总是依照次序来比较OPEN表中所有节点的估价值，设法从中选择一个估价值最小或最优的节点来搜索求解；n 其次，若有多个解路径存在时，要依照次序来比较每个解路径的代价值，以便从中找到总代价最小的

37、搜索解路径，即尽可能得到最优解。全局择优搜索又称为有序搜索法。n 全局择优搜索的搜索过程如下:(1) 把初始节点So放入OPEN表,计算f(So)；(2) 如果OPEN表为空,则转到步(8)。 (3 )把OPEN表中的第一个节点(记节点n)从表中移出，放入CLOSED表；(4) 考察节点n是否为目标节点。若是,则成功得到问题的一个解,标记其解路径。并标记目标节点顺序，记为Sgk,转步(2)，以便搜索下一个解。(5) 若节点n不可扩展,则转步(7)。(6) 扩展节点n,用估价函数f(n)计算每个子节点的估价值,并为每个子节点配置指向父节点的指针,把这些子节点都送人OPEN表中,然后对OPEN表中

38、的全部节点按估价从小至大进行排序；(7) 转步(2)；(8) 分别计算每一个目标节点的代价值，按照代价值从小至大进行排序。则排在最前面的目标节点优于排在后面的目标节点。2.5 与/或树、搜索树及其解树 n 与/或树(And/Or Trees)：是树表达的推广，与/或图的特例。问题的状态可以借用树及其根、枝、叶等名称来表示；也可按照祖先与后代诸如子、孙等层次或辈份关系来定义。其中根节点是唯一的，辈份最高；叶是端节点，辈份最低。枝、干及其分枝介于根与叶之间。n 与树：把一个难于直接求解的复杂问题分解为若干个比较简单的子问题，各个子问题的全部解决等价为该问题的解决；而对于困难的子问题求解，同样依照这

39、种方法处理。这样就形成了一种与结构的关系树，称之为与树；并把相关节点及其边用一弧线连接，称之为与关系表示。如下图所示，其S0节点及其子节点所形成的分枝树的结构关系。n 或树：使用类似的思想方法，我们可以引出或树的概念。也就是说，把一个难于直接求解的问题分解为若干个与之等价而又更简单的子问题，每个子问题的解决等价为该问题的解决，就形成了一种或结构的关系树，称之为或树。或关系树的表达可以不必特别加以标志。n 与/或树：如果问题状态空间既有或结构，又有与结构的复合关系，就得到了与/或混合树，简称与/或树，如上图6-25所示。若把前面所研究的搜索策略再应用于与/或树，自然也就形成了与/或树全部的搜索策

40、略了。 与树及其表示S S S S S S S1 S1 S1 S11 S S1S11 S113 S S11 五、神经网络一般地,人工神经元的结构模型如图3所示。 它是一个多输入单输出的非线性阈值器件。其中 x1，x2，xn表示神经元的n个输入信号量； w1，w2，wn表示对应输入的权值,它表示各信号源神经元与该神经元的连接强度； A表示神经元的输入总和,它相应于生物神经细胞的膜电位,称为激活函数;y为神经元的输出;表示神经元的阈值。 函数y=f(A)称为特性函数(亦称作用函数或传递函数)。特性函数可以看作是神经元的数学模型。如果将多个神经元按某种的拓扑结构连接起来，就构成了神经网络。 根据连接

41、的拓扑结构不同，神经网络可分为四大类：分层前向网络、反馈前向网络、互连前向网络、广泛互连网络。 神经网络至少可以实现如下功能： 数学上的映射逼近 通过一组映射样本(x1，y1)(x2，y2)，(xn，yn)，网络以自组织方式寻找输入与输出之间的映射关系：yi=f(xi)。 数据聚类、压缩通过自组织方式对所选输入模式聚类。 联想记忆 实现模式完善、恢复，相关模式的相互回忆等。 优化计算和组合优化问题求解 利用神经网络的渐进稳定态，特别是反馈网络的稳定平衡态，进行优化计算或求解组合优化问题的近似最优解。 网络学习一般是利用一组称为样本的数据,作为网络的输入(和输出),网络按照一定的训练规则(又称学

42、习规则或学习算法)自动调节神经元之间的连接强度或拓扑结构,当网络的实际输出满足期望的要求,或者趋于稳定时,则认为学习成功。例 9.3 设计一个BP网络，对表9.2所示的样本数据进行学习，使学成的网络能解决类似的模式分类问题。设网络的输入层有三个节点，隐层四个节点，输出层三个节点，拓扑结构如图9-11所示。输入输出X1 x2 x3Y1 y2 y30.3 0.8 0.10.7 0.1 0.30.6 0.6 0.61 0 00 1 0 0 0 1用样本数据按BP算法对该网络进行训练，训练结束后，网络就可作为一种模式分类器使用。因为网络的输出向量(1，0，0)、(0，1，0)、(0，0，1)可以表示多

43、种模式或状态。如可以分别表示凸、凹和直三种曲线，或者三种笔划，也可以表示某公司的销售情况：高峰、低谷和持平等等。当然，要使网络有很好的模式分类能力，必须给以足够多的范例使其学习，本例仅是一个简单的示例。按学习方式分类神经网络的学习方式包括三种，有导师学习、强化学习和无导师学习。按学习方式进行神经网络模型分类时，可以分为相应的三种，即有导师学习网络、强化学习网络及无导师学习网络。3、利用神经网络的结构和权值及阈值，请写神经元yi和z的计算公式，对4个例子的输入值计算出输出值。Zy1y2T1=1T2=1X1X21111其中作用函数为： 例子：X1X2Z00？10？01？11？（1）计算公式为（2）

44、4个例子的计算值为：（a） (b) （c） (d) 六、 专家系统n 须满足的基本功能（共六大功能）: 存储问题求解所需的专家知识; 存储具体领域内的初始数据和推理过程中所涉及到的各种信息如中间结果、目标、子目标、条件、假设等等。 根据当前输入的数据，利用已有的知识，按照一定的推理策略，去解决当前问题，并能控制、协调整个系统。 能对推理过程、结论或系统自身做出必要的解释如解题步骤、处理策略、选择处理方法、求解某种问题的能力、系统如何组织和管理其自身知识等。这样既便于用户的理解和接受，同时也便于系统的维护。 提供知识获取、机器学习、修改、扩充和完善等其它维护手段。这样才能更有效地提高系统的问题求

45、解能力及准确性。 提供一种人机接口，能分析、理解用户的各种请求。 其中，存放知识和使用知识是专家系统的两个基本功能，用于实现该功能的知识库和推理机构成了专家系统的两个核心部件，如图7-2所示。n 基于规则的专家系统的结构：一般包括知识与数据库、推理机、黑板、人机接口、解释器和知识获取机等六部分。知识库推理机输入或提问答案专家知识专家系统的基本结构 人 机 接 口推理机解释器知识获取知识与数据库黑 板专家系统的一般结构专家系统的一般结构 专家系统的结构知识与数据库：包括专家知识库和事实数据库两部分，存储着求解领域中问题所需的专家知识及数据，它是专家系统的组成基础。主要用途：用于存放相关领域或问题

46、的初始数据、中间结果、最终结论等。它能对知识和全局数据施行存储、管理，并以规则形式表达专家级知识。一类是领域中的定义、事实和理论等，通常收录于相关学术著作和教科书中；另一类是专家个人在工作经历中所获得的实践经验等。这使得专家们在错综复杂关键时刻，能临机决断，做出正确决策。特性： 它可被所有的规则访问； 规则之间的联系只有通过数据库才能发生。推理机：推理机实际上就是一组计算机程序，它是专家系统的“思维”机构，是构成专家系统的核心部分。主要功能：协调控制整个系统，模拟领域专家的思维过程，控制并执行对问题的求解。它能根据当前已知的事实，利用知识库中的知识，按一定的推理方法和控制策略进行推理，求得问题

47、的答案或证明某个假设的正确性。总之，知识库和推理机构成了一个专家系统的基本框架。同时，这两部分又是相辅相成、密切相关的。因为不同的知识表示有不同的推理方式，所以，推理机的推理方式和工作效率不仅与推理机本身的算法有关，还与知识库中的知识以及知识库的组织有关。黑板：黑板是一种可读、可刷新重写的装置，用于描述记录专家系统的中间推理过程、数据的变换与演算，又称为暂存器。许多专家系统结构把黑板并入数据库中，但它只是系统运行中间的一些动态信息的集合，是系统运行期间产生和变化的，因此，它只是数据库中“动态”变化的那一部分。有了黑板，便于进行系统跟踪、调试与解释。解释模块（解释器）： 这是实现系统透明性的重要

48、模块。它负责回答用户提出的各种问题，解释系统的推理过程，使系统向用户透明。 解释程序模块由一组程序构成，它是专家系统区别于一般程序的重要特征之一。它可对推理路线和提问的含义给出必要的清晰的解释，使用户了解推理过程；并能跟踪并记录推理过程，也为系统维护提供了方便的手段。知识获取模块： 这是专家系统中能将某专业领域内的事实性知识和领域专家所特有的经验性知识转化为计算机可利用的形式并送入知识库的功能模块。同时也负责知识库中知识的修改、删除和更新，并对知识库的完整性和一致性进行维护。知识获取模块是实现系统灵活性的主要部分，它使领域专家可以修改知识库而不必了解知识库中知识的表示方法、知识库的组织结构等实

49、现上的细节问题，这大大地提高了系统的可扩充性。人机接口： 人机接口负责把领域专家、知识工程师或一般用户输入的信息转换成系统内规范化的表示形式，然后把这些内部表示交给相应的模块去处理。系统输出的内部信息也由人机接口转换成用户易于理解的外部表示形式显示给用户。 n 求解过程大致有如下几个步骤： 根据用户的问题对知识库进行搜索，寻找有关的知识。 根据有关的知识和系统的控制策略形成解决问题的途径，即知识操作算子序列，从而构成一个假设集合。 对解决问题的一组可能假设方案进行排序，并挑选其中在某些准则下为最优的假设方案。 根据挑选的解决问题的假设方案去求解具体问题。 如果该方案不能真正解决问题，则回溯到假设方案序列中的下一个假设方案，重复求解问题。 上述过程循环执行，直到问题已经解决或所有可能的求解方案都不能解决问题而宣告“本系统该问题无解”为止。n 设有规则 R: (AB)(CD)(EF)G) S产生式结构可转换为与/或树结构来表示：SBA S1S S3 S4 C D S5 S6 E F G n 专家系统的性能需要从四方面来考虑：即方便性、有效性、可靠性和可维护性。n 专家系统设计的准则： 知识库和推理机分离。这是设计专家系统的基本原则。 尽量使用统一的知识表示方法。以便于系统对知识进行统一的处理、解释和管理。 推理机应尽量简化。把启发性知识也尽可能地独立