简介面向人工智能期末考试复习的结构化辅导笔记覆盖逻辑推理、搜索策略与决策制定等核心考点适合高校本科生、考研学生及需要系统梳理AI基础知识的自学者适用于期末冲刺、章节复习与考前查漏补缺。文档以章节条目形式展开逐一精讲复合代换、最一般合一、谓词公式化为子句集、归结原理与归结反演等逻辑推理重点并结合可信度方法说明不确定性推理的应用搜索部分则对比宽度优先与深度优先的盲目搜索引入启发式搜索、解树代价计算以及博弈树极大极小分析法对各算法特点、Open表队列/堆栈结构、可解性与搜索效率等易混淆点作了清晰梳理帮助建立从原理到题型的完整知识链路。资源为1份docx文档共5.64MB内容层次分明、公式与过程说明兼有方便打印背诵或碎片化回顾。该文档已有1318人学习特别适合考前冲刺使用也可作为课堂笔记补充。1. 从考试提纲到搜索系统为什么逻辑推导和状态搜索是同一件事拿到一份人工智能期末复习提纲时我先做了个试验把复合代换、归结反演、宽度优先搜索这些条目当成独立知识点去记结果过一遍就混淆了。后来换了个角度把归结过程看成在一个子句集构成的搜索空间里做目标查找把BFS/DFS看成同一套状态扩展框架下的不同策略所有内容就串起来了。谁适合读正在准备人工智能导论或人工智能基础期末考试的人以及需要快速重建AI核心概念的知识工程师都有用。复习的核心不是背定义而是把逻辑推理、搜索和博弈看成同一个状态空间问题的不同约束条件。2. 谓词逻辑与归结反演复合代换、MGU、子句集与归结原理2.1 复合代换的运算时机与表示代换的本质是一个从变量到项的映射记作θ {x1/t1, x2/t2}。复合代换处理的是两个代换叠加时的应用顺序问题。设 θ 作用于公式后得到中间结果再用 σ 作用等价于直接使用复合代换 θ∘σ。注意这里的“先 θ 后 σ”不是简单拼接而是要对 θ 中每一项的变量递归应用 σ同时把 σ 中未被 θ 覆盖的项并入结果。def compose_subst(theta, sigma): theta 与 sigma 的复合返回新的代换字典 result {} for x, t in theta.items(): result[x] apply_subst(t, sigma) # 先对t中的变量用sigma替换 for y, s in sigma.items(): if y not in result: result[y] s # 删掉被替换成自身的无用映射 return {k: v for k, v in result.items() if k ! v}这里的apply_subst负责递归替换一个项中出现的变量。如果不做递归只做一层替换复合代换在嵌套函数项时就会出错。例如θ {x/f(y), y/z}和σ {y/a}按规则应得到{x/f(a), y/a}而不是{x/f(y), y/a}。这个细节是考试里常见的陷阱。2.2 最一般合一MGU的求解流程最一般合一是指两个表达式在代换后完全相同且这个代换是所有可能合一者中最一般的。求解引擎一般用递归统一算法也就是向量的 unification。这个算法让我想到状态搜索里的解路径每一步都在消解语法树中的差异点。def unify_terms(x, y, bindingsNone): if bindings is None: bindings {} if x in bindings: return unify_terms(bindings[x], y, bindings) if y in bindings: return unify_terms(x, bindings[y], bindings) if x y: return bindings if isinstance(x, str) and x.islower(): # 变量 bindings[x] y return bindings if isinstance(y, str) and y.islower(): bindings[y] x return bindings if isinstance(x, list) and isinstance(y, list) and x and y: if x[0] y[0]: # 谓词名相同 return unify_terms(x[1:], y[1:], bindings) return None这个实现假设项用列表表达例如P(f(x), y)写成[P, [f, x], y]。参数bindings是用来保存中间代换的字典递归到最底层时返回完整代换。考试时只要记住MGU 不唯一的情况几乎不存在遇到需要选择时优先选变量指向更简单的项。提示合一失败多半是谓词名不同、参数个数不同或出现了所谓“发生检查”问题——变量被代换到包含自身的项中。2.3 谓词公式到子句集的标准化步骤把合式公式转成子句集有七步考试常考其中三步删掉全称量词、把合取词用逗号表示、使每个子句的变量符号不同。实际转换时我习惯按这个顺序走能减少一半错误。步骤操作目的1消去蕴含和等价把 → 和 ↔ 换成 ¬、∨、∧2否定内移把 ¬ 移到原子公式前3变量标准化让每个量词绑定唯一变量名4Skolem化消去存在量词用Skolem函数替代5消去全称量词删除所有 ∀默认全称6化为合取范式展开成 ∧ 连接的 ∨ 子句7消去合取词更改变量名每个子句独立不共享变量例如∀x(P(x) → ∃y(Q(x,y) ∧ ¬R(y)))先消去蕴含得到∀x(¬P(x) ∨ ∃y(Q(x,y) ∧ ¬R(y)))Skolem化时把 y 替换成s(x)消去全称量词后得到¬P(x) ∨ (Q(x,s(x)) ∧ ¬R(s(x)))再展开成两个子句¬P(x) ∨ Q(x,s(x))和¬P(x) ∨ ¬R(s(x))。最后一步更改变量名是为了后续合一时避免冲突。Skolem化有个容易踩的坑如果存在量词前面有全称量词那么必须用函数符号而不能用常量。这就是为什么∃y在∀x后变成了s(x)。很多考试题在这里故意给一个错误的常量替换让你找不到矛盾。2.4 归结原理与归结反演的工程实现命题逻辑归结很简单两个子句C1 A ∨ B、C2 ¬A ∨ C归结得到B ∨ C。谓词逻辑归结需要先对互补文字做合一再做命题归结。归结反演则先把目标取否定加入子句集反复消解直到推出空子句也就证明了原目标。def resolution_proof(clauses, goal, max_steps100): clauses [negate(goal)] clauses for _ in range(max_steps): new [] for i in range(len(clauses)): for j in range(i1, len(clauses)): resolvents, mgu resolve_pair(clauses[i], clauses[j]) if resolvents is None: continue if mgu is not None: resolvents [apply_subst(r, mgu) for r in resolvents] for r in resolvents: if not r: return True # 推出空子句 new.append(r) clauses.extend(new) return False这里resolve_pair接受两个子句返回可能的归结子句列表和所用的MGU。如果没有可归结的文字就返回None。注意每次把新子句加入集合后要设置步数上限max_steps防止无限循环。考试计算题要求手工推演不需要写代码但理解这个循环结构能帮你判断反演什么时候终止。归结反演的核心逻辑是如果加入目标否定后能推出空子句就说明原目标被证明。在手工练习时可以拿两个子句先画互补文字再写MGU并替换最后删去互补项。顺序反了容易把MGU写成只适用于其中一个子句导致结果里出现未替换的变量。这个错误比归结本身更常见。3. 从盲目搜索到启发式搜索BFS、DFS、A*的实现与参数3.1 Open表的数据结构差异为什么决定搜索顺序搜索算法的骨架都一样把初始状态放进Open表循环从Open表弹出一个节点扩展后继节点做目标判定直到Open表为空。BFS和DFS的区别只在弹出节点的策略。Open表用队列就是BFS先进先出层次浅的节点先被扩展所以在单位代价下第一次到达目标就是最短路径。Open表用栈就是DFS先进后出会一直往深处走可能陷入很深的无用分支。很多人把“宽度优先总能找到最好解”理解为总能找到最小代价解严格说不成立。BFS保证的是“如果每条边的代价相等首次找到的目标路径步数最少”。如果边权不同需要改用Dijkstra或A*。这个区分在考试简答题中经常被考察。3.2 盲目搜索BFS与DFS的代码骨架def bfs_shortest_path(graph, start, goal): from collections import deque open_queue deque([start]) closed set() parent {start: None} while open_queue: node open_queue.popleft() if node goal: return reconstruct_path(parent, node) if node in closed: continue closed.add(node) for nxt in graph.neighbors(node): if nxt not in parent: parent[nxt] node open_queue.append(nxt) return None这里closed集合记录已扩展节点防止循环。parent字典用于回溯路径。DFS只需把popleft改成pop也就是从同一端弹出实现栈行为。如果状态空间很大DFS的栈深度可能超过Python默认递归限制所以一般用显式栈循环而不是递归。维度BFSDFSOpen表队列堆栈空间复杂度高低是否保证最短单位代价下是否适用场景迷宫最短路径解存在且深度浅3.3 启发式搜索的评估函数设计启发式搜索的核心是选择下一个扩展节点时引入评估函数f(n) g(n) h(n)。g(n)是从起点到当前节点的实际代价h(n)是估计剩余代价。A*算法要求h(n)可采纳即估计值不超过真实剩余代价否则可能得不到最优解。def astar_search(graph, start, goal, heuristic): import heapq open_heap [(0, start)] # (f, node) g_score {start: 0} parent {start: None} while open_heap: _, node heapq.heappop(open_heap) if node goal: return reconstruct_path(parent, node) for nxt, cost in graph.neighbors_with_cost(node): tentative_g g_score[node] cost if tentative_g g_score.get(nxt, float(inf)): g_score[nxt] tentative_g parent[nxt] node f tentative_g heuristic(nxt, goal) heapq.heappush(open_heap, (f, nxt)) return None这里堆结构就是优先队列相当于Open表变成了按f值排序的优先级队列。启发式函数heuristic的设计直接影响搜索效率曼哈顿距离和欧式距离是最常用的两种。如果h恒为0A*退化为Dijkstra如果g恒为0则变成贪心最佳优先搜索速度快但不保证最优。实际考试里给出状态转移图让你计算BFS扩展序列的题型只需要维护一个队列记录每个节点的父指针。关键是区分“已放入Open表”和“已被扩展”只有被扩展的节点才进closed表。很多学生把进入Open表的节点直接视为已扩展导致重复扩展和路径回溯错误。4. 不确定性推理与解树代价可信度方法及其在状态评估中的角色4.1 可信度模型的组合计算可信度方法最早用于医疗专家系统核心是给每条规则一个可信度因子CF(H,E)取值范围 [-1,1]。正数表示支持负数表示反对。组合多个证据时有两条基本公式证据合取的CF取最小值证据析取的CF取最大值。多条规则指向同一结论时还要合成规则结果。def combine_cf(cf_e1, cf_e2): if cf_e1 0 and cf_e2 0: return cf_e1 cf_e2 - cf_e1 * cf_e2 if cf_e1 0 and cf_e2 0: return -(abs(cf_e1) abs(cf_e2) - abs(cf_e1) * abs(cf_e2)) return (cf_e1 cf_e2) / (1 - min(abs(cf_e1), abs(cf_e2)))这个函数实现了两条规则同向支持和反向支持时的合成逻辑。分母1 - min(abs(cf_e1), abs(cf_e2))在分母为零时说明两方完全冲突这时无法合成。考试计算题给两个证据的可信度要求合成时先判断是否同号再套公式。一个完整的计算例子规则IF A THEN B的CF为0.8证据A本身的可信度CF(A)0.6则结论B获得的可信度为0.6 * 0.8 0.48。如果另一条规则IF C THEN B的CF为0.5且CF(C)0.7那么B从第二条规则获得0.35。最后把0.48和0.35用上面的同号公式合成得到0.48 0.35 - 0.48*0.35 0.662。这个顺序在综合诊断类题目里很常见。4.2 解树的代价与搜索策略的联系解树的代价在博弈和与或树搜索中出现是评估一个候选解是否值得继续扩展的指标。常见的代价计算有两种或节点取子节点最小代价与节点取子节点最大代价。这个规则和极大极小分析是同一个思想。节点类型代价计算语义或节点min(子节点代价)存在一个解即可与节点max(子节点代价)所有子问题都解决才结束如果要把这段逻辑写成代码递归结构非常直接def solution_tree_cost(node): if node.is_leaf(): return node.cost if node.type or: return min(solution_tree_cost(c) for c in node.children) else: return max(solution_tree_cost(c) for c in node.children)这里node.type字段区分与节点和或节点。考试题中常见的陷阱是混淆或节点与与节点的计算方向比如把与节点当成所有子节点代价相加。记住解树代价不是一个“总代价”概念而是瓶颈代价尤其是与节点最大子节点代价决定了整个解树的代价。5. 博弈树极大极小分析的工程技巧5.1 极大极小递归的剪枝条件极大极小分析假设对手总是选择让自己收益最小的落点因此在博弈树中交替使用 max 和 min 操作。基础实现会展开整棵博弈树节点数随深度指数增长不实用。alpha-beta剪枝能在保持结果不变的前提下剪掉不可能影响最终选择的子树。def minimax_alpha_beta(node, depth, alpha, beta, maximizing): if depth 0 or node.is_terminal(): return node.evaluate() if maximizing: value float(-inf) for child in node.children(): value max(value, minimax_alpha_beta(child, depth-1, alpha, beta, False)) alpha max(alpha, value) if alpha beta: break return value else: value float(inf) for child in node.children(): value min(value, minimax_alpha_beta(child, depth-1, alpha, beta, True)) beta min(beta, value) if alpha beta: break return valuealpha是 max 方当前能保证的最低收益下界beta是 min 方当前能接受的最高收益上界。一旦alpha beta说明当前节点不可能被上层采用继续扩展只会浪费计算。5.2 子节点排序对剪枝效率的影响剪枝效率非常依赖子节点的访问顺序。理想的顺序是先评估最有可能改变上下界的节点这样能尽快触发剪枝。比如在国际象棋或五子棋中先搜索中心区域、吃子动作或历史命中率高的落点再搜索边缘点。这个优化比单纯把搜索深度加一层更划算。实际工程里通常还会在depth 2时先做一轮快速静态评估来排序接近应用层的做法是维护一张历史置换表。如果一个实现剪枝率上不去检查方向多半是alpha和beta更新位置是否正确。max 节点在更新子节点返回后必须立刻更新alphamin 节点必须立刻更新beta并且把比较放在循环内。把alpha beta放在循环外等于没剪枝。本文还有配套的精品资源点击获取 AI核心考点精讲：归结反演、搜索算法与博弈树
简介面向人工智能期末考试复习的结构化辅导笔记覆盖逻辑推理、搜索策略与决策制定等核心考点适合高校本科生、考研学生及需要系统梳理AI基础知识的自学者适用于期末冲刺、章节复习与考前查漏补缺。文档以章节条目形式展开逐一精讲复合代换、最一般合一、谓词公式化为子句集、归结原理与归结反演等逻辑推理重点并结合可信度方法说明不确定性推理的应用搜索部分则对比宽度优先与深度优先的盲目搜索引入启发式搜索、解树代价计算以及博弈树极大极小分析法对各算法特点、Open表队列/堆栈结构、可解性与搜索效率等易混淆点作了清晰梳理帮助建立从原理到题型的完整知识链路。资源为1份docx文档共5.64MB内容层次分明、公式与过程说明兼有方便打印背诵或碎片化回顾。该文档已有1318人学习特别适合考前冲刺使用也可作为课堂笔记补充。1. 从考试提纲到搜索系统为什么逻辑推导和状态搜索是同一件事拿到一份人工智能期末复习提纲时我先做了个试验把复合代换、归结反演、宽度优先搜索这些条目当成独立知识点去记结果过一遍就混淆了。后来换了个角度把归结过程看成在一个子句集构成的搜索空间里做目标查找把BFS/DFS看成同一套状态扩展框架下的不同策略所有内容就串起来了。谁适合读正在准备人工智能导论或人工智能基础期末考试的人以及需要快速重建AI核心概念的知识工程师都有用。复习的核心不是背定义而是把逻辑推理、搜索和博弈看成同一个状态空间问题的不同约束条件。2. 谓词逻辑与归结反演复合代换、MGU、子句集与归结原理2.1 复合代换的运算时机与表示代换的本质是一个从变量到项的映射记作θ {x1/t1, x2/t2}。复合代换处理的是两个代换叠加时的应用顺序问题。设 θ 作用于公式后得到中间结果再用 σ 作用等价于直接使用复合代换 θ∘σ。注意这里的“先 θ 后 σ”不是简单拼接而是要对 θ 中每一项的变量递归应用 σ同时把 σ 中未被 θ 覆盖的项并入结果。def compose_subst(theta, sigma): theta 与 sigma 的复合返回新的代换字典 result {} for x, t in theta.items(): result[x] apply_subst(t, sigma) # 先对t中的变量用sigma替换 for y, s in sigma.items(): if y not in result: result[y] s # 删掉被替换成自身的无用映射 return {k: v for k, v in result.items() if k ! v}这里的apply_subst负责递归替换一个项中出现的变量。如果不做递归只做一层替换复合代换在嵌套函数项时就会出错。例如θ {x/f(y), y/z}和σ {y/a}按规则应得到{x/f(a), y/a}而不是{x/f(y), y/a}。这个细节是考试里常见的陷阱。2.2 最一般合一MGU的求解流程最一般合一是指两个表达式在代换后完全相同且这个代换是所有可能合一者中最一般的。求解引擎一般用递归统一算法也就是向量的 unification。这个算法让我想到状态搜索里的解路径每一步都在消解语法树中的差异点。def unify_terms(x, y, bindingsNone): if bindings is None: bindings {} if x in bindings: return unify_terms(bindings[x], y, bindings) if y in bindings: return unify_terms(x, bindings[y], bindings) if x y: return bindings if isinstance(x, str) and x.islower(): # 变量 bindings[x] y return bindings if isinstance(y, str) and y.islower(): bindings[y] x return bindings if isinstance(x, list) and isinstance(y, list) and x and y: if x[0] y[0]: # 谓词名相同 return unify_terms(x[1:], y[1:], bindings) return None这个实现假设项用列表表达例如P(f(x), y)写成[P, [f, x], y]。参数bindings是用来保存中间代换的字典递归到最底层时返回完整代换。考试时只要记住MGU 不唯一的情况几乎不存在遇到需要选择时优先选变量指向更简单的项。提示合一失败多半是谓词名不同、参数个数不同或出现了所谓“发生检查”问题——变量被代换到包含自身的项中。2.3 谓词公式到子句集的标准化步骤把合式公式转成子句集有七步考试常考其中三步删掉全称量词、把合取词用逗号表示、使每个子句的变量符号不同。实际转换时我习惯按这个顺序走能减少一半错误。步骤操作目的1消去蕴含和等价把 → 和 ↔ 换成 ¬、∨、∧2否定内移把 ¬ 移到原子公式前3变量标准化让每个量词绑定唯一变量名4Skolem化消去存在量词用Skolem函数替代5消去全称量词删除所有 ∀默认全称6化为合取范式展开成 ∧ 连接的 ∨ 子句7消去合取词更改变量名每个子句独立不共享变量例如∀x(P(x) → ∃y(Q(x,y) ∧ ¬R(y)))先消去蕴含得到∀x(¬P(x) ∨ ∃y(Q(x,y) ∧ ¬R(y)))Skolem化时把 y 替换成s(x)消去全称量词后得到¬P(x) ∨ (Q(x,s(x)) ∧ ¬R(s(x)))再展开成两个子句¬P(x) ∨ Q(x,s(x))和¬P(x) ∨ ¬R(s(x))。最后一步更改变量名是为了后续合一时避免冲突。Skolem化有个容易踩的坑如果存在量词前面有全称量词那么必须用函数符号而不能用常量。这就是为什么∃y在∀x后变成了s(x)。很多考试题在这里故意给一个错误的常量替换让你找不到矛盾。2.4 归结原理与归结反演的工程实现命题逻辑归结很简单两个子句C1 A ∨ B、C2 ¬A ∨ C归结得到B ∨ C。谓词逻辑归结需要先对互补文字做合一再做命题归结。归结反演则先把目标取否定加入子句集反复消解直到推出空子句也就证明了原目标。def resolution_proof(clauses, goal, max_steps100): clauses [negate(goal)] clauses for _ in range(max_steps): new [] for i in range(len(clauses)): for j in range(i1, len(clauses)): resolvents, mgu resolve_pair(clauses[i], clauses[j]) if resolvents is None: continue if mgu is not None: resolvents [apply_subst(r, mgu) for r in resolvents] for r in resolvents: if not r: return True # 推出空子句 new.append(r) clauses.extend(new) return False这里resolve_pair接受两个子句返回可能的归结子句列表和所用的MGU。如果没有可归结的文字就返回None。注意每次把新子句加入集合后要设置步数上限max_steps防止无限循环。考试计算题要求手工推演不需要写代码但理解这个循环结构能帮你判断反演什么时候终止。归结反演的核心逻辑是如果加入目标否定后能推出空子句就说明原目标被证明。在手工练习时可以拿两个子句先画互补文字再写MGU并替换最后删去互补项。顺序反了容易把MGU写成只适用于其中一个子句导致结果里出现未替换的变量。这个错误比归结本身更常见。3. 从盲目搜索到启发式搜索BFS、DFS、A*的实现与参数3.1 Open表的数据结构差异为什么决定搜索顺序搜索算法的骨架都一样把初始状态放进Open表循环从Open表弹出一个节点扩展后继节点做目标判定直到Open表为空。BFS和DFS的区别只在弹出节点的策略。Open表用队列就是BFS先进先出层次浅的节点先被扩展所以在单位代价下第一次到达目标就是最短路径。Open表用栈就是DFS先进后出会一直往深处走可能陷入很深的无用分支。很多人把“宽度优先总能找到最好解”理解为总能找到最小代价解严格说不成立。BFS保证的是“如果每条边的代价相等首次找到的目标路径步数最少”。如果边权不同需要改用Dijkstra或A*。这个区分在考试简答题中经常被考察。3.2 盲目搜索BFS与DFS的代码骨架def bfs_shortest_path(graph, start, goal): from collections import deque open_queue deque([start]) closed set() parent {start: None} while open_queue: node open_queue.popleft() if node goal: return reconstruct_path(parent, node) if node in closed: continue closed.add(node) for nxt in graph.neighbors(node): if nxt not in parent: parent[nxt] node open_queue.append(nxt) return None这里closed集合记录已扩展节点防止循环。parent字典用于回溯路径。DFS只需把popleft改成pop也就是从同一端弹出实现栈行为。如果状态空间很大DFS的栈深度可能超过Python默认递归限制所以一般用显式栈循环而不是递归。维度BFSDFSOpen表队列堆栈空间复杂度高低是否保证最短单位代价下是否适用场景迷宫最短路径解存在且深度浅3.3 启发式搜索的评估函数设计启发式搜索的核心是选择下一个扩展节点时引入评估函数f(n) g(n) h(n)。g(n)是从起点到当前节点的实际代价h(n)是估计剩余代价。A*算法要求h(n)可采纳即估计值不超过真实剩余代价否则可能得不到最优解。def astar_search(graph, start, goal, heuristic): import heapq open_heap [(0, start)] # (f, node) g_score {start: 0} parent {start: None} while open_heap: _, node heapq.heappop(open_heap) if node goal: return reconstruct_path(parent, node) for nxt, cost in graph.neighbors_with_cost(node): tentative_g g_score[node] cost if tentative_g g_score.get(nxt, float(inf)): g_score[nxt] tentative_g parent[nxt] node f tentative_g heuristic(nxt, goal) heapq.heappush(open_heap, (f, nxt)) return None这里堆结构就是优先队列相当于Open表变成了按f值排序的优先级队列。启发式函数heuristic的设计直接影响搜索效率曼哈顿距离和欧式距离是最常用的两种。如果h恒为0A*退化为Dijkstra如果g恒为0则变成贪心最佳优先搜索速度快但不保证最优。实际考试里给出状态转移图让你计算BFS扩展序列的题型只需要维护一个队列记录每个节点的父指针。关键是区分“已放入Open表”和“已被扩展”只有被扩展的节点才进closed表。很多学生把进入Open表的节点直接视为已扩展导致重复扩展和路径回溯错误。4. 不确定性推理与解树代价可信度方法及其在状态评估中的角色4.1 可信度模型的组合计算可信度方法最早用于医疗专家系统核心是给每条规则一个可信度因子CF(H,E)取值范围 [-1,1]。正数表示支持负数表示反对。组合多个证据时有两条基本公式证据合取的CF取最小值证据析取的CF取最大值。多条规则指向同一结论时还要合成规则结果。def combine_cf(cf_e1, cf_e2): if cf_e1 0 and cf_e2 0: return cf_e1 cf_e2 - cf_e1 * cf_e2 if cf_e1 0 and cf_e2 0: return -(abs(cf_e1) abs(cf_e2) - abs(cf_e1) * abs(cf_e2)) return (cf_e1 cf_e2) / (1 - min(abs(cf_e1), abs(cf_e2)))这个函数实现了两条规则同向支持和反向支持时的合成逻辑。分母1 - min(abs(cf_e1), abs(cf_e2))在分母为零时说明两方完全冲突这时无法合成。考试计算题给两个证据的可信度要求合成时先判断是否同号再套公式。一个完整的计算例子规则IF A THEN B的CF为0.8证据A本身的可信度CF(A)0.6则结论B获得的可信度为0.6 * 0.8 0.48。如果另一条规则IF C THEN B的CF为0.5且CF(C)0.7那么B从第二条规则获得0.35。最后把0.48和0.35用上面的同号公式合成得到0.48 0.35 - 0.48*0.35 0.662。这个顺序在综合诊断类题目里很常见。4.2 解树的代价与搜索策略的联系解树的代价在博弈和与或树搜索中出现是评估一个候选解是否值得继续扩展的指标。常见的代价计算有两种或节点取子节点最小代价与节点取子节点最大代价。这个规则和极大极小分析是同一个思想。节点类型代价计算语义或节点min(子节点代价)存在一个解即可与节点max(子节点代价)所有子问题都解决才结束如果要把这段逻辑写成代码递归结构非常直接def solution_tree_cost(node): if node.is_leaf(): return node.cost if node.type or: return min(solution_tree_cost(c) for c in node.children) else: return max(solution_tree_cost(c) for c in node.children)这里node.type字段区分与节点和或节点。考试题中常见的陷阱是混淆或节点与与节点的计算方向比如把与节点当成所有子节点代价相加。记住解树代价不是一个“总代价”概念而是瓶颈代价尤其是与节点最大子节点代价决定了整个解树的代价。5. 博弈树极大极小分析的工程技巧5.1 极大极小递归的剪枝条件极大极小分析假设对手总是选择让自己收益最小的落点因此在博弈树中交替使用 max 和 min 操作。基础实现会展开整棵博弈树节点数随深度指数增长不实用。alpha-beta剪枝能在保持结果不变的前提下剪掉不可能影响最终选择的子树。def minimax_alpha_beta(node, depth, alpha, beta, maximizing): if depth 0 or node.is_terminal(): return node.evaluate() if maximizing: value float(-inf) for child in node.children(): value max(value, minimax_alpha_beta(child, depth-1, alpha, beta, False)) alpha max(alpha, value) if alpha beta: break return value else: value float(inf) for child in node.children(): value min(value, minimax_alpha_beta(child, depth-1, alpha, beta, True)) beta min(beta, value) if alpha beta: break return valuealpha是 max 方当前能保证的最低收益下界beta是 min 方当前能接受的最高收益上界。一旦alpha beta说明当前节点不可能被上层采用继续扩展只会浪费计算。5.2 子节点排序对剪枝效率的影响剪枝效率非常依赖子节点的访问顺序。理想的顺序是先评估最有可能改变上下界的节点这样能尽快触发剪枝。比如在国际象棋或五子棋中先搜索中心区域、吃子动作或历史命中率高的落点再搜索边缘点。这个优化比单纯把搜索深度加一层更划算。实际工程里通常还会在depth 2时先做一轮快速静态评估来排序接近应用层的做法是维护一张历史置换表。如果一个实现剪枝率上不去检查方向多半是alpha和beta更新位置是否正确。max 节点在更新子节点返回后必须立刻更新alphamin 节点必须立刻更新beta并且把比较放在循环内。把alpha beta放在循环外等于没剪枝。本文还有配套的精品资源点击获取