人工智能导论(本科生)--复习大纲--参考答案

目录 绪论 .................................................................................................................................................. 1 搜索技术........................................................................................................................................... 1 遗传算法........................................................................................................................................... 8 谓词逻辑........................................................................................................................................... 8 结构化知识表示 ............................................................................................................................. 12   绪论 1、什么是人工智能？ 答：人工智能又称机器智能，是用计算机模拟或实现的智能；(人工智能是研究如何制造出人造的智能机器或系统，来模拟人类智能活动的能力，以延伸人们智能的科学)  2、什么是符号智能与计算智能？并举例说明。 答：符号智能是模拟闹智能的人工智能，是以符号形式的知识和信息为基础，主要通过逻辑推理，运用知识进行问题求解。如搜索技术、专家系统、定理证明等；计算智能是模拟群智能的人工智能，以数值数据为基础，主要通过数值计算，运用算法进行问题求解。 搜索技术 1.状态图是由什么组成的？ 答：状态图是由节点与有向边组成；  2.简述图搜索的方式和策略。 答：搜索方式：线式搜索和树式搜索；搜索策略：盲目搜索和启发式搜索；  3.阐述图搜索策略中OPEN表与CLOSED表的作用。 答：OPEN表用来保存当前待考察的节点，并按照某种排列，来控制搜索的方向和顺序；CLOSED表用来记录搜索过程中已考察过的节点，保存全局搜索信息，并可根据节点返回指针得到搜索解路径。  4.简述广度优先策略与深度优先策略的不同点。 答：广度优先搜索是始终在同一级节点中考查，当同一级节点考查完毕，才考查下一级节点。因此，是自顶向下一层一层逐渐搜索的，属于横向搜索策略，其搜索是完备的，得到的解为最优解；  深度优先搜索是在搜索树的每一层始终只扩展一个子节点，不断向纵深前进，直到不能再前进时，才从当前节点返回到上一级节点，沿另一方向又继续前进。因此，是从树根开始一枝一枝逐渐搜索的，属于纵向搜索策略，其搜索是不完备的，得到的解不一定为最优解。  5.什么是启发式搜索？并以八数码难题为例，说明其原理。 答：启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的。对于八数码难题，可以利用不在位将牌数或者与目标距离信息来作为启发函数，可以加快搜索目标的步数。  6.简述启发函数的单调性判别。 答：设m是n的子节点，t为目标节点，当h(n)‐h(m) ≤ C(n, m), h(t) = 0成立时，则可称启发函数h是单调的。  7.分别用深度优先搜索方法、宽度优先算法、启发式搜索算法求解下图所示八数码难题。 2 8  1231 6 3 847 5 4 765     初始状态        目标状态 答：略 设定启发式函数 h(n)为当前节点“不在位”的将牌数；     对于空格，有向左、向上、向下，向右的启发式规则；     （根据启发函数定义以及启发式规则使用顺序的不同，答案不唯一）       2  8   1  6  37  5  4g=0 h=7 f=7 2     8 1  6  3 7  5  4 g=1 h=7 f=8 2  8  31  6   7  5  4g=1 h=6 f=7 2  8  31     67  5  4g=2 h=6 f=8 2  8  31  6  47  5  g=2 h=5 f=7 2  8  31  6  47     5g=3 h=4 f=7 2  8  31  6  4  7  5g=4 h=5 f=9 2  8  31     47  6  5g=4 h=3 f=7 2  8  31  4   7  6  5g=5 h=4 f=9 2     31  8  47  6  5g=5 h=3 f=8 2  8  3   1  47  6  5g=5 h=3 f=8    2  8 1  6  3 7  5  4 g=2 h=6 f=8 2  6  8 1     3 7  5  4 g=2 h=7 f=9 1  2  8    6  3 7  5  4 g=3 h=5 f=8 1  2  8 7  6  3    5  4 g=4 h=6 f=10 1  2  8 6     3 7  5  4 g=4 h=5 f=9 2  8  31  5  67     4g=3 h=6 f=9 2     31  8  67  5  4g=3 h=6 f=9 2  8  3    1  6 7  5  4 g=3 h=6 f=9 2  8  31     47  6  5g=6 h=3 f=9    8  3 2  1  4 7  6  5 g=6 h=3 f=9    2  31  8  47  6  5g=6 h=2 f=8 2  3   1  8  47  6  5g=6 h=4 f=10 1  2  37  8  4  6  5g=8 h=2 f=10 1  2  38     47  6  5g=8 h=0 f=8 1  2  3   8  47  6  5g=7 h=1 f=8 1324 1097 8 6 511 1213目标 8.下图为五大城市之间的交通图，边上的数字是城市之间的距离。用图搜索算法，求解A到E的最短路径答：可利用分支界限法进行求解。1、加权图转换为加权树2、利用分支界限可得搜索图OPEN:C5、E7、E1、C2、E4、B2A C1 D1 E1 8 9 4 3  4 B1 C2 E7 B2 D3 E2 E4 D4 C5 2  4  4 4 9  4 6 A C1 D1 E1 8 9 4 6 3  4 B1 B3 C4 C2 E7 C3 B2 C6 B4 E6 D3 E2 E3 D2 E4 D4 E5 C5 2  4  4  4 4 9  4 3 6 6 6 6 6 3 3 A C D E 8 9 2 4 6 3  4 B CLOSED：A、B1、C1、D4、D1、D3、E2解路径：A、B1、C1、E29.比较A算法与A*算法的特点。答： A算法为一种启发式搜索算法，当A算法的启发函数满足h(x)≤h*(x)时，该A算法即为A*算法。A*算法可以保证搜索取得最优解。  10.什么是与或图的终止节点？什么是能解节点？什么是解树？答：本原问题对应的节点为终止节点；当一个节点满足以下三个条件时，该节点为能解节点：1)该节点为终止节点；2）当该节点为与节点时，当且仅当其所有子节点能解；3）当该节点为或节点时，只要其任一子节点能解皆可。解树是在一个与或图中从初始节点到目标节点的图或树形路径。11.什么是解树的代价？答：解树的代价即树根的代价，是从树叶开始自下而上逐层计算而求得的。12.什么是希望树？答：希望树是当前与或图中具有最小代价的解树。13.判断下图各节点的能解性，并确定解树。答：略。14.指出下图的解树，并计算每个解树的代价，以及希望树。答：解树1：{Q0，A，t1，t2}g(t1)=g(t2)=0,g(A)=11,g(Q0)=13解树2：{Q0，B，D，G，t4，t5}g(t4)=g(t5)=0,g(G)=3,g(D)=4,g(B)=6,g(Q0)=8所以，解树2为最优解树，即希望树15.比较极大极小算法与α‐β剪枝技术的区别。答：极大极小算法是一种静态搜索算法，搜索树的生成与格局估值分开的，搜索效率低。α‐βQ0 1 t1 2 1 t2 A 5 6 t3 t4 2 B C 3 2 1 G F E D 2 2 1 t5 1 4 t1 2 7 t2 3 5 6 t3 t4 剪枝为动态搜索算法，利用有限深度优先搜索技术，节点的扩展与格局估值是同时进行的，提高了搜索效率，同时保证解的完备性。 16.下图所示博弈树，按从左到右的顺序进行α‐β剪枝搜索（1）计算各节点的倒推值。（2）利用α-β剪枝技术剪去不必要的分枝。 答：  2   3  ‐4  10  2  5   7  8   ‐5  10  5  ‐6  ‐1  ‐2  1  ‐2  5   6  3   6  ‐4   4  ‐3  4 2 ‐4 2 22 2 ‐5 ‐5 ‐5 ‐6 ‐3 ‐3 ‐3 ‐4 5 5 3 2   3  ‐4  10  2  5   7  8   ‐5  10  5  ‐6  ‐1  ‐2  1  ‐2  5   6  3   6  ‐4   4  ‐3  4 2遗传算法  1、什么是遗传算法？ 答：遗传算法是你们从生物界按自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计出来的一种优化搜索算法。  2、举例说明遗传算法的三种操作。 答：选择、交叉、变异。  3、简述基本遗传算法的过程。 答：略。  4、对某一问题的遗传算法的选择操作过程，初始种群为S={ s1=13, s2=24，s3=8，s4=19}，个体s1，s2，s3，s4的适应度函数计算分别为169，576，64，361 a)在从区间[0,1]产生4个随机数r1=0.45, r2=0.11, r3=0.57, r4=0.98，试用轮盘赌选择法进行选择操作； b)分析该过程的遗传优化机制。 答：1.  s1，s2，s3，s4的适应度值分别为169，576，64，361  2. s1，s2，s3，s4的选择概率分别为0.14, 0.49, 0.06, 0.31, 累计概率分别为0.14, 0.63, 0.69, 1.00  3.  轮盘赌选择操作可得下一代种群为s2, s1, s2, s4  适应度越高的染色体被随机选中的概率越大，被选中的次数就越多，从而在新种群中被复制的次数就越多，而适应度较低的染色体被选中的次数也就越少，从而在新种群中复制的次数就越少，充分体现了优胜劣汰的自然选择法则。  谓词逻辑  1.什么是知识？知识的组成要素是什么？答：知识是经过加工处理的信息。组成要素：事实、规则、控制、元知识。2.简述知识常用表示方法。答：谓词逻辑、产生式、语义网络、框架、状态空间法、面向对象法； 3.用谓词逻辑表示下列知识：（1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。（2）他每天下午都去打篮球。（3）夏天既干燥又炎热。（4）并不是每一个人都喜欢吃臭豆腐。答：1）定义谓词like(x,y):x喜欢y（∃x）(like(x,meihua))∨（∃y）(like(y,juhua))∨（∃z）(like(z,meihua)∧like(z,juhua))2）定义谓词time（x）:x是下午，play（x,y）：x玩y∀x(time(x)→play(he,basketball))3）定义谓词dry(x) :x干燥，hot(x):x炎热，实体x表示夏天dry(x)∧