想象你是一位名叫阿峰的登山爱好者，来到一片连绵起伏的山脉，目标是找到群山之中的最高峰。你带了一台精准的海拔仪，但制定了一条简单的规则：只看脚下，哪边地势高就往哪边走。很快，你爬上了一座小土丘——环顾四周，附近的土地确实都比这里低，你心满意足地宣布“这就是最高峰”。然而，远处云雾缭绕的地方，藏着一座巍峨得多的山峰，只是你永远看不到了。 这就是“局部最优”的生动写照。在基于分数的因果发现中，算法像阿峰一样在 DAG（有向无环图）空间中“爬山”：每一步只做一个微小的改动（加一条边、删一条边、转一条边），只要评分变好就接受。这种贪心策略简单高效，却经常把小山丘误认为最高峰——搜索陷入局部最优，错过评分更高的因果结构。幸运的是，我们有三类经典的“破局”策略：随机重启（换一座山重新爬）、邻域扰动（大胆跳离当前山丘）、多起点搜索（多派几支登山队分头行动）。今天这篇文章，就沿着阿峰的脚步，把局部最优的成因与逃逸策略讲个明白。

岗位关联

对 AI 从业者而言，理解局部最优陷阱是设计稳健结构学习算法的前提——它能帮你避免次优拓扑的固化，在构建可信 AI 基础设施时交付更可靠的因果模型。

目录
  1. 可视化演示
  2. 贪心搜索原理
  3. 局部最优成因
  4. 登山搜索过程
  5. 随机重启策略
  6. 邻域扰动机制
  7. 多起点搜索
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示分数景观中贪心搜索陷入局部最优、随机重启多起点覆盖与邻域扰动逃逸机制，帮助理解因果发现结构学习优化策略。

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

'+captions.landscape+'

贪心搜索原理

阿峰的登山法则是“只往高处走”。他每走一步，就抬起脚试探四周：左边高一点，就往左；右边高一点，就往右。这个方法效率极高，因为他从不浪费时间去走“下坡路”。但它的代价也很明显——他只看得到脚边几米的地形，看不到山的那边还有更高的峰。在基于分数的因果发现中，贪心搜索就是这样一个“只往高处走”的登山者。

把这种思路搬到 DAG 结构学习里：算法从某个初始结构出发，每一步枚举当前结构的所有“邻居”——也就是只改动一条边就能得到的其他合法 DAG。它用一个评分函数（如 BIC、BDeu）给每个候选结构打分，然后毫不犹豫地走向评分最高的那个邻居。评分函数的角色正如阿峰手中的海拔仪，它不关心结构是否“看起来合理”，只关心数学上对数据的解释能力是否更强。

这种“每步取最优”的搜索策略，数学上可以写成如下形式：

阿峰靠着“只看脚边”的规则很快登上了眼前的小丘，但也正是这条规则锁死了他的视野。贪心搜索的高效与短视，就像这枚硬币的两面——他从不走弯路，也因此永远看不到弯路之后可能藏着的大山。

