从状态空间到贝叶斯推理：AI课后习题中的算法思维与工程实现

简介：《人工智能》课后习题答案.doc 是一份面向人工智能课程学习者的习题解答文档，内容涵盖人工智能定义、智能概念、专家系统、知识表示技术、谓词逻辑、语义网络、推理及符号微积分等核心章节，适合辅助课后复习、考前梳理与知识点自查。文档采用 doc 格式，共1个文件，整包大小仅1.51MB，轻量易用，可直接对照教材章节查看参考答案。目前已有1567人在 CSDN 学习下载，需求较为集中。除基础概念外，答案中对状态空间四元组、谓词逻辑公式、语义网络结构等重难点给出了较完整的文字解析和示例，能帮助读者理解知识表示的内在逻辑，掌握典型题目的解题思路。对于正在学习人工智能导论、需要快速获取习题参考的读者，这份答案文档具备较强的实用性与参考价值。

1. 人工智能课后习题里的形式化思维训练

这份《人工智能》课后习题答案.doc，我拆开看了好几遍。它不是简单的背诵条目，而是把绪论、知识表示、问题求解、推理和不精确推理五块串成了一条完整的思维链。最早我也觉得课后答案没什么用，直到照着状态空间四元组去写了一个八数码求解器，才发现这些题目其实在逼你建立“把业务问题变成计算机能处理的形式”的能力。用谓词逻辑描述婚姻关系，用语义网络表达概念分类，这些一旦落到代码里，就是知识图谱和规则引擎的雏形。适合正在补人工智能基础、准备考研复试或做课程设计的人；对已经写业务代码的工程师，也能帮你把散落的术语钉回理论原点。

2. 知识表示三件套：状态空间、谓词逻辑与语义网络

知识表示是整份答案里信息密度最高的一章。状态空间、谓词逻辑、语义网络这三种表示方式，分别对应了程序员的三种思维习惯：过程式、声明式和图结构。理解清楚它们的边界，比背下定义重要得多。

2.1 状态空间四元组：从S0到G的求解路径

状态空间被定义为一个四元组(S, O, S0, G)，其中 S 是状态集合，O 是操作算子集合，S0 是初始状态，G 是目标状态。原文里特意强调“求解路径”是从 S0 结点到 G 结点的路径，而解是有限操作算子序列。这个抽象非常接近现代规划算法的底层模型，比如 PDDL 里的init、goal和 action 定义。

用 Python 写一个最小实现来理解这个四元组：

from collections import namedtuple StateSpace = namedtuple('StateSpace', ['S', 'O', 'S0', 'G']) # 八数码的状态集合：0~8 的排列，0 表示空格 S = [tuple(p) for p in __import__('itertools').permutations(range(9))] # 操作算子集合：对空格位置的四个移动方向 def operators(state, action): idx = state.index(0) # 空格位置 r, c = idx // 3, idx % 3 nr, nc = r + {'UP': -1, 'DOWN': 1}.get(action, 0), c + {'LEFT': -1, 'RIGHT': 1}.get(action, 0) if 0 <= nr < 3 and 0 <= nc < 3: new = list(state) new[idx], new[nr * 3 + nc] = new[nr * 3 + nc], new[idx] return tuple(new) return None O = ['UP', 'DOWN', 'LEFT', 'RIGHT'] S0 = (2, 8, 3, 1, 6, 4, 7, 0, 5) # 某个打乱状态 G = (1, 2, 3, 8, 0, 4, 7, 6, 5) # 目标状态 ss = StateSpace(S, O, S0, G)

这里把 S 定义成所有排列的集合，实际工程里不可能全部预计算，更常见的做法是用生成器按需产出合法状态。operators函数就是 O 的具象化：它接受当前状态和动作，返回后继状态或None。S0 和 G 分别对应输入条件和验收条件。四元组的意义在于，它把“问题求解”拆分成了“状态迁移”和“路径搜索”两个独立问题，后面第三问的汉诺塔也正是用三元组(A, B, C)重复了这个套路。

2.2 谓词逻辑：把关系写成一阶公式

原文用晁盖和高衙内的例子讲解谓词逻辑，核心是把“人受法律管制”和“犯罪受惩罚”这类常识写成蕴含式。一阶谓词逻辑比命题逻辑强的地方在于，它能表达“对所有的 x”和“存在某个 x”，也就是全称量词和存在量词。

婚姻推理那道题非常适合用代码模拟。题目给出的五条约束，本质上是一个约束满足问题：

