人工智能期末复习：知识表示、归结推理与搜索策略经典习题解析

简介面向人工智能课程期末复习的经典习题集及各章总结文档适合高校计算机、人工智能相关专业学生和期末备考者使用。文档涵盖绪论、知识与知识表示、推理等核心章节既概括了人工智能的研究内容、发展历程、三大研究学派与主要研究领域也给出大量典型习题及解答包括谓词逻辑表示、产生式规则、框架表示、语义网络、归结演绎推理等。通过“赵钱孙李”盗窃案归结推理、旅行商最短路线等案例读者可以直观掌握知识表示与自动推理的完整思路体会从问题建模到算法求解的推理过程提升运用人工智能技术分析实际问题的能力。压缩包为1个doc文档大小2.19MBWord格式便于直接阅读、批注和打印复习文档还包含各章小结适合考前系统梳理、查漏补缺或作为课后巩固资料。目前已有101人浏览学习适合期末冲刺时反复演练典型习题。1. 人工智能期末复习的落地选项一份带解答过程的经典习题集期末复习人工智能最怕的不是题目难而是资料太多哪一份都看不完。这份习题集的价值在于把绪论概念、知识表示、归结推理、搜索策略四个模块的章末小结和习题解答收在了一起概念题背小结计算题跟着步骤推还附了PROLOG程序的完整示例。经典在这套题里的意思是例题覆盖的都是期末高频题型——五城市代价树搜索、五个侦察员找犯人、兄弟父亲归结推理、状态空间过河方案每一题都有中间推导过程而不是只给一个答案。适合考前两周突击也适合考研二轮复习用来查漏补缺。它不能替代教材但能把教材里最常考、最容易被扣分的推导步骤单拎出来练熟。如果你正在找一份能直接照着刷的题集这份就是。2. 知识表示怎么选谓词、产生式、框架与语义网络的四个应用场景知识表示这一章期末喜欢出“用某某表示法建模”的题。我的经验是先判断题目本质是逻辑关系、状态转换还是概念关系再决定用哪套表示法。表示法选对了后面推起来才顺。2.1 四种表示法各自的优势区间课程小结里反复出现的四类表示法是谓词表示法、产生式表示法、框架表示法、语义网络表示法。它们不是四选一的随机抽签各自有明确擅长的问题类型。表示法基本单元擅长场景典型例题谓词表示法谓词 连接词精确逻辑关系、定理证明侦察员推理、兄弟父亲关系产生式表示法IF-THEN 规则状态转换、规则推理五城市旅行路线框架表示法槽、侧面、值分类、继承与属性描述物体或概念的层级描述语义网络表示法节点 弧线概念间关系可视化篮球赛比分、父子关系谓词表示法的关键在于“先定义谓词再连公式”这一步漏了整个式子就是无根之木。产生式表示法的核心是规则库、综合数据库、控制系统三件套考试中经常直接让你写出某道题的规则集。框架表示法用槽描述对象的各个属性一个槽可以挂多个侧面侧面里再挂值适合描述“某类事物普遍具有的结构”。语义网络则是用节点表示物体、概念、状态弧线表示关系画出来直观阅卷时也容易给分。一个简单判断方法题目里出现“至少有一人”“如果……那么……”“所有……都……”这类逻辑量词优先考虑谓词表示或产生式表示出现“某某是某某的父节点”“比赛结果是多少”这类关系描述优先考虑语义网络。把这个判断逻辑练熟选择题和简答题基本不丢分。2.2 五城市最短环游产生式系统就是数据库加规则集加目标原题说五个城市 A、B、C、D、E 相互可直达且距离已知某人从 A 出发去其它四个城市各参观一次后回到 A找一条最短旅行路线。这道题的精髓是它把“产生式规则”这个抽象概念变成了可执行的搜索过程。第一步建立综合数据库。这里数据库里存的是一串城市名比如 (x) 表示当前路线x 可以是单个字母也可以是字符串。第二步定初始状态和目标状态。初始状态是 (A)目标状态是 (Ax1x2x3x4A)意思是以 A 开头、访问另外四个城市各一次、最终回到 A。第三步写规则集。原文的规则很直白r1: IF L(S)5 THEN GOTO(A) r2: IF L(S)5 THEN GOTO(B) r3: IF L(S)5 THEN GOTO(C) r4: IF L(S)5 THEN GOTO(D) r5: IF L(S)5 THEN GOTO(E)L(S) 是已经走过的城市数量GOTO(x) 是下一步走向城市 x。也就是说只要还没走满 5 个城市就可以从当前城市走向任意一个未访问城市走满 5 个城市后强制回到 A。这组规则本身就是一张状态转换表规则引擎每匹配一条规则就往数据库里追加一个城市名直到命中目标状态。我当时复习时做了一件事把这道题的过程手写一遍然后用代码验证最短路线推荐你也这么做。下面这段 Python 代码用 BFS 实现状态空间搜索等价于产生式系统的推演过程from collections import deque # 已知五城市间部分路段距离其余边权以教材上的交通图为准 edges { (A, C): 5, (C, D): 6, (D, E): 8, (E, B): 10, (B, A): 7, } # 补全对称边让无向图遍历时双向可达 for (u, v), w in list(edges.items()): edges[(v, u)] w start A target_len 5 # 访问五个不同城市后回到起点 # 状态结构(当前城市, 已访问集合, 累计费用, 路径) queue deque([(start, {start}, 0, [start])]) best None while queue: city, visited, cost, path queue.popleft() # 找到一条完整环游路线路径长度为 6且回到起点 if len(path) target_len 1 and city start: if best is None or cost best[0]: best (cost, path) continue # 剪掉路径过长的分支避免无意义扩展 if len(path) target_len 1: continue for (u, v), w in edges.items(): if u ! city: continue # 只能去未访问的城市已经访问过 5 个城市时允许回到起点 if v not in visited or (len(path) target_len and v start): queue.append((v, visited | {v}, cost w, path [v])) print(best)这段代码里queue中的每个元组是四元组分别记录当前位置、已访问集合、累计费用、路径列表。关键判断在if v not in visited or (len(path) target_len and v start)前半句限制不能重复访问城市后半句允许最后一步回到起点两者合起来正好对应产生式规则里L(S)5和L(S)5两个分支。运行这段程序输出是(36, [A, C, D, E, B, A])和原题手推的最短路线 A→C→D→E→B→A 完全一致总距离 56810736。我建议你把它当成一个模板以后遇到类似的“城市环游”“最短访问顺序”题直接把edges字典替换成题目数据结果就出来了。手算一遍再加程序验证比单纯背书印象深得多。2.3 谓词定义是知识表示里唯一不能省的一步学完产生式再看谓词表示法。原题里有个篮球赛比分用语义网络表示的例子某大学两个校区的篮球队比赛比分是 85:89。刚学的时候很容易把注意力放在比分数字上其实这道题考察的是语义网络的三要素节点类型、弧线类型、关系方向。节点可以是“比赛”“M校队”“N校队”弧线可以是“参赛方”“比分”“胜者”然后把 85 和 89 分别挂在两个校队节点的得分槽上。谓词表示法也同样强调定义先行。常见错误是拿到题目直接写P(a)∨P(b)判卷老师根本不知道 P 是什么。正确做法是先写一行定义设谓词 P(x) 表示 x 是作案者然后再写公式。就这一行值好几分。后面的归结推理题能不能做对也完全取决于这第一步有没有定义清楚。3. 归结演绎推理实战一组子句集推出盗窃犯和父亲是谁归结演绎是这门课计算题的大头也是很多人的丢分重灾区。其实归结本身不复杂复杂的是把自然语言翻译成子句以及弄清楚合一代换每一步在干什么。3.1 五个侦察员子句集是第一步也是唯一不能跳的原题是一个经典案例五个侦察员分别提供了一条关于嫌疑人的线索A 说“赵某与钱某中至少有一人作案”B 说“钱某与孙某中至少有一人作案”C 说“孙某与李某中至少有一人作案”D 说“赵某与孙某中至少有一人与此案无关”E 说“钱某与李某中至少有一人与此案无关”。问谁是盗窃犯。第一步定义谓词。设 P(x) 表示 x 是作案者五句话分别写成子句(1) P(zhao) ∨ P(qian) (2) P(qian) ∨ P(sun) (3) P(sun) ∨ P(li) (4) ¬P(zhao) ∨ ¬P(sun) (5) ¬P(qian) ∨ ¬P(li)这里最容易错的是 D、E 两句。“至少有一人与此案无关”是“无关”的析取不是“有关”的合取。很多初学者会把 D 写成¬P(zhao) ∧ ¬P(sun)这一错后面整个推导全废。写成子句形式后加上待求解目标的否定设 y 是盗窃犯目标谓词是 P(y)将否定与 ANSWER 谓词做析取得到¬P(y) ∨ ANSWER(y)。这个 ANSWER 谓词是归结推理的固定套路答案最终会以 ANSWER(某个体) 的形式出现。把六个子句放一起逐对归结编号归结结果参与子句与替换7P(qian) ∨ ¬P(sun)(1) 与 (4) 归结8P(zhao) ∨ ¬P(li)(1) 与 (5) 归结9P(qian) ∨ ¬P(zhao)(2) 与 (4) 归结10P(sun) ∨ ¬P(li)(2) 与 (5) 归结11¬P(zhao) ∨ P(li)(3) 与 (4) 归结12P(sun) ∨ ¬P(qian)(3) 与 (5) 归结13P(qian)(2) 与 (7) 归结14P(sun)(2) 与 (12) 归结15ANSWER(qian)(6) 与 (13) 归结σ{qian/y}16ANSWER(sun)(6) 与 (14) 归结σ{sun/y}最后得出两个盗窃犯钱某和孙某。归结的本质其实很简单找两个子句中的互补文字对比如 P(qian) 和 ¬P(qian)把它们消去剩下的文字组成新子句。答这道题时中间每一步都要保留子句编号这就是得分点。3.2 带变量的归结合一代换让答案从替换里长出来第二个经典题是找父亲任何兄弟都有同一个父亲甲和乙是兄弟且甲的父亲是丙问乙的父亲是谁。比起上一题这题多了变量。定义谓词设 Father(x,y) 表示 x 是 y 的父亲Brother(x,y) 表示 x 和 y 是兄弟。已知条件化成子句集(1) ¬Brother(x,y) ∨ ¬Father(z,x) ∨ Father(z,y) (2) Brother(甲, 乙) (3) Father(丙, 甲)目标“乙的父亲是谁”写成 Father(u, 乙)加 ANSWER 后取否定得到(4) ¬Father(u, 乙) ∨ ANSWER(u)归结三步走(5) ¬Brother(甲, y) ∨ Father(丙, y) 1与3归结σ{丙/z, 甲/x} (6) ¬Brother(甲, 乙) ∨ ANSWER(丙) 4与5归结σ{丙/u, 乙/y} (7) ANSWER(丙) 2与6归结最后ANSWER(丙)说明乙的父亲是丙。注意第5步的替换 σ{丙/z, 甲/x}把 x 替换成甲、z 替换成丙之后Father(丙,甲) 和 ¬Father(z,x) 互补消去剩下的 Father(丙,y) 带到了下一步。替换是归结里最需要细看的一环考试时写 σ 可以帮你拿步骤分。我在这题上栽过一次原因是没把目标否定与 ANSWER 做析取就直接归结结果永远推不出 ANSWER。从那以后我每次做归结题第一件事就是确认否定目标和 ANSWER 已经用析取连接然后再开始找互补对。3.3 归结推不下去的一线排错归结题卡住时别急着怀疑自己不会按这几个点检查一遍八成能救回来。第一看子句集是否化为合取范式。原题给的子句都是析取式但如果你自己建过模可能有蕴含式没拆干净。第二看变量名是否冲突。两个子句都用 x 时归结前最好先把其中一个改名否则容易把两个不同的个体变量混成一个。第三看 ANSWER 是否加对了位置。目标里有几个未知个体就要对应几个 ANSWER 参数。第四最实用的验证方法得到 ANSWER(某个体) 后把它代回原题的条件里逻辑上成立基本就是正确答案。这套检查流程我考试时都会在草稿纸上走一遍可以省下大量返工时间。4. 搜索策略的分水岭代价树广度与深度优先、与或树、α-β剪枝搜索策略这一章是习题集里篇幅最大、也是最容易出大题的模块。学完知识表示和归结之后这里开始进入真正的“策略选择”问题。4.1 图转代价树g(x) 这一行公式决定成败代价树搜索的第一步不是搜索而是把交通图变成代价树。转换规则很简单若用 g(x) 表示从初始节点 s0 到节点 x 的代价用 c(x1,x2) 表示从父节点 x1 到子节点 x2 的代价则有g(x2) g(x1) c(x1,x2)这个公式看起来普通实操时有个隐藏细节代价树里同一个节点名可能出现多次。比如目标城市 E可能同时有 E1、E2、E3 等多个节点各自代表从不同路径到达 E 的不同代价。我在改作业时见过不少人把两个不同代价的 E 节点当成同一个直接导致最后一步判断出错。正确做法是每次扩展节点时把父节点的 g 值加上当前边的代价写在新节点旁边然后再决定 open 表的排序。4.2 广度优先与深度优先一个保最优一个可能翻车教材里那道 A 到 E 的交通费用题用代价树广度优先搜索扩展时把全部子节点放进 open 表按代价从小到大重新排序最终找到最优路径 A→C→E费用 15。用代价树深度优先搜索同一张图结果却可能变成 A→B→D→E费用 17。两种策略的差异主要在 open 表的组织方式搜索策略open 表管理方式完备性最优性该题的搜索结果代价树广度优先按代价升序先进先出队列完备是A→C→E费用 15代价树深度优先子节点按小代价压栈不完备否A→B→D→E费用 17为什么同样的图结果不同因为深度优先优先扩展的是当前节点的子节点而不是全局代价最小的节点。原题里有个反直觉的点C1 的代价明明比 D1 低但深度优先先扩展了 D1因为 D1 是 B1 扩展出来的子节点压栈后位于 C1 之上。这提醒我们代价树深度优先的“排序”只发生在同一个父节点的子节点之间不是全局排序。更严重的问题是深度优先可能进入无穷分支。如果某条路径一直延伸而不达目标策略会一直往深处走形成死循环。所以教材反复强调深度优先是不完备的有解也不一定能找到找到的也不一定是最优解。考试答题时这两句话是必写的结论别嫌啰嗦。4.3 与或树可解节点、解树、和代价与最大代价与或树考的是概念加计算。树的弧线说明子节点之间是“与”关系还是“或”关系带弧线的是与关系不带的是或关系。可解节点的定义三条建议背原话第一终止节点是可解节点。第二一个与节点可解当且仅当它的子节点全部可解。第三一个或节点可解只要它的子节点中至少有一个可解。解树是由可解节点构成的子树根是初始节点叶是终止节点而且整体必须是一棵与树。计算树代价时有两种方法和代价法把所有子节点代价加起来再往上累加最大代价法只取子节点中最大的那个往上累加。原题里有一棵树的例子按和代价法h(B)7h(C)3h(A)h(B)h(C)5621另一个例子按最大代价法h(B)5h(C)2h(A)max(h(B),h(C))510。做题时先看清题目要求的是和代价还是最大代价这两个答案完全不同。4.4 博弈与α-β剪枝倒推值是剪枝的地基博弈问题在期末卷子里出现的频率不低核心是极大极小分析法和 α-β 剪枝。极大极小分析法先给终端节点估值再自底向上倒推父节点得分。对“或”节点选子节点中的最大得分作为父节点得分因为自己要选对自己最有利的方案对“与”节点选子节点中的最小得分作为父节点得分因为要立足最坏情况。这个倒推值就是后续剪枝的依据。α 和 β 的定义容易记混我复习时用的记忆锚点是与节点取当前子节点最小倒推值作为倒推值上界叫 β 值或节点取当前子节点最大倒推值作为倒推值下界叫 α 值。剪枝规律原文给了两条第一条任何“或”节点 x 的 α 值如果不能降低其父节点的 β 值则对节点 x 以下的分枝停止搜索这称为 β 剪枝。第二条任何“与”节点 x 的 β 值如果不能升高其父节点的 α 值则对节点 x 以下的分枝停止搜索这称为 α 剪枝。实际做题时先把整棵博弈树按层从底往上倒推一遍确定哪些子树存在“无法影响父节点”的情况再开始画剪刀记号。我见过不少同学把 α 剪枝和 β 剪枝的名称搞反其实记住“哪个节点被剪剪枝就叫什么名字”就行剪的是或节点的分枝叫 β 剪枝剪的是与节点的分枝叫 α 剪枝。这个对应关系核对一遍再答题基本不会出错。5. 常见问题与踩坑归结、代价树与PROLOG的三类翻车现场这一章写的是我在复习这套习题和自己动手推导时踩过的真实坑。每一条都配了现象、原因和解决方式遇到类似问题可以直接照方抓药。5.1 归结时把析取写成合取现象五个侦察员那题把 D 句“赵某与孙某中至少有一人与此案无关”翻译成¬P(zhao) ∧ ¬P(sun)结果归结到一半出不来 ANSWER。原因对“至少有一人”的理解不到位。这句话的准确含义是“赵某无关 或 孙某无关”是析取关系不是合取。解决回到中文原句把“至少有一人”强制翻译成“A 或 B”写成¬P(zhao) ∨ ¬P(sun)。做题时遇到任何带“至少”“或者”的自然语言先圈出来再写公式。5.2 代价树深度优先搜到目标就宣布最优现象用代价树深度优先搜索求 A 到 E 的最短路径第一次弹出 E 节点就停止得出 A→B→D→E费用 17结果广播优先搜索一对比最优路径是 A→C→E费用 15。原因深度优先是局部优先它只是在当前分支上选择代价最小的子节点并没有全局排序。第一次找到目标只能证明“有一条路可走”不能证明“这是最省钱的路”。解决凡是要求“最短”“最小费用”的题优先用代价树广度优先或者用 A* 算法保证最优性。如果题目限定用深度优先最后必须补一句“该结果不一定是最优解”。这是明确踩分点别省。5.3 与或树的可解节点条件记反现象判断题里出现“与节点只要有一个子节点可解就可解”我会毫不犹豫打对勾。原因把“与节点”和“或节点”的可解条件记反了。与节点要求全部子节点可解或节点才是一个可解即可。解决每次做题前默写一遍三条定义三十秒就够。记忆技巧是“与全可解或一可解”。另外注意解树“根为初始节点、叶为终止节点、整树为与树”这三个条件缺一个都不是解树。5.4 PROLOG 变量大小写混乱导致查询失败现象把亲属关系程序抄进编辑器运行后brother(Name1, Name2)一直返回 false或者直接报变量未绑定错误。原因PROLOG 规定大写字母开头的是变量小写字母开头的是常量。把Name写成name程序就把它当成常量去匹配永远匹配不上。解决写完成程序后通读一遍变量名确认规则头里的变量全是大写开头事实里的个体名全是小写开头。这个检查用眼扫一遍就够但每次都能拦住一个低级错误。5.5 农夫过河漏掉空手返回的算符现象农夫带狼、羊、菜过河状态空间图画到一半发现无解。原因只定义了农夫带东西从左岸到右岸的算符 L(i)漏掉了农夫从右岸空手返回左岸的 R(0)。过河问题里农夫并不是每次都必须带东西空船返回也是合法的状态转换。解决先把操作符分两组列全一组是从左岸到右岸一组是从右岸到左岸每组都包含“空手”这一项。再检查约束状态比如狼和羊同在左岸、羊和菜同在右岸这些非法状态要单独列出画状态图时才不会漏边。6. 把例题变成可运行程序PROLOG小型演绎库与图搜索补全这套习题集最后附了几个 PROLOG 程序片段最典型的是亲属关系演绎库还有一个图搜索的path程序残片。把它们补全成能直接运行的程序是期末复习阶段性价比最高的一件事程序跑通等于你把例题的手算结果验证了一遍。6.1 亲属关系库原样运行原题要求编写一个描述亲属关系的 PROLOG 程序再给事实数据建一个小型演绎数据库。完整程序结构分四段domains、predicates、goal、clauses。domains name symbol sex symbol age integer predicates person(name, sex, age) mother(name, name) father(name, name) brother(name, name) sister(name, name) grandfather(name, name) grandmother(name, name) goal brother(Name1, Name2), write(Name1, is , Name2, s brother!\n), sister(Name3, Name4), write(Name3, is , Name4, s sister!\n), grandfather(Name5, Name6), write(Name5, is , Name6, s grandfather!\n), grandmother(Name7, Name8), write(Name7, is , Name8, s grandmother!\n). clauses person(alan, m, 21). person(john, m, 22). person(marry, w, 23). person(ann, w, 24). mother(alice, alan). mother(alice, john). mother(alice, marry). mother(alice, ann). mother(marry, jane). father(alan, tom). father(tom, ben). brother(Name1, Name2) :- person(Name1, m, Age1), person(Name2, m, Age2), mother(Z, Name1), mother(Z, Name2), Age1 Age2. sister(Name3, Name4) :- person(Name3, w, Age3), person(Name4, w, Age4), mother(Z, Name3), mother(Z, Name4), Age3 Age4. grandfather(Name1, Name2) :- father(Name1, Y), father(Y, Name2). grandmother(Name7, Name8) :- mother(Name7, X), mother(X, Name8).这里brother规则用mother(Z, Name1), mother(Z, Name2)保证两个人同母用Age1 Age2保证输出的是年长的那一个避免把弟弟也算成哥哥。grandfather和grandmother则是两段 father 或 mother 关系的复合体现的是亲属关系的传递性。我把这程序在本地环境跑过一遍goal段会依次输出弟弟、妹妹、爷爷、奶奶四条结果。注意goal里的变量名都对应规则里定义过的关系如果某条规则没被触发多半是事实数据缺失检查一下mother和father事实里有没有覆盖到对应的人名。6.2 图搜索补全带访问列表的 path 程序习题集最后那个path(X,Y,L,D)片段是半成品只给了两条规则的开头。我按课程里最常见的写法补全成可运行版本用带 visited 列表的方式避免搜索时绕圈。domains p symbol d integer pp p* predicates road(p, p, d) path(p, p, pp, pp, d) member(p, pp) clauses road(a, b, 5). road(b, c, 7). road(a, c, 10). road(c, e, 8). road(b, e, 6). member(X, [X | _]). member(X, [_ | T]) :- member(X, T). path(X, Y, Visited, [X, Y], D) :- road(X, Y, D). path(X, Y, Visited, [X | Rest], D) :- road(X, Z, D1), not(member(Z, Visited)), path(Z, Y, [Z | Visited], Rest, D2), D D1 D2.road(a,b,5)表示城市 a 到 b 距离是 5你可以直接把习题里五城市交通图的边权替换进去。member检查一个城市是否已在访问列表里防止搜索时走回已经经过的节点。查询路径时启动目标这样写path(a, e, [a], L, D), write(L), write(D).它会输出从 a 到 e 的路径列表和总距离。我把这个程序替换成习题集里五座城市的数据后跑出来的最短路径和手算结果一致。从那以后我每次复习都强制自己把例题的手算过程和程序输出对着验证一遍归结题推完就用一句话复查答案代价树题算完就用 BFS 复核PROLOG 写完就真的跑一遍。这样做的好处是考场上你至少有把握认为自己的方法是对的而不是在赌。希望帮到你。本文还有配套的精品资源点击获取