想象你是一位在浓雾中登山的旅人。你看不见整座山脉的轮廓，只能看清脚下周围几十米的范围。你的登山策略朴素而直接：先环顾四周，看看哪个方向地势在上升、坡度最陡，然后朝那里迈一步；站定之后，再环顾，再迈步……直到有一天，你发现无论朝哪个方向走，脚下都会变低，于是你舒口气说：“我登顶了。”可若此刻雾散，你才发现自己站在的只是一座小山丘，不远处才是真正的高峰。 这正是因果发现中大名鼎鼎的爬山搜索（Hill Climbing）——一种朴素却实用的寻路算法。它不用一口气看遍所有可能的因果图，而是从一张初始草图出发，反复尝试“加一条连线、撤一条连线、把连线方向反过来”这三种微调动作，哪一步能让数据解释得更好就走哪一步。它像那位雾中登山者一样，简单、直观、永不停歇，却也容易止步于“看得见的最高点”，陷入局部最优。 本篇文章，我们就跟着这位雾中登山者，把爬山搜索的评分、邻域、流程、困境与价值一次看透。

岗位关联

爬山搜索是分数式结构学习的入门基石——掌握它，你就能快速构建因果图基线，为更复杂的结构搜索与可信 AI 决策铺路。

目录
  1. 可视化演示
  2. 爬山思想
  3. 三项操作
  4. 评分函数
  5. 搜索历程
  6. 局部最优困局
  7. 算法评价
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示邻域操作演示、爬山搜索迭代过程及局部最优逃逸策略的三模态交互动画。

本节配有交互动效（进入视口后自动加载，约 3KB）。

邻域操作演示 加边 删边 Add|Del|Rev 爬山搜索评估三种邻域操作加边删边反转边选择评分提升最大的方向

爬山思想

雾中登山者的第一条信条是：“我只相信亲眼确认的上坡。”他不会因为听人说东边有座更高的山就贸然改道，他只在自己能看清的范围内寻找最陡的上坡方向。这种“眼见为实、步步为营”的哲学，正是爬山搜索的灵魂。

在因果发现里，登山者脚下的“地形”是所有可能的因果关系图构成的空间，而“海拔仪”则是评分函数——它给每张候选图打一个分，衡量这张图解释数据的水平。爬山搜索要做的，就是从一张初始图出发，沿着评分不断升高的方向迭代移动，逐步逼近理想的因果结构。

形式化地说，爬山搜索是在所有无环有向图中寻找评分最高的一张，作为对真实因果结构的估计。由于候选图的数量随变量数呈超指数增长，逐一枚举绝无可能，爬山搜索便用贪心策略逐步逼近：每次只考虑“走一步”能到达的图，选最好的方向迈出去。

登山者每一步只需要回答一个问题：“我现在站的地方，往哪边走最陡？”爬山搜索也一样——它不追求一步登天，只追求每一步都比刚才高一点。这种贪心到近乎天真的信条，正是它简单、快速、好用的根本原因。

G^=arg⁡max⁡G∈DAGScore(G,D)\widehat{\mathcal{G}} = \arg\max_{\mathcal{G} \in \mathcal{DAG}} \text{Score}(\mathcal{G}, \mathcal{D})
这个式子的意思是：在“无环有向图”这个大山里，找到让评分函数最高的那张图。
  1. 候选空间DAG 表示所有无环有向图组成的集合，登山者只能在“无环”的地形上行走，形成环的候选一律淘汰。
    G∈DAG\displaystyle \mathcal{G} \in \mathcal{DAG}
  2. 评分函数Score(G, D) 像登山者的海拔仪，给每张候选图打一个“地形高度分”，衡量它解释数据的水平。
    Score(G,D)\displaystyle \text{Score}(\mathcal{G}, \mathcal{D})
  3. 最优目标argmax 表示“哪个候选图得分最高就选哪个”，这是所有分数式方法的统一目标。
    arg⁡max⁡G\displaystyle \arg\max_{\mathcal{G}}
  4. 估计结果带帽子的 Ĝ 表示搜索结束后估算出的最优因果结构，是后续因果推断的依据。
    G^\displaystyle \widehat{\mathcal{G}}