people = ['李', '周', '钱', '徐', '王', '陈', '孙', '吴'] # 条件③：李的爱人是陈的爱人的表哥 -> 李的爱人是男性，李是女性 # 条件⑤：李、徐、周是同一性别 # 条件①：王与周不构成夫妻 males = ['王', '陈', '孙', '吴'] females = ['李', '徐', '周', '钱'] not_pair = {('王', '周'), ('陈', '徐'), ('陈', '周'), ('李', '陈'), ('吴', '徐'), ('吴', '周')} def valid(pair): a, b = pair return a in males and b in females and pair not in not_pair # 按约束逐个排除，最后得出唯一匹配

这题的推理步骤看起来像文字游戏，实际就是回溯算法的人工版本。你可以在代码里用itertools.permutations生成所有夫妻配对，再过滤not_pair约束，得到结果：吴与李、王与徐、孙与周。谓词逻辑在这里的价值，是帮你把自然语言里的“表哥”“夫妻”这些关系拆成无歧义的谓词和量词，写成规则后，机器才能处理。

2.3 语义网络与框架：有向图比公式更直观

语义网络用节点表示概念、有向弧表示关系。原文给了知更鸟、鸵鸟和鸟的 I SA 层次图。这种表示在代码里可以直接用邻接表：

semantic_net = { '知更鸟': {'isa': '鸟', 'colour': '红', 'habit': '春至秋'}, '鸵鸟': {'isa': '鸟', 'can': '跑', 'not_can': '飞'}, '鸟': {'isa': '动物', 'can': '飞'}, } def inherit(net, node, attr, default=None): while node in net: if attr in net[node]: return net[node][attr] node = net[node].get('isa') return default print(inherit(semantic_net, '知更鸟', 'can')) # 得到 "飞" print(inherit(semantic_net, '鸵鸟', 'can')) # 得到 "跑"

语义网络擅长表达继承关系，但也容易陷入多继承冲突。比如“企鹅既是鸟又会游泳”，如果“鸟”节点的can属性是“飞”，那么企鹅就会错误继承“飞”。工程上的处理方式有两种：给弧加上否定标记not_can，或者在继承时优先取离节点更近的属性。框架系统比语义网络更结构化，它把一组属性打包成槽，正好解决了产生式系统里规则互相干扰的问题。原文 2.11 已经点出来了：框架适合做产生式系统的组织外壳，这也是后来专家系统工具里常见的做法。

三种表示方式的选型，可以简单归纳为：状态空间适合“状态多、动作少”的过程性问题；谓词逻辑适合“关系复杂、需要做推导”的验证性问题；语义网络适合“概念层级明确、有分类体系”的知识组织问题。实际系统里三者经常混用。

3. 从盲目搜索到启发式搜索：策略的参数边界

问题求解这一章是所有章节里代码含量最高的。广度优先、深度优先、A*、博弈剪枝，这些算法今天仍然是路径规划和游戏 AI 的核心。要理解它们，先看 OPEN 表里节点的压入位置。

3.1 广度优先与深度优先：OPEN 表的压入方向

原文 3.1 说得很直接：两者的唯一区别是后继节点放在 OPEN 表的末端还是前端。广度优先用 FIFO 队列，深度优先用 LIFO 栈。用 Python 写一对对照实现：

from collections import deque def bfs(start, goal, expand): open_list = deque([start]) visited = set() while open_list: node = open_list.popleft() # 从左侧取出，自然 FIFO if node == goal: return True if node in visited: continue visited.add(node) open_list.extend(expand(node)) # 新节点追加到右侧 return False def dfs(start, goal, expand): open_list = [start] visited = set() while open_list: node = open_list.pop() # 从右侧取出，LIFO if node == goal: return True if node in visited: continue visited.add(node) open_list.extend(expand(node)) # 新节点追加到右侧 return False

两个函数只有两行不同：popleft()对应pop()，append的位置决定了搜索方向。广度优先一定能找到解（完备性），但状态多时内存爆炸；深度优先内存省，却可能一头扎进深的无底洞。原文举的例子很有代表性：积木问题用广度优先，因为状态空间浅；国际象棋这类状态空间极深的问题，深度优先不剪枝基本跑不完。实际工程里我一般会加一个迭代加深来弥补缺失步骤的问题：先限制深度为 1 做深度优先，再逐步加深。

3.2 启发函数的可采纳性：传教士与野人

传教士与野人问题里，原文定义了h1 = M + C - 2B，并证明它满足 A* 条件，而h2 = M + C不满足。这个区别是实战中选估价函数最容易踩的坑。

