人工智能复习资料.doc

《人工智能复习资料.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、选择填空1.产生式系统由综合数据库，规则库，控制策略三个部分组成2.α-β剪枝中，极大节点下界是α，极小节点是β。3.发生β剪枝的条件是祖先节点β值<=后辈节点的α值。4.发生α剪枝的条件是后辈节点β值<=祖先节点的α值。5.在证据理论中，信任函数Bel(A)与似然函数Pl(A)的关系为0<=Bel(A)<=Pl(A)<=1。6.深度优先算法的节点按深度递减的顺序排列OPEN中的节点。7.宽度优先算法的节点按深度递增的顺序排列OPEN中的节点。8.A算法失败的充分条件是OPEN表为空。9.A算法中OPEN中的节点按f值

2、从小到大排序。10.爬山算法（不可撤回方式）是只考虑局部信息，没有从全局角度考虑最佳选择。f(n)=g(n)只考虑搜索过的路径已经耗费的费用11.分支界限算法（动态规划算法）：f(n)=h(n)只考虑未来的发展趋势。仅保留queue中公共节点路径中耗散值最小的路径，余者删去，按g值升序排序。12.回溯策略是试探性地选择一条规则，如发现此规则不合适，则退回去另选其它规则。定义合适的回溯条件①新产生的状态在搜索路径上已经出现过。②深度限制(走到多少层还没有到目标，就限制往回退)③当前状态无可用规则。13.A*选中的任何节点都有

3、f(n)<=f*(s)=h*(n)，g(n)与g*(n)的关系是g(n)≥g*(n)。15.求解图的时候，选择一个正确的外向连接符是顺着现有的连接符的箭头方向去找，不能逆着箭头走。16.根节点：不存在任何父节点的节点。叶节点：不存在任何后继节点的节点。17.两个置换s1,s2的合成置换用s1s2表示。它是s2作用到s1的项。18.LS和LN两个参数之间应该满足LS、LN>=0,不独立，LS、LN可以同时=1，LS、LN不能同时>1或<1。19.语义网络：一般用三元组（

4、对象，属性，值）或（关系，对象1，对象2）20.反向推理方法：定义：首先提出假设，然后验证假设的真假性，找到假设成立的所有证据或事实。21.证据A的不确定性范围：-1≤CF(A)≤1。22.析取范式：仅由有限个简单合取式组成的析取式。23.合取范式：仅由有限个简单析取式组成的合取式。24.原子公式：由原子符号与项（为常量、变量和函数）构成的公式为原子公式。二、产生式系统（第一章）给定一个初始状态S、一个目标状态G，求从S到G的走步序列。S状态G状态解：①综合数据库定义：矩阵（Sij）表示任何状态，其中：Sij∈0,1,…8

5、｝1≦i,j≦3Sij互不相同状态空间：9！=362,880种状态②规则集设：空格移动代替数码移动。至多有四种移动的可能：上、下、左、右。定义：Sij为矩阵第i行j列的数码;其中：i0,j0表示空格所在的位置，则Si0j0=0（0代表空格）空格左移规则：ifj0-1≧1thenj0＝j0-1;Si0j0＝0如果当前空格不在第一列，则空格左移一位，新的空格位置赋值为0同理：右移规则：ifj0+1≦3thenj0＝j0+1;Si0j0＝0上移规则：ifi0-1≧1theni0＝i0-1;Si0j0＝0下移规则：ifi0+1≦3

6、theni0＝i0+1;Si0j0＝0③控制策略（1）爬山算法设：－W(n)：不在位的数码个数n：任意状态目标状态，－W(n)=0（每个数码都在规定的位置）最不利状态，－W(n)=－8（每个数码都不在规定的位置）左右上－W(n)=－4－W(n)=－5－W(n)=－5（－3）（－3）（－3）其余2种移动(略)此路径(略)上左左（－2）下（－1）（0）右（1）回溯策略限定搜索深度为6，移动次序为左上右下。深度=1可用规则：左、上、右此状态与深度=3的状态相同左深度=4左深度=5可用规则：上、右右可用规则：左、右、下左与深度=4

7、状态相同且深度=6可用规则：左、下深度=6下限定搜索深度=6 规则排列次序： 左移、上移、右移、下移（3）A算法令：g(n)=d(n)节点深度h(n)=w(n)不在位的数码个数（启发函数）则f(n)=d(n)+w(n)283 164 75283 14 765283 164 75283 164 7523 184 765283 14 765283 14 765283 714 6583 214 76523 184 76523 184 765123 84 765123 84 765123 784 65s(4)A(6)B(4)C(6

8、)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456三、第二章和第四章（1）超图（与或图）找解图，并计算解图耗散值n0n1n3n6n7n2n5n4n8n0n3n6n7n5n4n8解图1n1n5n0n8n7解图2左图耗散值①K(n0,N)＝1+K(n1,N)＝