xt+1=arg⁡max⁡x′∈N(xt)S(x′)\displaystyle x_{t+1} = \arg\max_{x' \in \mathcal{N}(x_t)} S(x')
公式含义：下一步的结构 \(x_{t+1}\)，就是在当前结构的邻域 \(\mathcal{N}(x_t)\) 中，让评分函数 \(S\) 取值最大的那个候选。
  1. 当前位置 \(x_t\)表示第 \(t\) 步搜索到的 DAG 结构，好比阿峰此时此刻站立的地点。
    xtx_t
  2. 邻域 \(\mathcal{N}(x_t)\)从当前结构出发，通过一次加边、删边或转边能到达的所有合法 DAG 结构。
    N(xt)\mathcal{N}(x_t)
  3. 候选评分 \(S(x')\)对每一个邻居结构用评分函数打分，分数越高表示越符合数据。
    S(x′)S(x')
  4. 取最大 \(\arg\max\)在所有邻居中挑选评分最高的一个，作为下一步移动的目标。
    xt+1=arg⁡max⁡x′∈N(xt)S(x′)x_{t+1} = \arg\max_{x' \in \mathcal{N}(x_t)} S(x')

局部最优成因

阿峰站在小丘上，疑惑地转了一圈：东边比这里低，西边也比这里低，南边北边都低！他郑重地宣布“我到了最高峰”——但这恰恰是问题的核心：他只在“附近”做了比较。在 DAG 结构搜索里，这个“附近”被严格定义为“单步操作可达的邻居集合”。一个结构如果评分比所有邻居都高，但比某个远处的结构低，它就是局部最优。

为什么评分景观里会有这么多“小丘”？首先，评分函数在结构空间中的取值非常崎岖——加一条边可能让分数暴涨，再加第二条又暴跌，形成无数坑坑洼洼的局部隆起。其次，DAG 空间是天文数字级的：\(n\) 个节点的 DAG 数量随 \(n\) 指数爆炸，哪怕只有 10 个节点，可能的结构也是亿级以上。阿峰在如此广阔的山脉里，凭一条“只往上走”的规则，几乎没有可能恰好走到真正的最高峰。

更隐蔽的原因是路径依赖。阿峰一开始选择往东南走，后来发现西边有更高的山，但他已经下了太多坡，按规则“不能走下坡路”，就永远回不去了。贪心搜索同样如此——早期的一个错误边决策，会让后续所有操作都围绕错误结构修修补补，最终停在一个次优的拓扑上。数学上，局部最优的严格定义是：

阿峰终于明白：山丘的“高”是相对于脚边而言的，山外有山。局部最优之所以让人防不胜防，正是因为它用“邻域内的绝对优势”掩盖了“全局范围内的相对劣势”。

S(x∗)≥S(x), ∀x∈N(x∗),且S(x∗)<S(xglobal)\displaystyle S(x^*) \geq S(x), \ \forall x \in \mathcal{N}(x^*), \quad \text{且} \quad S(x^*) < S(x_{global})
公式含义：局部最优 \(x^*\) 在自己的邻域内评分无出其右，却在全局范围内输给了最优结构 \(x_{global}\)。
  1. 局部最优 \(x^*\)一个在邻居眼中“最强”的 DAG 结构，好比阿峰脚下的小山丘。
    x∗x^*
  2. 邻域无敌对邻域中的每一个结构 \(x\)，它的评分都不高于 \(x^*\)。
    S(x∗)≥S(x), ∀x∈N(x∗)S(x^*) \geq S(x), \ \forall x \in \mathcal{N}(x^*)
  3. 全局不如但与真正的全局最优相比，仍然差了一截。
    S(x∗)<S(xglobal)S(x^*) < S(x_{global})

登山搜索过程

如果把贪心搜索放大来看，它其实是一套非常机械的操作流程。阿峰的登山之道可以被拆解为“初始化—试探—判断—停滞”四个环节：他先随便找个起点站好，然后反复试探“往哪走会变高”，一旦找不到更高的方向，就原地扎营，宣告结束。DAG 搜索的登山算法（Hill Climbing）也是这个套路。

第一步是初始化——从空图、随机图或基于先验知识的图出发。第二步是生成邻域——枚举所有“单边操作”，包括加边（添加一条原本不存在的有向边）、删边（去掉一条已有边）、转边（把一条边的方向反转）。每一次操作必须保证不产生有向环，这是 DAG 结构合法性的底线，就像阿峰不能踩着沼泽上山一样。第三步是评分判断——对每个候选结构算一遍评分，看分数有没有提升。最后，当所有邻居的评分都不再高于当前结构时，搜索陷入停滞：

阿峰把每一步拆成“试探—比较—迈步”，每一步都走得有理有据。然而登山者走得越“理性”，就越容易在一座小丘上彻底驻足——因为在他严苛的规则里，任何下坡都是不被允许的。

ΔS=S(G′)−S(G)>0\displaystyle \Delta S = S(G') - S(G) > 0
公式含义：只有当新结构 \(G'\) 的评分减去当前结构 \(G\) 的评分为正时，登山者才迈出这一步。
  1. 当前结构 \(G\)搜索进行到现在所在的 DAG，相当于阿峰脚下的位置。
    GG
  2. 候选结构 \(G'\)对当前结构做一次加边、删边或转边操作后得到的新 DAG。
    G′G'
  3. 评分差 \(\Delta S\)用评分函数分别打分再相减，度量“这一步值不值得走”。
    ΔS=S(G′)−S(G)\Delta S = S(G') - S(G)
  4. 严格提升才迈步只有评分为正才接受移动，否则留在原地。
    ΔS>0\Delta S > 0

随机重启策略

站在小丘上，阿峰终于意识到问题：不是自己没有能力，而是起步的位置决定了很多。如果一开始就往西边那座更高的山走，结果会完全不同。于是他做出一个大胆的决定——下山，换一座山重新爬。一次不行，就再来一次。他把这个策略称为“多试几座山”。

随机重启策略（Random Restart Hill Climbing）的核心思想正是如此：不再执着于从同一个起点一路爬到头，而是反复地从随机生成的初始结构出发，每次独立执行完整的贪心爬山，最后保留所有登山结果中评分最高的那个。这里的“随机初始点”可以理解为阿峰每次被直升机空投到山脉的不同区域，每个区域的地形都不同，撞见真正最高峰的概率自然大大增加。

假设单次搜索找到全局最优的概率是 \(p\)，那么独立重复 \(k\) 次后，至少成功一次的概率呈指数增长：

阿峰试了 3 座山、5 座山、10 座山，果然在第 7 次时看到了那座巍峨的真正的最高峰。但他的新烦恼也随之而来：每次重启都要从头爬一遍，时间成本越来越高。随机重启不是免费的午餐，而是用“时间”换“概率”的一场赌局。

Psuccess(k)=1−(1−p)k\displaystyle P_{success}(k) = 1 - (1-p)^k
公式含义：失败一次的概率是 \(1-p\)，\(k\) 次全部失败的概率是其 \(k\) 次方，用 1 减去它，就是至少成功一次的概率。
  1. 单次成功概率 \(p\)从某一次随机初始点出发爬山最终找到全局最优的概率，通常很小但大于 0。
    pp
  2. 单次失败概率 \(1-p\)这一次尝试没能找到全局最优的概率。
    1−p1-p
  3. \(k\) 次全部失败因为每次搜索相互独立，所有尝试都失败的概率是相乘关系。
    (1−p)k(1-p)^k
  4. 至少成功一次用“必然事件概率 1”减去“全部失败”，即得到至少一次成功的概率。
    Psuccess(k)=1−(1−p)kP_{success}(k) = 1 - (1-p)^k

邻域扰动机制

“重启”听起来很美好，但每次都要从零开始，效率太低了。阿峰心想：我现在已经在一座山上了，为什么不直接往山下跳几大步，落到另一座山的半山腰再往上爬呢？这个想法，对应着结构学习中的另一类强大策略——邻域扰动，其中最著名的代表就是模拟退火算法。

模拟退火的关键在于：允许算法在温度较高时“接受差解”。想象阿峰在高温下像个弹力球，就算前方的路是下坡，他也可能因为“热运动”而滚过去；随着温度逐渐降低，他越来越安静，最终只会老老实实地向高处走。翻译成算法语言就是：当候选结构 \(G'\) 的评分比当前结构 \(G\) 差时，不再像贪心搜索那样直接拒绝，而是以一定概率接受这次“下坡移动”。这个接受概率由温度 \(T\) 控制：

随着退火进程推进，温度从初值 \(T_0\) 按冷却系数逐渐衰减，阿峰的“弹跳能量”越来越小，最终收敛并稳定在某座山峰上。邻域扰动的精髓就在于此：先靠高温度过山丘低谷，再靠低温锁定真正的高峰。它给了贪心搜索一个“回头”的机会，而这一回头，往往就能看见被山丘遮挡的辽阔风景。

P(accept)=exp⁡(ΔST),ΔS=S(G′)−S(G)<0\displaystyle P(\text{accept}) = \exp\left(\frac{\Delta S}{T}\right), \quad \Delta S = S(G') - S(G) < 0
公式含义：当评分差 \(\Delta S\) 为负时，接受差解的概率为指数 \(e^{\Delta S / T}\)；\(\Delta S\) 越接近 0（差距越小）概率越大，温度 \(T\) 越高概率也越大。
  1. 评分差 \(\Delta S\)候选结构评分减去当前结构评分，此时为负值，代表这是一条“下坡路”。
    ΔS=S(G′)−S(G)<0\Delta S = S(G') - S(G) < 0
  2. 温度 \(T\)一个正的控制参数，好比阿峰身上的“弹跳能量”，温度越高越敢走不寻常的路。
    T>0T > 0
  3. 接受概率\(\Delta S\) 除以 \(T\) 后取指数，得到一个介于 0 和 1 之间的概率值。
    P=exp⁡(ΔST)P = \exp\left(\frac{\Delta S}{T}\right)

多起点搜索

阿峰的经验在登山队里传开了。这一次，他不再单兵作战，而是召集了多支登山队：队长老赵从南坡出发，队员小陈从北坡出发，向导老刘则根据旧地图先标记了几个疑似高峰的坐标作为起点。大家分头行动，最后在山脚集合，汇报各自找到的最高点，取其中最高者作为全队成绩。这就是多起点搜索（Multi-start Search）的思路。

与随机重启相比，多起点搜索更强调初始点的“设计感”。随机重启的初始点完全随机，靠“碰运气”式的大量尝试来提高成功率；而多起点搜索则会刻意安排多样化的初始结构——比如一个空图（从最简模型开始）、一个随机图（探索未知区域）、一个基于专家先验的图（从可信的局部区域开始）、甚至先用贪心快速爬出一个结果作为另一个起点。这样一来，不同的“登山队”覆盖了山脉的不同区域，最终找到全局最优的可能性大大提升。

多起点搜素最终的选择逻辑非常直白——把所有队伍带回的最终解放在一起，用评分函数做终极排名，选出王者：

登山队最终找到的那座最高峰，不是靠一个人闷头苦爬，而是靠分工与多样才赢来的。多起点搜索和随机重启、邻域扰动一样，都在回答同一个问题：在你不知道全局地形的时候，怎样提高找到最高峰的可能性？ 答案是——从不同的视角多试几次。

G∗=arg⁡max⁡G∈RS(G)\displaystyle G^* = \arg\max_{G \in \mathcal{R}} S(G)
公式含义：最终答案 \(G^*\) 是所有搜索路径最终解集合 \(\mathcal{R}\) 中，评分最高的那个 DAG 结构。
  1. 结果集合 \(\mathcal{R}\)各支登山队带回的全部最终结构，即各条搜索路径的终点。
    R={Gfinal(1),Gfinal(2),…,Gfinal(m)}\mathcal{R} = \{G^{(1)}_{final}, G^{(2)}_{final}, \dots, G^{(m)}_{final}\}
  2. 逐个体检对集合中每一个最终解 \(G\) 计算评分函数 \(S(G)\)。
    S(G),G∈RS(G), \quad G \in \mathcal{R}
  3. 终极排名在所有最终解中选出评分最高者，作为多起点搜索的输出。
    G∗=arg⁡max⁡G∈RS(G)G^* = \arg\max_{G \in \mathcal{R}} S(G)

AI 应用场景

基因调控网络重构

阶段：模型训练与搜索优化

解决的问题：从基因表达数据推断基因调控网络，本质上是基于分数的因果结构学习。传统的贪心搜索容易陷入局部最优，导致识别出的调控关系偏离真实生物学通路。通过随机重启与邻域扰动，搜索可以跳出次优拓扑，找到与实验数据更吻合的调控结构。

具体案例：某癌症研究团队用多起点搜索配合贪心爬山，从单细胞 RNA 测序数据中识别与肿瘤转移相关的基因调控模块。相比纯贪心，最终结果在已知通路数据库中的命中率提升了约 35%，并发现了 3 条此前被遗漏的调控边。

金融风险传导分析

阶段：可解释 AI 与因果推断

解决的问题：金融机构需要识别风险因子之间的因果传导链，而非仅仅做相关性预测。贪心结构学习容易过早收敛到小规模子图，漏掉“流动性紧张 → 债务违约 → 股价下跌”这类长链条因果路径。邻域扰动和随机重启能帮助算法跳出短链陷阱。

具体案例：某风控团队利用模拟退火策略，从企业财务指标时间序列中推断多级风险传导的 DAG 结构，发现了一条此前模型从未捕捉到的间接因果链，并将其加入风控规则库，提升了信用风险预警的召回率。

推荐系统因果纠偏

阶段：特征工程与模型去偏

解决的问题：推荐系统的观测数据存在“曝光偏差”，热门物品被过度曝光导致模型误以为“曝光多=用户真爱”。用因果结构学习识别“用户偏好 → 曝光 → 点击”之间的因果方向，需要对多个候选 DAG 做评分比较，极易陷入局部最优。

具体案例：某电商平台使用多起点搜索，设计了“空图、曝光图、偏好先验图”三类初始结构并行爬山，最终估计出的因果 DAG 被用于指导训练样本的倾向性加权，显著缓解了热门物品的头部效应。

Python 演示

python160 行
import mathimport random  class DAG:    """用邻接矩阵表示有向无环图"""     def __init__(self, n):        self.n = n        self.adj = [[0] * n for _ in range(n)]     def copy(self):        g = DAG(self.n)        for i in range(self.n):            for j in range(self.n):                g.adj[i][j] = self.adj[i][j]        return g     def add_edge(self, i, j):        if i != j and self.adj[i][j] == 0 and not self.has_path(j, i):            self.adj[i][j] = 1            return True        return False     def remove_edge(self, i, j):        if self.adj[i][j] == 1:            self.adj[i][j] = 0            return True        return False     def has_path(self, s, t):        """深度优先判断从 s 到 t 是否存在有向路径"""        visited = [False] * self.n        stack = [s]        while stack:            u = stack.pop()            if u == t:                return True            for v in range(self.n):                if self.adj[u][v] == 1 and not visited[v]:                    visited[v] = True                    stack.append(v)        return False     def neighbors(self):        """枚举加边、删边、转边三类操作得到的所有合法邻居"""        nbrs = []        for i in range(self.n):            for j in range(self.n):                if i == j:                    continue                if self.adj[i][j] == 0:                    g = self.copy()                    if g.add_edge(i, j):                        nbrs.append(g)                else:                    g = self.copy()                    g.remove_edge(i, j)                    nbrs.append(g)                    g2 = self.copy()                    g2.remove_edge(i, j)                    if g2.add_edge(j, i):                        nbrs.append(g2)        return nbrs  def bic_score(g, data):    """极简 BIC 评分: 边数惩罚 + 数据拟合收益"""    n = g.n    edge_count = 0    fit = 0.0    for i in range(n):        for j in range(n):            if g.adj[i][j] == 1:                edge_count += 1                fit += data[i][j]    return fit - 0.5 * edge_count  def random_init(n):    """随机生成初始 DAG, 每条边以 20% 概率尝试加入"""    g = DAG(n)    for i in range(n):        for j in range(n):            if i != j and random.random() < 0.2:                g.add_edge(i, j)    return g  def hill_climb(data, n, start=None, max_steps=100):    """贪心爬山: 每次移到评分最高的邻居, 直到无法提升"""    cur = start if start is not None else DAG(n)    score = bic_score(cur, data)    for _ in range(max_steps):        best_g, best_s = None, score        for nxt in cur.neighbors():            ns = bic_score(nxt, data)            if ns > best_s:                best_s, best_g = ns, nxt        if best_g is not None:            cur, score = best_g, best_s        else:            break    return cur, score  def random_restart(data, n, k=5):    """随机重启: k 次独立随机起点贪心爬山, 保留全局最优"""    best_g, best_s = None, float('-inf')    for _ in range(k):        g, s = hill_climb(data, n, start=random_init(n))        if s > best_s:            best_g, best_s = g, s    return best_g, best_s  def simulated_annealing(data, n, T0=2.0, alpha=0.98, max_iter=500):    """模拟退火: 以一定概率接受差解, 跳出局部最优"""    cur = DAG(n)    score = bic_score(cur, data)    best_g, best_s = cur.copy(), score    T = T0    for _ in range(max_iter):        nbrs = cur.neighbors()        if not nbrs:            break        nxt = random.choice(nbrs)        ns = bic_score(nxt, data)        delta = ns - score        if delta > 0 or random.random() < math.exp(delta / T):            cur, score = nxt, ns            if score > best_s:                best_g, best_s = cur.copy(), score        T *= alpha        if T < 1e-4:            break    return best_g, best_s  def main():    random.seed(42)    n = 4    # 模拟真实因果结构带来的拟合收益: 0->1, 0->2, 1->3 是强关系    data = [[0.0] * n for _ in range(n)]    data[0][1] = 2.0    data[0][2] = 1.8    data[1][3] = 2.2    data[0][3] = 0.6     g1, s1 = hill_climb(data, n)    g2, s2 = random_restart(data, n, k=5)    g3, s3 = simulated_annealing(data, n)     print("贪心爬山    边数:", sum(sum(row) for row in g1.adj), "评分:", round(s1, 2))    print("随机重启    边数:", sum(sum(row) for row in g2.adj), "评分:", round(s2, 2))    print("模拟退火    边数:", sum(sum(row) for row in g3.adj), "评分:", round(s3, 2))  if __name__ == "__main__":    main()
目的：演示贪心爬山、随机重启与模拟退火三种结构搜索策略在 DAG 空间中的表现差异。
  1. def neighbors(self):生成当前 DAG 的全部合法邻居，对应登山的“试探脚边每一步”
  2. if self.adj[i][j] == 0:判断 i 到 j 之间是否已有边，决定当前是加边还是删边分支
  3. g2.add_edge(j, i)尝试把边 i→j 转成 j→i，即“转边”操作
  4. return fit - 0.5 * edge_count极简 BIC 评分：结构越简单加分越少，拟合越好加分越多
  5. def hill_climb(data, n, start=None, max_steps=100):贪心爬山主函数，反复进入评分最高的邻居
  6. if ns > best_s:严格大于才更新最优候选，保证每一步都“只往高处走”
  7. def random_restart(data, n, k=5):随机重启主函数，k 次独立爬山取全局最优
  8. g, s = hill_climb(data, n, start=random_init(n))从随机生成的初始结构开始一次完整爬山
  9. if delta > 0 or random.random() < math.exp(delta / T):模拟退火的接受准则：变好必接受，变差按概率接受

常见误区

误区我以为局部最优就是指搜索到的结构评分很低、分数不理想，只要评分高就是全局最优。

正解局部最优是“相对”概念——它所在的邻域内确实评分最高，但全局还有更优解。就像阿峰脚下的小土丘，在周围几公里内确实是最高点，评分值也不算低，但远处的高山才是真正的目标。一个局部最优的评分可以很高，只是还不够高。

为何常见：把“局部”理解成“差劲”，忽略了“邻域”这个关键限定范围，导致判断标准错位。

误区既然一次重启可能失败，那我重启 100 次甚至 1000 次，效果一定越来越好。

正解成功率随重启次数是指数逼近 1 的，收益边际递减。从 10 次提升到 100 次，成功率从约 89% 提升到接近 100%，但耗时也涨了 10 倍。实际工程里要在计算预算与质量之间做权衡，通常会结合扰动策略，而不是无限堆次数。

为何常见：只看到成功概率的上升，忽略了时间成本这条同样在增长的曲线。

误区模拟退火会接受差解，所以它肯定比贪心强，一定能找到全局最优。

正解理论上只有“无限慢”降温才能保证收敛到全局最优；实际有限迭代只是“更可能”接近全局最优。温度初值、冷却系数、邻域设计都会强烈影响结果，调参不当甚至比单纯贪心还差。

为何常见：把理论收敛性等同于实际性能保证，忽视了有限时间下的工程折中。

误区贪心容易陷入局部最优，那就应该彻底抛弃贪心，直接用复杂的模拟退火或多起点搜索。

正解贪心是几乎所有高级策略的“地基”——随机重启和多起点搜索本质上都是“多次贪心”，模拟退火在温度趋近于 0 时也退化为贪心。贪心得到的结果经常是后续扰动的优质起点，抛弃贪心等于扔掉了最精准的局部寻优能力。

为何常见：把“贪心的缺点”放大为“贪心一无是处”，没有看到它作为基础模块的组合价值。

误区它们不都是“从多个点开始搜”吗？我觉得这俩完全是一回事。

正解随机重启的关键在“重复试错”——用大量完全随机起始点去撞全局最优，赌的是次数；多起点搜索的关键在“多样覆盖”——刻意设计差异化的初始点（空图、随机图、先验图、贪心图），让不同区域都被探索到。实现上经常结合，但设计意图差异明显。

为何常见：只看到表面形式的相似，没理解两种策略各自想解决的核心问题不同。

面试题

Q1. 贪心搜索在每一步会做什么？

单选题 · easy

  • A.枚举全部可能的DAG结构
  • B.选择评分提升最多的操作← 正确答案
  • C.随机选择一个合法操作
  • D.保留所有候选结构

答案：B。贪心搜索的核心是“每一步都选当前评分提升最大的操作”，对应阿峰只往最高处走的登山法则。A 是全空间枚举，C 是随机搜索，D 是光束搜索的思想，都不符合贪心。

Q2. 关于局部最优，下列说法正确的是？

单选题 · mid

  • A.当前评分最低的DAG
  • B.包含边数最多的DAG
  • C.邻域最高但非全局最优← 正确答案
  • D.评分等于全局的最优DAG

答案：C。局部最优是“邻域内评分最高，但不是全局最高”的结构，恰如阿峰脚下的小土丘——周围几公里它最高，但远处还有更高的山。A 把方向搞反了，B 与评分无关，D 描述的是“找到了全局最优”而非局部最优。

Q3. 在模拟退火中，“温度”的作用是什么？

单选题 · easy

  • A.数据归一化范围
  • B.节点数量控制
  • C.边的权重赋值
  • D.差解接受概率← 正确答案

答案：D。温度控制算法接受差解的概率：高温时像弹力球一样敢走“下坡路”，低温时则趋于稳定，只走高坡。A、B、C 都是干扰项，温度与评分函数、结构形态无关。

Q4. 随机重启策略的核心思想是什么？

单选题 · mid

  • A.多次随机起点爬山择优← 正确答案
  • B.反复修改当前解的边
  • C.放弃评分改用互信息
  • D.用深度优先搜索替代

答案：A。随机重启就是多次从随机初始点出发独立做贪心爬山，最终选择评分最高的结果，相当于阿峰被直升机空投到不同区域多爬几次山。B 是邻域扰动，C 换了一种评分准则，D 换了搜索策略，都不是重启的本意。

Q5. 贪心搜索陷入局部最优的根本原因是什么？

单选题 · mid

  • A.评分函数计算耗时太多
  • B.只接受提升且邻域有限← 正确答案
  • C.初始DAG包含太多边
  • D.原始数据量过于庞大

答案：B。贪心只接受评分提升的移动，且邻域只覆盖单步操作，导致它无法绕过“评分低谷”去发现更高的地方。就像阿峰坚持不走下坡路，就永远到不了被山谷隔开的那座大山。C、D 是工程问题而非结构成因。

Q6. 单次搜索找到全局最优的概率 p=0.2，随机重启 k=5 次，至少成功一次的概率约为？

单选题 · hard

  • A.约 0.20
  • B.约 0.33
  • C.约 0.67← 正确答案
  • D.约 1.00

答案：C。用公式 \(1-(1-p)^k\) 计算：\(1 - 0.8^5 = 1 - 0.32768 \approx 0.67\)。这正是随机重启“用次数换概率”的量化体现。A 是单次概率，B 是 \(0.8^5\) 的取值，D 错在假设必然成功。

Q7. 贪心搜索中的“邻域”指的是什么？

单选题 · easy

  • A.所有合法DAG结构集合
  • B.相同评分的结构集合
  • C.随机构造的结构集合
  • D.单步边操作邻居集合← 正确答案

答案：D。邻域是对当前结构做一次加边、删边或转边操作所能到达的合法 DAG 集合。A 是整个搜索空间，B 是等分线概念，C 是随机采样，都不是邻域的准确定义。

Q8. 下列哪些策略可以有效缓解局部最优问题？

多选题 · mid

  • A.使用随机重启策略← 正确答案
  • B.使用邻域扰动策略← 正确答案
  • C.使用多起点搜索策略← 正确答案
  • D.提高评分函数精度

答案：ABC。随机重启、邻域扰动（模拟退火）、多起点搜索是三大经典逃逸策略，分别从次数、跳离、多样三个角度突破局部最优。提高评分函数精度只让“海拔仪”更准，无法解决“只走高处”的路线问题。

Q9. 关于局部最优与全局最优的关系，下列说法正确的是？

多选题 · mid

  • A.局部最优在邻域内评分最高← 正确答案
  • B.全局最优不一定是局部最优
  • C.全局最优一定是局部最优← 正确答案
  • D.局部最优不一定就是全局最优← 正确答案

答案：ACD。局部最优在邻域内评分最高（A 对）；全局最优在其邻域内也不可能有更高评分的邻居，否则它就不是全局最优，因此全局最优一定是局部最优（C 对、B 错）；局部最优只是“邻域之王”，不一定能称霸全局（D 对）。

Q10. 关于随机重启与多起点搜索，下列说法正确的是？

多选题 · hard

  • A.两者都会从多个初始结构出发← 正确答案
  • B.随机重启侧重重复试错次数← 正确答案
  • C.多起点侧重初始点多样性← 正确答案
  • D.两者本质上是完全相同的

答案：ABC。两者都从多个初始结构出发（A 对）；随机重启靠随机初始点的重复次数磨概率（B 对）；多起点搜索刻意设计多样化初始点，如空图、先验图、贪心结果等，强调覆盖不同区域（C 对）。D 忽略了设计意图的本质差异。