2013年杭州电子科技大学 期末考试 人工智能复习题_答案改.doc

解释下列概念的主要含义：（每题5分，共30分）1、 状态空间法：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的实验序列，直至 达到目标状态止。2、原子谓词公式：用P(x1,x2,xn)表示一个n元谓词公式其中P为n元谓词，x1,x2,xn为客体变量或变元。3、合一：寻找项对变量的置换，以使两表达式一致。4、框架：通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可以拥有若干个值。5、消解反演：把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去,把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决。6、问题归约法：问题归约法从目标(要解决的问题)出发，逆向推理，通过一系列变换把初始问题变换为子问题集合和子子问题集合，直至最后归约为一个平凡的本原问题集合。这些本原问题的解可以直接得到从而解决了初始问题，用与或图来有效地说明问题归约法的求解途径。问题归约法能够比状态空间法更有效地表示问题。状态空间法是问题归约法的一种特例。在问题归约法的与或图中，包含有与节点和或节点，而在状态空间法中只含有或节点。7、置换：就是在表达式中用置换项置换变量。8、语义网络：是知识的一种图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。9、消解：对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句,又称归结。10、规则演绎系统：基于规则的问题求解系统运用IfThen规则来建立，每个if可能与某断言(assertion，主张)集合中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then 部分为后项。11、遗传算法：遗传算法是你们从生物界按自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计出来的一种优化搜索算法。设有下列语句，请用相应的谓词公式把它们表示出来：（每题5分，共10分）1、 并不是每个人都喜欢吃水果。答：x（man(x)like（x，fruit）2、 张某给屋里的人每人一件礼物。答：xGive(zhang,x,y)Inroom(x) present(y)3、 杭州的夏天既炎热又潮湿。答hot(hangzhou,summer) wet(hangzhou,summer)4、 计算机专业的学生必须掌握高等数学。答x(dept(x,computer) must(x,maths)用问题归约法求解梵塔问题，画出相应的归约图。（P32）已知八数码问题如下：（1）在一个3*3的方框内放有8个编号的小方块 （2）紧邻的小方块可以移入到空位中 （3）通过移动小方块将某一布局变换为另一布局已知初始布局如下，要求以广度优先搜索技术、深度优先搜索技术、启发式搜索技术将初始布局变换为目标布局 （20分）2831231648475765初始布局 目标布局广度优先（按舒适郑方向一动空格）深度优先启发式搜索（f(n)=d(n)+w(n):d(n)表示深度，w(n)表示错误的位置）城市之间的交通费用图如下图所示，图中圆圈表示城市，城市之间连线的数字为城市之间路程的费用，要求从A城市出发，经过其他每个城市至多一次，最后到达E城市，要求按代价树广度优先、深度优先搜索得出解树（要求画出OPEN表与CLOSED表的动态过程及最后的解树）。 （20分）已知子句集，用消解反演来证明结论成立（P81）。（20分）1) S(x,y)M(y)I(f(x)2) S(x,y)M(y)E(x,f(x)3) I(z)4) S(a,b)5) M(b)在正向演绎系统中，用与或