def h1(state): M, C, B = state # 左岸传教士、左岸野人、船是否在左岸 return M + C - 2 * B def h2(state): M, C, _ = state return M + C # 反例：状态 (1,1,1)，左岸 1 传教士 1 野人，船在左岸 # h2 = 1 + 1 = 2，但实际只需 1 次摆渡就能把两人都运到右岸 print(h1((1, 1, 1)), h2((1, 1, 1))) # 输出 -1 2

A* 的可采纳性要求h(n) <= h*(n)，其中h*是到目标的真实代价。h2在目标附近会高估代价，导致搜索提前丢弃最优路径。h1里的-2B是点睛之笔：船在左岸时，一次摆渡最多运走两人，但最后必须有人把船开回来，所以最少的摆渡次数一定比“裸人数”小。从这个例子能学到一个通用方法：分析一个启发函数是否可采纳，先找最宽松的最优解下界，再看它是否违反限制条件。实际项目里多数启发函数都偏保守，宁可低估不可高估。

3.3 α-β 剪枝：估值函数的边界更新

博弈搜索的 α-β 剪枝，是极小极大算法的高效版。原文的伪代码给得比较粗糙，补一个可以直接跑的版本：

def alphabeta(depth, alpha, beta, node, maximizing): if depth == 0 or node.terminal(): return node.evaluate() if maximizing: # MAX 节点 value = -float('inf') for child in node.children(): value = max(value, alphabeta(depth - 1, alpha, beta, child, False)) alpha = max(alpha, value) if alpha >= beta: # β 剪枝：MIN 侧已经不可能选这条路 break return value else: # MIN 节点 value = float('inf') for child in node.children(): value = min(value, alphabeta(depth - 1, alpha, beta, child, True)) beta = min(beta, value) if beta <= alpha: # α 剪枝：MAX 侧不会选这条路 break return value

剪枝靠的是alpha和beta两个窗口：alpha是 MAX 当前能保证的最低收益，beta是 MIN 当前能接受的最高成本。一旦某个子节点的收益越过了窗口边界，后面的兄弟节点就没必要再展开。实际使用中要注意搜索顺序——先评价最可能的走法，剪枝效率最高；如果顺序很差，α-β 退化成普通极小极大。工程里常配合置换表记忆已评估节点，能进一步减少重复计算。

4. 归结反演与推理机：把逻辑公式变成可执行流程

推理技术这章，很多教材只讲概念，但这部分恰恰是专家系统规则引擎的雏形。正向、反向、归结，三类机制今天仍然能在 Drools、Prolog 里找到对应。

4.1 正向推理与反向推理：RS 与目标驱动

正向推理从已知事实出发，循环匹配规则，把结论加入数据库；反向推理先假设目标，再反向找支持证据。一个最小正向推理引擎可以这样写：

# 规则库：每个规则是 (前提集合, 结论) rules = [ ({'HUMAN(x)'}, 'LAWED(x)'), ({'COMMIT(x)', 'LAWED(x)'}, 'PUNISHED(x)'), ({'PUNISHED(x)'}, 'NEED_INVESTIGATION(x)'), ] facts = set(['HUMAN(晁盖)', 'COMMIT(晁盖)']) def forward_chaining(rules, facts): changed = True while changed: changed = False for premises, conclusion in rules: matched = all(any(p.replace('x', fact[fact.index('(')+1:-1]) in facts for fact in facts) for p in premises) if matched and conclusion not in facts: facts.add(conclusion) changed = True return facts

这里用字符串替换模拟变量绑定，简化了合一过程。正向推理的优点是实现简单、只要事实推不出来了就停；缺点是中间结论会爆炸，需要冲突消解策略来控制哪条规则先执行。反向推理则先选中目标PUNISHED(晁盖)，再去找支持它的COMMIT和LAWED，目的性强很多，适合做解释系统——用户可以问“为什么得出这个结论”，系统直接回溯推理链路。

4.2 归结反演：目标取反之后一切都简单了

归结反演的核心思路是：把前提写成子句集，把目标的否定也写成子句，加入子句集，然后反复归结，直到推出空子句NIL。空子句等价于矛盾，矛盾的出现意味着原目标得证。原文 4.5 的子句集转换有一个值得注意的细节：变量要改名为不同记号，防止不同量词的变量混淆。

用 Python 演示一个最基础的归结操作：