三项操作

登山者脚边有三件法宝：垫脚石、撤石子、调方向。想往上够，就垫一块石头（加边）；发现踩着的石头松了、多余了，就撤掉（删边）；发现石头朝向不对，就把它反过来（反转边）。他所有的探索，都在这三件法宝之间做选择。

换成因果图的语言：加边是在两个变量之间新增一条有向边，表示“我怀疑 A 影响 B”；删边是移除一条现有边，表示“这条关系可能是误加的”；反转边则是把 A→B 改成 B→A，表示“方向也许弄反了”。这三种操作，构成了爬山搜索的全部脚步。

在任意一张图 G 上，所有能通过一次加边、删边或反转边得到的合法无环图，合起来称为 G 的邻域，记作 N(G)。每一轮搜索只在邻域内打量候选，绝不跳远。当变量数为 n 时，任意两个变量之间都可能发生操作，所以邻域规模约为 n 的平方量级。

登山者每一步都在三件法宝间做单选，绝不跨大步。这种谨慎让每一步都有据可查、可回溯，也让“邻域”这个概念成为整座爬山算法大厦的地基。

N(G)=Add(G)∪Delete(G)∪Reverse(G)\mathcal{N}(\mathcal{G}) = \text{Add}(\mathcal{G}) \cup \text{Delete}(\mathcal{G}) \cup \text{Reverse}(\mathcal{G})
邻域就是“走一步能到达的所有合法图”的集合，相当于登山者视野内所有可落脚的位置。
  1. 加边操作在当前图中添加一条尚未存在的有向边 i→j，表达“我怀疑 i 是 j 的原因”，前提是加完仍无环。
    Add(G)={G+(i→j)∣i→j∉G,  无环}\displaystyle \text{Add}(\mathcal{G}) = \{ \mathcal{G} + (i \to j) \mid i \to j \notin \mathcal{G}, \; \text{无环} \}
  2. 删边操作移除一条现有边 i→j，砍掉可能多余或虚假的因果连接，删边永远不会制造环。
    Delete(G)={G−(i→j)∣i→j∈G}\displaystyle \text{Delete}(\mathcal{G}) = \{ \mathcal{G} - (i \to j) \mid i \to j \in \mathcal{G} \}
  3. 反转边操作把 i→j 改为 j→i，相当于“先删后加”的组合拳，但组合后仍需做无环检查。
    Reverse(G)={G−(i→j)+(j→i)∣i→j∈G,  无环}\displaystyle \text{Reverse}(\mathcal{G}) = \{ \mathcal{G} - (i \to j) + (j \to i) \mid i \to j \in \mathcal{G}, \; \text{无环} \}

评分函数

登山者需要一台可信的海拔仪，否则分不清哪边才是上坡。这台海拔仪就是评分函数。聪明的登山者还明白：海拔不只看你爬了多高，还要看你为此背了多少装备——拟合得好，必须对得起付出的复杂度。

因果发现中最常用的海拔仪之一是 BIC（贝叶斯信息准则）评分。它由两项构成：第一项是“拟合分”，看当前图把数据解释得多好；第二项是“惩罚分”，图的参数越多、越复杂，扣分越重。两项相减，就是这张图的最终评分。

形式上，对一张图 G 和数据 D，BIC 定义为对数似然项减去复杂度惩罚项。其中 θ̂ 是参数的最大似然估计，d 是参数个数，N 是样本量。惩罚项会随样本量增大而变强——数据越多，我们越有底气要求模型简洁，防止它把噪声也当作规律。

BIC 还有一个了不起的性质——可分解。整图的评分等于各节点评分之和，而每个节点的评分只取决于它自己和它的父节点。这意味着评估“加一条边”的效果时，只需重新计算受影响的节点，而不必重算整张图。

有了这台扣过装备重量的海拔仪，登山者才敢放心迈步——他每走一步，都知道自己是“净爬升”而不是“表面爬升”。BIC 正是这样一杆秤：既要数据解释得好，又不要模型复杂到浮夸。

