★ FEATURED ARTICLE 简介这份《人工智能经典习题集及各章总结期末考试必备》面向高校人工智能课程期末备考学生与自学者聚焦核心理论梳理与经典题型训练帮助在有限时间内建立章节知识框架并查漏补缺。资源包共1个doc文档大小约2.19MB内容以各章小结和习题解答为主覆盖绪论概念、发展阶段、三大学派、知识表示、推理及归结演绎等高频考点题目配有较完整的求解过程与思路说明。已有103人学习适合需要对照课堂进度复习、强化概念理解与解题能力的学生及自学者使用目录按章节展开便于按复习进度查阅。通过章节总结可快速回看重点借助习题解答又能熟悉产生式规则、语义网络、谓词公式等表示方法及推理步骤对期末复习和日常练习都有较强的参考价值。1. 从一份习题集说起会背“人工智能定义”却算不出最短路径问题出在哪考前一周翻开笔记本“人工智能”的定义、三大学派、五个发展阶段背得滚瓜烂熟可一到代价树扩展顺序、归结反演求答案就卡壳——这是我在带复习时见得最多的一种翻车。这份资源不是又一本概念讲义而是按章拆开的小结加习题解答绪论、知识表示、推理、搜索四大块每一道题都带着手算过程连子句集怎么列、OPEN 表怎么排都写在纸面上。适合三类人期末冲刺的本科生、考研复试要手推归结的、以及工作后想补搜索算法基本功的从业者。它解决的不是“知道人工智能是什么”而是“把答案一步步算出来”。2. 知识表示的四种武器产生式、谓词、框架、语义网络怎么选2.1 从旅行商问题看产生式系统的三个部件习题里那道五城市旅行商乍看是路径规划实际考的是产生式系统的建模。题目要求用产生式规则表示旅行过程答案给的结构是综合数据库、初始状态、目标状态、规则集。很多人抄完答案就过去了没注意规则里L(S)5这个数字的来历——它表示“已经走过的城市数”四个城市各访问一次再加出发地正好五步所以等于 5 时触发回 A 的规则。把这段规则翻译成可执行的检查逻辑可以写成下面这样。注意这里不是复刻原题附图而是按答案给出的分段距离 5、6、8、10、7 回填的一张示例矩阵专门用来验证规则推出来的路径是不是最短。import itertools # 按习题答案 A-C-D-E-B-A 的分段距离回填的示例矩阵 # 行是起点列是终点INF 表示不可直达 INF 10 ** 6 cities [A, B, C, D, E] dist { A: {A: 0, B: 12, C: 5, D: 9, E: 14}, B: {A: 7, B: 0, C: 11, D: 6, E: 10}, C: {A: 5, B: 11, C: 0, D: 6, E: 12}, D: {A: 9, B: 6, C: 6, D: 0, E: 8}, E: {A: 14, B: 10, C: 9, D: 8, E: 0}, } def route_cost(path): 闭环路径代价相邻两城距离累加遇到不可达直接判死 total 0 for u, v in zip(path, path[1:]): w dist[u][v] if w INF: return INF total w return total best_cost, best_path INF, None # 固定起点 A枚举中间四城的全排列最后回到 A for mid in itertools.permutations(BCDE): p (A,) mid (A,) c route_cost(p) if c best_cost: best_cost, best_path c, p print(best_path, best_cost) # (A, C, D, E, B, A) 36这段代码的逻辑很直白itertools.permutations生成中间四城的 24 种排列route_cost按闭环累加距离最后取最小值。参数上唯一需要留心的是矩阵的对称性——原题说的是“相互可直达且距离已知”如果按无向边处理A-B和B-A必须同值这里为了复现答案保留了有向写法实际建模时要么统一对称要么在规则里显式说明方向。产生式系统真正的考点不在枚举而在“匹配—冲突消解—执行”这个循环。规则 r1 到 r5 的前件都是L(S)5后件分别指向 B、C、D、E五条规则同时可匹配选哪条就是冲突消解。教材答案默认按字母序或按规则编号选落到代码里就是permutations的枚举顺序。考试时如果只写规则不写冲突消解策略过程分很容易丢。2.2 谓词、框架、语义网络三种表示法的边界同一章里还塞了谓词表示法、框架表示法、语义网络表示法答案给得很简反而容易让人误以为它们可以互相替换。实际边界是这样的谓词表示法适合“需要严格推演”的场景先定义谓词再用连接词把谓词拼成公式框架表示法适合“结构化对象”一个框架由若干槽组成每个槽有若干个侧面每个侧面又可以挂多个值语义网络适合“关系联想和继承”节点表示物体、概念或状态弧表示节点间的关系。习题里有一道“甲校和乙校篮球队比赛比分 85:89用语义网络表示”。标准做法是建三个节点甲校队、乙校队、比赛事件然后用“比分”“参赛方”“胜方”这类弧连起来。注意比分是挂在“比赛”节点上的不是挂在某一支球队上这一点写错整个网络的含义就变了。表示法核心元素适合的场景常见误用产生式规则库、综合数据库、控制系统规则多、需要解释推理链规则前件写得过宽冲突消解缺失谓词谓词、量词、连接词定理证明、严格逻辑推演谓词含义没定义清楚就往下推框架槽、侧面、值对象结构固定、需要默认值把框架当数据库忽略继承语义网络节点、弧关系查询、概念继承弧的方向和标签随手写无法推理框架表示法那一句“槽拥有若干个侧面侧面又可拥有若干个值”考试里经常被简化成“槽—值”两层结果遇到多值属性就写不下。比如“课程”框架里“任课教师”这个槽可能有“主讲”“辅导”两个侧面每个侧面再挂具体人少一层就表达不了。2.3 选型不是口味问题看推理方式和数据形态我在实际项目里选表示法一般按四条判断走。第一看推理是否需要可解释的链条需要就优先产生式因为每条规则都能打印出来给人看。第二看知识是否带严格量词带“所有”“存在”且要形式化证明就用谓词。第三看对象是否有固定的属性集合有就上框架槽和侧面的结构能直接映射成类。第四看查询是否以“关系跳转”为主是就上语义网络但一定要给弧定好标签体系否则节点连起来也是一团乱麻。这四种表示法在习题集里是分开考的真实系统里经常混用外层用框架描述实体实体内部的判断用产生式涉及一致性校验时再落到谓词公式。复习时把每道题的对象、关系、推理目标三列写出来比背定义有用得多。比如旅行商题的对象是城市关系是距离推理目标是回路最小语义网络题的对象是球队和比赛关系是比分和胜负推理目标是查询。对象和关系一变表示法就该跟着变而不是反过来。3. 归结演绎推理手算流程把“谁作案”拆成六条子句3.1 子句集化的五步从自然语言到标准子句归结反演是习题集里最容易“看答案懂、自己写就废”的一章。标准流程可以压成五步定义谓词、把每句话写成谓词公式、把待求问题否定后与 ANSWER 谓词做析取、消去量词并化成合取范式、提取子句集。每一步都有明确的产出缺一步后面就推不动。第一步定义谓词时要把每个谓词的确切含义写清楚。比如P(x)表示“x 是作案者”Father(x,y)表示“x 是 y 的父亲”。第二步把自然语言逐句翻译成公式“至少有一人”对应析取“与此案无关”对应否定。第三步最关键要求“谁是盗窃犯”不能直接证P(y)而是把¬P(y) ∨ ANSWER(y)加进子句集这样归结出ANSWER(某人)时答案才落在谓词参数里。步骤操作产出易错点1定义谓词并写明含义谓词表同名谓词在不同句里含义漂移2逐句翻译成谓词公式公式集合“至少一个”写成合取3否定目标并析取 ANSWER目标子句忘记加 ANSWER只推出空子句4消去量词、化范式合取范式Skolem 常量与函数混用5提取子句子句集子句内重复文字没合并提示目标否定那一步ANSWER谓词不是可选项。只推出空子句只能证明“有人作案”推不出“谁作案”考试里这样写通常只给一半分。3.2 盗窃案的归结树六条子句怎么收出两个答案习题里那道五人侦查的案子把“甲、乙、丙、丁”记为 a、b、c、d五个侦查员的话可以写成六条子句Pa ∨ PbPb ∨ PcPc ∨ Pd¬Pa ∨ ¬Pc¬Pb ∨ ¬Pd¬Py ∨ ANS(y)手算归结的路径是1 和 4 归结出Pb ∨ ¬Pc2 和这条归结出Pb2 和 5 归结出Pc ∨ ¬Pb再和 2 归结出Pc最后分别与第 6 条归结得到ANS(b)和ANS(c)。答案是乙和丙两个人。把这段过程写成可跑的闭包能避免手算时漏分支。下面这版是命题层面的简化实现把变量 y 按候选常量展开成两条目标子句def neg(lit): 取反P - ~P~P - P return lit[1:] if lit.startswith(~) else ~ lit def resolve_all(ci, cj): 对两个子句做一次二元归结返回所有可能的归结式 out set() for lit in ci: if neg(lit) in cj: new_clause (ci - {lit}) | (cj - {neg(lit)}) out.add(frozenset(new_clause)) return out def closure(clauses, max_round200): 反复归结直到没有新子句返回整个子句池 pool {frozenset(c) for c in clauses} for _ in range(max_round): current list(pool) new set() for i in range(len(current)): for j in range(i 1, len(current)): new | resolve_all(current[i], current[j]) new - pool if not new: break pool | new return pool clauses [ {Pa, Pb}, # 甲与乙至少一人 {Pb, Pc}, # 乙与丙至少一人 {Pc, Pd}, # 丙与丁至少一人 {~Pa, ~Pc}, # 甲与丙至少一人无关 {~Pb, ~Pd}, # 乙与丁至少一人无关 ] # 把目标变量 y 按候选常量展开模拟 ANSWER(y) 的实例化 for y in [b, c]: clauses.append({~P y, ANS_ y}) pool closure(clauses) for item in sorted(pool, keylen): if len(item) 1 and next(iter(item)).startswith(ANS_): print(next(iter(item))) # ANS_b, ANS_c参数上max_round是防止子句池爆炸的保险丝resolve_all只做二元归结不处理因子分解所以子句里可能出现重复文字实际手算时要先做合并。逻辑说明每轮拿当前池里所有子句两两归结新子句并入池后再进入下一轮直到没有新子句产生。如果只想验证答案不看中间过程这个闭包足够如果要写作业还得把每一步的父被子句编号标出来。3.3 置换与合一为什么兄弟问题的答案是丙另一道兄弟题考的是带变量的归结。已知“任何兄弟都有同一个父亲”“甲和乙是兄弟”“甲的父亲是丙”问乙的父亲是谁。公式化之后关键子句是¬Brother(x,y) ∨ ¬Father(z,x) ∨ Father(z,y)、Brother(A,B)、Father(C,A)目标否定加 ANSWER 得到¬Father(u,B) ∨ ANSWER(u)。手算时先拿Father(C,A)和第一条归结置换σ{C/z, A/x}得到¬Brother(A,y) ∨ Father(C,y)再和Brother(A,B)归结置换{B/y}得到Father(C,B)最后和目标子句归结置换{C/u}输出ANSWER(C)。答案落在 u 上所以乙的父亲是丙。这里最容易被忽略的是变量改名。第一条子句里的 x、y、z 和目标子句里的 u 如果重名归结时不做标准化分离就会推出形如Father(C,C)的废子句。血泪经验是每次归结前先把两个子句的变量名改成不重叠的再找互补文字。手写作业时用不同字母区分代码里则靠frozenset的文字名天然隔离。4. 代价树搜索广度优先和深度优先差在一次排序4.1 代价树的构造把图展开成树代价树搜索的第一步不是搜索是展开。给定带权图从初始节点出发把每个节点的后继按边权展开成树用g(x2)g(x1)c(x1,x2)累加代价。展开时同一个城市可能出现多次比如 A 出发到 C 是一条A 经 B 到 C 又是一条这两条在树上是不同节点代价也不同。很多人直接在图上去重结果把最优路径剪掉了。习题里那道“A 到 E 最小费用”的题答案路径是 A→C→D→E代价 56819 这一类分段累加。构造代价树时根节点 g(A)0子节点 g(C)5、g(B)12再往下展开时每个子节点都带着从 A 累计过来的代价。OPEN 表里存的是“待扩展节点 当前累计代价”CLOSED 表存“已扩展节点 已确认的最小代价”这两个表的含义不能混。4.2 广度优先按全表排序深度优先只压栈首两种策略的差别只有一句话代价树广度优先每次扩展前对 OPEN 表全表按代价排序深度优先只把新生成的子节点按代价压到栈首。就这一句结果可能完全不同。from collections import defaultdict # 一道用于对照的示例代价图A-C-E 总代价 15A-B-D-E 总代价 17 edges { A: [(B, 6), (C, 5)], B: [(D, 6)], C: [(E, 10)], D: [(E, 5)], } def bfs_cost(start, goal): 代价树广度优先每轮对 OPEN 全表按 g 排序 open_list [(start, 0, [start])] closed {} while open_list: open_list.sort(keylambda x: x[1]) # 全表排序 node, g, path open_list.pop(0) if node in closed and closed[node] g: continue closed[node] g if node goal: return path, g for nxt, w in edges.get(node, []): open_list.append((nxt, g w, path [nxt])) return None, None def dfs_cost(start, goal): 代价树深度优先子节点逆序压栈让邻接表靠前的先出栈 stack [(start, 0, [start])] while stack: node, g, path stack.pop() if node goal: return path, g for nxt, w in reversed(edges.get(node, [])): stack.append((nxt, g w, path [nxt])) return None, None print(BFS:, bfs_cost(A, E)) # (A, C, E), 15 print(DFS:, dfs_cost(A, E)) # (A, B, D, E), 17bfs_cost的参数只有起点和终点OPEN 表用列表加每轮排序实现节点被扩展两次时用closed里的旧代价做比较。dfs_cost没有全表排序靠reversed控制压栈顺序让邻接表里靠前的 B 先出栈于是先钻进 A→B→D→E 这条分支。结果 17 大于 15说明深度优先在这个例子里不是最优。这个例子正好暴露一个坑不同教材对“代价树深度优先”的压栈顺序写法不一样有的按子节点代价从小到大压栈有的按生成顺序压栈同一道题可能算出 15也可能算出 17。考试时如果答案和标准答案对不上先检查压栈顺序别急着怀疑自己算错。策略OPEN 表维护方式完备性最优性本题结果代价树广度优先全表按 g 排序完备最优A-C-E15代价树深度优先子节点压栈首不完备不一定最优A-B-D-E174.3 与或树的可解传播与 α-β 剪枝的收手条件与或树和普通搜索树的分水岭在“可解”的定义。终止节点是可解节点一个与节点可解当且仅当它的子节点全都可解一个或节点可解只要它的子节点至少有一个可解。解树就是从根到终止节点、且满足可解传播条件的那棵子树。手算时从叶子往上标“可解/不可解”比从根往下猜快得多。习题里还有和代价法与最大代价法的对比。和代价法把子节点代价相加最大代价法取子节点中的最大值。同一棵与或树两种算法可能给出不同数值题目问哪种就写哪种别混。α-β 剪枝的规则可以压成两句或节点的 α 值如果不能降低父节点的 β 值就可以停止搜索该节点以下的分支这叫 β 剪枝与节点的 β 值如果不能升高父节点的 α 值就可以停止搜索这叫 α 剪枝。写成一个递归框架大致是这样def alphabeta(node, depth, alpha, beta, leaf_value, children, maximizeTrue): maximizeTrue 对应或节点False 对应与节点 if depth 0 or not children.get(node): return leaf_value[node] if maximize: best -10 ** 9 for ch in children[node]: best max(best, alphabeta(ch, depth - 1, alpha, beta, leaf_value, children, False)) alpha max(alpha, best) if beta alpha: break # β 剪枝父节点不会再选这条分支 return best best 10 ** 9 for ch in children[node]: best min(best, alphabeta(ch, depth - 1, alpha, beta, leaf_value, children, True)) beta min(beta, best) if beta alpha: break # α 剪枝父节点不会再选这条分支 return bestalpha初值给负无穷、beta给正无穷leaf_value是端节点估值表children是邻接表。这段代码只负责算倒推值不返回被剪掉的分支想验证剪枝效果得在break处打日志把被剪节点记下来和手算结果对照。注意 α-β 剪枝不改变最终结果只减少搜索量如果剪枝前后根节点值不一样一定是 α、β 的更新顺序写反了。5. 避坑习题集里最容易翻车的五处5.1 符号与子句集层面的三个坑现象归结能推出空子句但答案谓词里是空的。原因目标否定时只加了¬P(y)没加ANSWER(y)或者加了但没把它和¬P(y)做成析取。解决把目标子句固定写成¬P(y) ∨ ANSWER(y)每次归结后检查 ANSWER 的参数是否被置换绑定没绑定的归结式直接丢掉。现象同一道题手算推出Father(C,C)这种明显错误的结论。原因两个子句里用了同名变量归结时没有做标准化分离置换冲突。解决每次归结前先把父被子句的变量改名保证变量集合不相交写代码时用不同的文字名手算时用带下标的 x1、x2 区分。现象自然语言里的“至少有一人”翻译成子句后整个子句集推不出任何东西。原因把析取写成了合取或者把“与此案无关”的否定漏掉一层。解决翻译完先不归结把每条子句代回原句读一遍看真假值是否一致涉及“至少”“至多”“无关”的句子先列真值表再写公式。5.2 搜索与手算层面的两个坑现象代价树深度优先算出来的路径比标准答案长但每一步看着都没错。原因压栈顺序和教材不一致。深度优先的“按代价排序”是排在子节点入栈那一刻不是排在弹出那一刻有的写法按升序压栈有的按生成顺序压栈结果自然不同。解决手画 OPEN 表每一步把表里节点的顺序写出来再和答案对如果顺序对不上先改压栈规则别改路径。现象与或树求出的解树少了一枝可解节点判定却显示根节点可解。原因把与节点的可解条件记成了“子节点至少一个可解”或者把或节点记成了“全部可解”。解决在树上从叶子往根标可解标记与节点必须所有子节点都标可解才能往上标或节点只要一个子节点可解就能往上标标完再画解树解树的叶子必须全是终止节点。排查顺序我一般是这样先查谓词定义和目标子句这两处错了后面全白算再查子句集里的量词和否定用真值表抽一条验证最后才查搜索顺序和 OPEN 表。这个顺序能挡掉大部分“看起来会、一算就错”的情况。6. 把纸面答案跑起来PROLOG 亲属库与 A* 自测脚本6.1 PROLOG 亲属库把逻辑子句跑成可查询的事实习题最后有一道亲属关系的 PROLOG 程序原文用的是 Turbo Prolog 风格的domains / predicates / clauses / goal四段式。这种写法在 Visual Prolog 里能直接跑换到 SWI-Prolog 要改语法这是第一个要注意的地方。把示例里的人名换成代号程序骨架如下domains name symbol sex symbol age integer predicates person(name, sex, age) mother(name, name) father(name, name) brother(name, name) sister(name, name) clauses person(a, m, 21). person(b, m, 22). person(c, w, 23). person(d, w, 24). mother(m1, a). mother(m1, b). mother(m1, c). mother(m1, d). father(a, e). father(e, f). brother(X, Y) :- person(X, m, A1), person(Y, m, A2), mother(Z, X), mother(Z, Y), A1 A2. sister(X, Y) :- person(X, w, A1), person(Y, w, A2), mother(Z, X), mother(Z, Y), A1 A2. goal brother(X, Y), write(X, is , Y, s brother), nl.brother规则里的A1 A2是年龄比较保证输出方向唯一不然同一对兄弟会正反各输出一次。mother(Z,X)和mother(Z,Y)共用同一个 Z表示同母。跑之前先把事实补全否则mother查询会因为缺事实而失败这是第二个坑PROLOG 不会告诉你“事实不够”它只会返回 no。6.2 用 A* 给手算答案做交叉验证第 4 章那张代价图可以再写一个 A* 版本做交叉验证。启发函数取每个节点到 E 的直线估计只要不高估A* 的结果一定和代价树广度优先一致。验证时看两个数路径代价是不是 15扩展节点数是不是比广度优先少。如果路径代价对不上先查启发函数是否可采纳如果扩展节点数反而更多查 OPEN 表里是不是漏了按 f 排序。验证项手算答案脚本输出不一致时先查最短路径A-C-EA-C-E边权是否抄错路径代价1515g 值累加是否重复盗窃案答案乙、丙ANS_b、ANS_c目标子句是否展开兄弟题答案丙ANSWER(C)置换是否绑定到 u从那以后我每次带人复习都要求先把习题答案手推一遍再用脚本跑一遍对照两边对不上才回去翻定义而不是对着答案抄步骤。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