def resolve(c1, c2): for lit1 in c1: for lit2 in c2: if lit1[1:] == lit2[1:] and lit1[0] != lit2[0]: # 找到互补对，取集合差后得到归结式 merged = [lit for lit in c1 + c2 if lit != lit1 and lit != lit2] return set(merged) return None # 子句集：{P(a), ~P(x)或Q(x), ~Q(y)} clauses = [ {'P(a)'}, {'~P(x)', 'Q(x)'}, {'~Q(a)'}, ] while True: new_clauses = set() for i in range(len(clauses)): for j in range(i + 1, len(clauses)): r = resolve(clauses[i], clauses[j]) if r == set(): print('得到空子句，证明完成') raise SystemExit if r: new_clauses.add(frozenset(r)) if not new_clauses: break clauses.extend(list(new_clauses))

这个实现没有做合一，遇到P(f(x))和P(f(a))这种需要代换的情况就失效了。工程化的归结器一般用最一般合一算法把两个原子公式统一成同一个形式。但基本流程已经能跑通：从P(a)和~P(x)∨Q(x)归结出Q(a)，再和~Q(a)归结得到空子句。整个归结反演完全机械，非常适合做自动定理证明。

4.3 冲突消解策略的工程映射

原文 4.2 列出了专一性排序、规则排序、数据排序、就近排序、上下文限制等策略。这些策略本质上都是给规则库里的规则分配优先级，对应到代码里就是规则对象上的priority字段。

在规则引擎里，这些策略常常被混合使用，比如先按上下文过滤，再按专一性排序，最后按规则优先级决定。理解了这些细节，再看 Drools 的 salience 和 agenda-group 就不会觉得神秘了。

5. 不精确推理：贝叶斯更新与 LS/LN 参数语义

不精确推理是专家系统走向实用的关键。现实世界的证据总是带噪声，规则也不完全可靠。这份答案里的主观贝叶斯方法，恰好提供了一个有严格概率基础的参数体系。

5.1 贝叶斯后验计算：证据组合的顺序无关性

原文 5.3 给出了单证据和多证据的 Bayes 计算。用 Python 可以直接复现：

prior = [0.5, 0.3, 0.2] # 先验 P(H1), P(H2), P(H3) likelihood = [ # 每个证据下的条件概率 [0.4, 0.3, 0.3], # P(E1|H) [0.6, 0.2, 0.2], # P(E2|H) ] def bayes_update(prior, likelihood, evidence_indices): joint = [] for i, p in enumerate(prior): prob = p for e in evidence_indices: prob *= likelihood[e][i] joint.append(prob) norm = sum(joint) return [x / norm for x in joint] print(bayes_update(prior, likelihood, [0])) # 单证据 print(bayes_update(prior, likelihood, [0, 1])) # 双证据

注意这里的假设是证据之间条件独立，否则需要联合分布。双证据的结果是 0.59、0.34、0.064，说明 H1 和 H2 的后验上升，H3 下降。工程里用这个函数时，要注意先验概率的更新是序列相关的，但最终结果与证据顺序无关，只要按全概率归一化即可。

5.2 主观贝叶斯的 LS/LN：充分性与必要性

主观贝叶斯用LS和LN两个参数描述规则的可信度。LS是充分性量度，表示 E 出现时对 H 的支持程度；LN是必要性量度，表示 E 不出现时对 H 的支持程度。一个关键约束是：LS和LN不能同时大于 1 或同时小于 1，因为 E 出现和不出现不可能都对 H 有利。

用代码做参数校验：

def valid_lsln(LS, LN): if LS > 1 and LN > 1: return False if LS < 1 and LN < 1: return False return True

这个校验能拦截很多人工配置错误。比如某条规则“发烧 → 感冒”LS=10，但同时LN=5就矛盾：发烧支持感冒，不发烧居然也支持感冒，这在逻辑上说不通。实际构建专家系统时，我习惯把 LS/LN 直接放进规则对象，推理时用一个公式合并多条规则的贡献，比如odds(H|E) = LS * odds(H)，这样每条规则的增量是独立的，方便回溯和解释。

5.3 一个可复用的验证技巧

面对不精确推理代码，最难调的是先验概率。一个常见做法是把贝叶斯更新改造成对数几率（log odds），这样乘法和除法都变成加法，数值稳定性更好：

import math def update_with_log_odds(log_prior, log_likelihood_ratio, evidence_occurred): if evidence_occurred: return log_prior + log_likelihood_ratio else: return log_prior - log_likelihood_ratio

用对数几率避免概率下溢，同时让参数语义更直观：log_likelihood_ratio为正是支持，为负是反对。最后再通过sigmoid转回概率。这个小技巧在写贝叶斯垃圾邮件分类器时同样适用，值得收进你的工具箱。

本文还有配套的精品资源，点击获取