BIC(G∣D)=ln⁡P(D∣G,θ^)−d2ln⁡N\mathrm{BIC}(\mathcal{G} \mid \mathcal{D}) = \ln P(\mathcal{D} \mid \mathcal{G}, \hat{\theta}) - \frac{d}{2} \ln N
可分解性让地形测量变成“分段量台阶”：整座山的高度，等于每段台阶高度的简单加和。
  1. 逐节点求和整图评分是各节点评分的简单加和，像把整座山的高度拆成一段段台阶分别测量。
    ∑i=1n\displaystyle \sum_{i=1}^{n}
  2. 局部依赖每个节点的 BIC 只取决于它自己和它的父节点 Pa(X_i)，与图中其他部分无关，这是高效评估邻域操作的关键。
    BIC(Xi∣Pa(Xi))\displaystyle \mathrm{BIC}(X_i \mid \mathrm{Pa}(X_i))

搜索历程

现在，雾中登山者正式出发了。他的登山手册写着：先找一个起点；然后环顾四周，把所有迈一步就能到的位置都量一遍海拔；再选最高的方向迈过去；反复执行，直到四周都找不到更高的地方。

爬山搜索的完整流程正是如此：初始化 → 评估邻域 → 择优移动 → 检查终止。起点通常是空图，也可以随机生成一张图。每一步移动都必须保证新图仍是合法的无环图，所以“评估邻域”时要做无环检查。

把“评估邻域”和“择优移动”合起来看，就得到爬山搜索的核心迭代公式：下一步踩的图，是当前图所有邻居里评分最高的那一张。

手册最后一页写着：当四周都找不到更高的地方，就停下宣布登顶。爬山搜索也一样——当所有邻域操作的评分提升都不大于零，搜索便收敛，这段“环顾—迈步—再环顾”的旅途就此画上句号。

Gt+1=arg⁡max⁡G′∈N(Gt)BIC(G′∣D)\mathcal{G}_{t+1} = \arg\max_{\mathcal{G}' \in \mathcal{N}(\mathcal{G}_t)} \mathrm{BIC}(\mathcal{G}' \mid \mathcal{D})
这个式子描述了登山者最经典的一步：在视野内所有可落脚处中，挑海拔最高的那个迈过去。
  1. 当前位置G_t 是第 t 轮当前踩着的因果图——登山者此刻站立的坐标。
    Gt\displaystyle \mathcal{G}_t
  2. 候选邻域N(G_t) 是当前图所有“走一步就能到达”的邻居图，也就是加边、删边、反转一次后的全部合法结果。
    G′∈N(Gt)\displaystyle \mathcal{G}' \in \mathcal{N}(\mathcal{G}_t)
  3. 择优方向argmax 从全部邻居中挑出 BIC 评分最高的那个，作为下一步的落脚点——最陡的上坡。
    arg⁡max⁡G′\displaystyle \arg\max_{\mathcal{G}'}
  4. 迭代前进G_{t+1} 成为新的当前图，“评估-移动”循环往复，直到没有邻居比当前更好。
    Gt+1\displaystyle \mathcal{G}_{t+1}

局部最优困局

雾散了。登山者站在山顶得意地环视四周，却猛然发现远方还有一座更高的主峰，而自己脚下只是一座被山谷隔开的小山丘。按自己的规则，无论朝哪个方向走，海拔都会先降再升，而“先下降”是他绝不接受的选择。

这就是爬山搜索最著名的心结：局部最优。它保证了“每一步都在变好”，却无法保证“最终停在最好的地方”。真实数据的评分地形往往多峰林立，从不同的初始图出发，登山者很可能停在不同的小山丘上——结果对起点十分敏感。

破局招数应运而生：随机重启，派多支队伍从不同山脚出发，取各自登顶高度中的最高者；塔布搜索，把最近走过的路记入“禁行名单”，逼自己先下坡再上坡；模拟退火，偶尔允许往下走一步，用概率对抗地形的欺骗。它们的共同逻辑是：一次爬行不靠谱，就用多次尝试与记忆对冲运气。

登山者从此明白：登山的智慧不只是“永远向上”，还有“承认视野有限，多试几条路”。爬山搜索的朴素与局限，恰恰教会后来者：任何只看局部信息的方法，都要对“局部最优”保持敬畏。

Gfinal=arg⁡max⁡r=1R  BIC(Glocal(r)∣D)\mathcal{G}_{\mathrm{final}} = \arg\max_{r=1}^{R} \; \mathrm{BIC}\left(\mathcal{G}^{(r)}_{\mathrm{local}} \mid \mathcal{D}\right)
随机重启的思路：多派几支登山队从不同山脚出发，最后以“实测海拔最高”的那一次结果为准。
  1. 多轮爬山重复 R 轮搜索，每轮从不同的初始图出发，得到各自的局部最优解。
    Glocal(r)\displaystyle \mathcal{G}^{(r)}_{\mathrm{local}}
  2. 全局比较在 R 个局部最优中比较评分，r 从 1 取到 R，选出最高的那一个——像几支登山队各自登顶后，以实测海拔最高者为准。
    arg⁡max⁡r=1R  BIC(Glocal(r)∣D)\displaystyle \arg\max_{r=1}^{R} \; \mathrm{BIC}\left(\mathcal{G}^{(r)}_{\mathrm{local}} \mid \mathcal{D}\right)
  3. 概率提升随机重启不保证找到全局最优，但能让“找到一个好解”的概率明显上升，代价只是多花几倍运行时间。
    Gfinal\displaystyle \mathcal{G}_{\mathrm{final}}

算法评价

回到营地，登山者把方法写进手册，评价道：“它不保证登上最高峰，但总能让你快速到达一座山顶。”这正是爬山搜索在因果发现中的定位——一个简单、直观、快速、可解释的基线方法。

优点十分鲜明：实现门槛极低，几十行代码即可跑通；配合 BIC 的可分解性，单边操作的评分可以局部更新，迭代效率高；对十几个变量以内的中小规模问题非常友好，常作为复杂新方法的对照基线。

短板同样清晰：贪心本质使其极易陷入局部最优，可靠性随变量维度升高而快速下降；结果对初始图敏感，不同起点可能得到不同结论；缺乏全局最优保证，在高维真实场景中只能作为“初步草图”而非最终答案。

如果说因果发现是一望无际的群山，爬山搜索就是那根最趁手的登山杖：它不能带你飞到最高的主峰，却能在迷雾中稳稳地把你托上第一座山顶，让你看清地形，再决定要不要换更先进的装备。理解它，就是理解一切分数式结构学习的起点。

每轮迭代：O(n2)  次候选评估总复杂度：O(I⋅n2)\text{每轮迭代：} O(n^2) \; \text{次候选评估} \qquad \text{总复杂度：} O(I \cdot n^2)
节点数为 n 时，每轮要评估 n 平方量级的候选操作；乘上收敛轮数 I，就是整体的计算开销。
  1. 每轮候选数节点数为 n 时，任意两个节点之间都可能发生加、删、反转操作，候选规模是 n 的平方量级。
    O(n2)\displaystyle O(n^2)
  2. 收敛轮数记收敛需要的迭代轮数为 I，它与数据规模和地形复杂度有关，通常远小于候选总数。
    I\displaystyle I
  3. 总计算量把“每轮候选数”乘以“轮数”，就是爬山搜索的整体开销，中小规模问题可以轻松跑完。
    O(I⋅n2)\displaystyle O(I \cdot n^2)

AI 应用场景

基因调控网络骨架初筛

阶段：因果结构学习 / 模型选择

解决的问题：传统湿实验逐个验证基因间的调控关系，成本高、周期长、通量低。爬山搜索可从基因表达数据出发，用 BIC 评分快速生成候选调控网络骨架，把“大海捞针”变成“定向验证”。

具体案例：某计算生物团队对 20 个候选基因的表达谱运行 BIC-爬山搜索，几十秒内得到初始网络草图，筛出 12 条高置信边进入后续基因敲除验证，实验效率提升近一倍。

营销渠道归因初探

阶段：特征因果筛选 / 根因分析

解决的问题：营销数据中渠道间互相影响，常规相关性分析分不清谁是真正的驱动因素。爬山搜索可快速圈出影响转化的核心渠道，为后续 A/B 实验指明方向。

具体案例：某增长团队对 12 个投放渠道与转化指标建模，用爬山搜索发现仅 3 个渠道进入因果骨架，据此重排预算，转化率提升 18%。

系统故障根因草图

阶段：可解释 AI 辅助诊断

解决的问题：故障告警指标有数十个，人工排查根因耗时费力。爬山搜索从监控指标序列中勾勒因果草图，定位疑似根因指标，再由运维专家做定向干预验证。

具体案例：某 SRE 团队对 15 个核心监控指标运行爬山搜索，在服务抖动时 5 分钟内锁定 2 个疑似根因指标，相比人工排查缩短 70% 时间。

Python 演示

python110 行
import numpy as npfrom itertools import combinations  def reg_ll(data, child, parents):    y = data[:, child]    if not parents:        return -0.5 * len(y) * np.log(np.var(y) + 1e-9)    beta = np.linalg.lstsq(data[:, list(parents)], y, rcond=None)[0]    return -0.5 * len(y) * np.log(np.var(y - data[:, list(parents)] @ beta) + 1e-9)  def node_bic(data, child, parents):    return reg_ll(data, child, parents) - 0.5 * len(parents) * np.log(len(data))  def graph_score(data, g):    n = g.shape[0]    return sum(node_bic(data, i, [j for j in range(n) if g[j, i]]) for i in range(n))  def has_cycle(g):    n = len(g)    state = [0] * n     def dfs(v):        state[v] = 1        for u in range(n):            if g[v, u] and (state[u] == 1 or (state[u] == 0 and dfs(u))):                return True        state[v] = 2        return False     return any(state[v] == 0 and dfs(v) for v in range(n))  def reversed_graph(g, a, b):    h = g.copy()    h[a, b], h[b, a] = 0, 1    return h  class HillClimbingSearch:    def __init__(self, data):        self.data = np.asarray(data, dtype=float)        self.n = self.data.shape[1]        self.graph = np.zeros((self.n, self.n), dtype=int)     def move_candidates(self):        g = self.graph        for a, b in combinations(range(self.n), 2):            if g[a, b] == 0:                yield a, b, 'add'            else:                yield a, b, 'delete'                h = reversed_graph(g, a, b)                if not has_cycle(h):                    yield a, b, 'reverse'            if g[b, a] == 0:                yield b, a, 'add'            else:                yield b, a, 'delete'                h = reversed_graph(g, b, a)                if not has_cycle(h):                    yield b, a, 'reverse'     def apply(self, a, b, kind):        if kind == 'add':            self.graph[a, b] = 1        elif kind == 'delete':            self.graph[a, b] = 0        else:            self.graph[a, b], self.graph[b, a] = 0, 1     def search(self, max_iter=100):        while max_iter > 0:            max_iter -= 1            base = graph_score(self.data, self.graph)            best_move, best_gain = None, 0.0            for a, b, kind in self.move_candidates():                h = self.graph.copy()                if kind == 'add':                    h[a, b] = 1                elif kind == 'delete':                    h[a, b] = 0                else:                    h[a, b], h[b, a] = 0, 1                if has_cycle(h):                    continue                gain = graph_score(self.data, h) - base                if gain > best_gain:                    best_gain, best_move = gain, (a, b, kind)            if best_move is None:                break            self.apply(*best_move)            print('move:', best_move, 'gain: %.3f' % best_gain)        return self.graph  if __name__ == '__main__':    rng = np.random.RandomState(42)    N = 500    x0 = rng.normal(size=N)    x1 = 0.8 * x0 + rng.normal(size=N)    x2 = 0.6 * x1 + rng.normal(size=N)    data = np.column_stack([x0, x1, x2])     dag = HillClimbingSearch(data).search()    print('recovered DAG (row -> col):')    print(dag)
目的：从线性高斯数据中，用 BIC 评分与加边、删边、反转边三种操作，实现完整的爬山搜索因果发现。
  1. return reg_ll(data, child, parents) - 0.5 * len(parents) * np.log(len(data))BIC 的“净海拔”：拟合分减去复杂度惩罚。
  2. sum(node_bic(data, i, [j for j in range(n) if g[j, i]]) for i in range(n))可分解性：整图分数等于各节点分数之和。
  3. state[v] = 1` 与 `if state[u] == 1DFS 三色法检测有向环，保证候选图始终合法。
  4. if g[a, b] == 0: yield a, b, 'add'无边的位置尝试加边，有边的位置尝试删边与反转。
  5. if not has_cycle(h): yield a, b, 'reverse'反转边必须先做无环检查，否则丢弃该候选。
  6. gain = graph_score(self.data, h) - base计算每个候选相对当前评分的提升量。
  7. if best_move is None: break无任何提升即收敛，登山者宣布登顶。
  8. data = np.column_stack([x0, x1, x2])构造已知链条 x0→x1→x2 的合成数据作为实验场。

常见误区

误区初学者常以为“既然每一步都选最好的，最后停下的地方当然就是全局最好的，爬山搜索一定能还原真实因果图。”

正解每一步选最好只保证“局部爬升”，最终停下的恰恰可能是局部最优。评分地形多峰林立，从不同起点出发会得到不同结果。它像雾中登山，可能停在低处的小山丘上，而主峰还藏在雾里。随机重启、塔布搜索等策略只是缓解，并不能根除这个问题。

为何常见：把“迭代中每一步最优”等同于“全局最优”，忽略了贪心策略只看局部邻域的本质。

误区“BIC 分数高就等于模型解释数据能力强，那把所有边都加上，拟合肯定最好，不就行了吗？”

正解BIC = 拟合项 − 复杂度惩罚项。加边虽提升拟合，也增加参数、被惩罚扣分；完全图必然过拟合，把噪声也当成了规律。它像登山时既要爬得高，又要背着装备——净爬升才是真正的高度。

为何常见：只看到公式前半项的拟合，忽略了复杂度惩罚在模型选择中的均衡作用。

误区“反转一条边，本质上就是删掉再加一条反方向的边，跟单独删边没区别，不需要特殊对待。”

正解反转往往改变路径结构，可能制造环。例如 A→B→C 中把 A→C 反转为 C→A，就形成 A→B→C→A 的环。三种操作共享同一条铁律：结果必须仍是合法 DAG，每次反转后都必须做无环检查。

为何常见：把三种操作割裂看待，没意识到它们都受“无环”这一全局约束的制约。

误区“爬山搜索每轮要试几十上百个候选，每个候选都要从头算整张图的分数，肯定慢得没法用。”

正解BIC 可分解，加边、删边只影响被操作节点的评分及其局部分支，其余节点完全不变，评分可以增量更新。正是这种“只量一段台阶”的能力，让爬山搜索在中小规模问题上跑得飞快。

为何常见：不了解评分可分解性，把“整图一个分数”误解为“每次都要整图重算”。

面试题

Q1. 爬山搜索的核心思想是什么？

单选题 · easy

  • A.随机生成大量候选图投票
  • B.沿评分提升方向迭代爬升← 正确答案
  • C.枚举所有图结构取最优
  • D.用独立性检验筛选边

答案：B。爬山搜索每一步都从当前图的邻域里挑评分提升最大的方向移动（B 对）。A 是投票式随机搜索的思路，C 是全局枚举、成本不可行，D 是基于约束方法的做法。它就像雾天登山：只看四周，选最陡的上坡。

Q2. 下列哪项不是爬山搜索的邻域操作？

单选题 · easy

  • A.添加一条新有向边
  • B.删除一条已有边
  • C.反转一条边的方向
  • D.整张图重新初始化← 正确答案

答案：D。加边、删边、反转边是爬山搜索的三件套，构成完整的邻域操作；“整张图重新初始化”是一次重启，不是单步操作。登山者每一步只允许动一条边，不会突然传送回山脚。

Q3. BIC 评分函数由哪两部分构成？

单选题 · mid

  • A.对数似然项与复杂度惩罚← 正确答案
  • B.先验概率与后验概率
  • C.均值估计与方差估计
  • D.精确率与召回率

答案：A。BIC 由拟合项（对数似然）与复杂度惩罚项构成，追求“拟合与简洁的平衡”。B 属于贝叶斯估计框架，C 是参数估计内容，D 是分类评估指标，都不是 BIC 的定义成分。它像登山时的净海拔：爬升高度减去装备重量。

Q4. 关于 BIC 的惩罚项，下列说法正确的是？

单选题 · mid

  • A.与样本量大小完全无关
  • B.随样本量增大而变强← 正确答案
  • C.只与变量个数有关
  • D.总是一个固定常数

答案：B。BIC 惩罚项为 (d/2)·lnN，N 是样本量，lnN 随 N 单调上升，所以样本越大惩罚越强（B 对），更倾向于选简单图。A、C、D 都与数学形式不符。这就像补给越足，登山队越该轻装简行。

Q5. 爬山搜索最主要的缺点是什么？

单选题 · mid

  • A.实现起来过于复杂
  • B.容易陷入局部最优← 正确答案
  • C.无法处理小规模数据
  • D.必须手动指定初始图

答案：B。爬山搜索实现简单、擅长小规模数据，最出名的问题是贪心导致的局部最优（B 对）。它像雾中登山，可能停在低处的小山丘，而真正的主峰还在远处。初始图虽影响结果，但通常可从空图出发，并非必须手动指定。

Q6. 下列哪些方法可以缓解爬山搜索的局部最优问题？

多选题 · mid

  • A.多次随机重启取最优← 正确答案
  • B.塔布搜索记录历史← 正确答案
  • C.模拟退火允许下坡← 正确答案
  • D.取消评分函数使用

答案：ABC。随机重启（A）、塔布搜索（B）、模拟退火（C）都是经典破局策略：多试几次、记住禁行路线、偶尔允许下坡。取消评分函数等于扔掉海拔仪，方法无从谈起（D 错）。它们的共同逻辑是：一次爬行不靠谱，就用多次尝试对冲运气。

Q7. 爬山搜索的停止条件是什么？

单选题 · easy

  • A.迭代达到整数上限即可
  • B.所有变量都被访问到
  • C.邻域内找不到更高分← 正确答案
  • D.搜索时间超过一小时

答案：C。爬山搜索的天然终止条件是“邻域内没有任何操作能提升评分”（C 对）。若还能提升却停下，说明收敛判断有误。登山者四周望去全是下坡，才宣布登顶；A、B、D 都不是算法本身定义的自然停止条件。

Q8. 关于爬山搜索，下列说法正确的有？

多选题 · hard

  • A.结果对初始图非常敏感← 正确答案
  • B.评分可分解是高效前提← 正确答案
  • C.每步都必须保持无环← 正确答案
  • D.一定能找到全局最优

答案：ABC。初始图决定从哪个山脚出发，起点不同结果可能不同（A 对）；BIC 可分解使单边操作只需局部更新评分（B 对）；每次操作后都必须保证 DAG 无环（C 对）；爬山是贪心算法，不保证全局最优（D 错）。这正是它被称为“基线”而非“终版”的原因。

Q9. 当样本量 N 非常大时，BIC 惩罚项会产生什么影响？

单选题 · hard

  • A.惩罚减弱倾向复杂图
  • B.惩罚增强倾向简单图← 正确答案
  • C.惩罚完全不起任何作用
  • D.只影响拟合项数值

答案：B。惩罚项为 (d/2)·lnN，随 N 增大对复杂图的扣分更重，因此数据越多越倾向选简单图（B 对）。这与直觉相反却很重要：大样本下 BIC 更严苛地拒绝冗余参数。好比补给越充分，登山队越应该轻装，而不是背更多装备。

Q10. 为什么爬山搜索常被当作因果发现的基线方法？

单选题 · mid

  • A.因为它总是能找出最优图
  • B.因为实现简单且可快速试错← 正确答案
  • C.因为它完全不依赖数据
  • D.因为它只适用于大样本

答案：B。爬山搜索的价值在于实现简单、直观、可快速试错，适合作为对照基线（B 对）。A 夸大了它的能力，C 与事实相反——它依赖评分函数与数据，D 也不成立，它更适合中小规模数据。它是登山队的入门杖，而非登顶神器。