求解旅行商问题的最短回路时，算法为每个部分路径计算一个可能总代价的下界；若下界已经不小于当前最优完整回路，就不再扩展该结点。该策略最符合（）。
题干的决定性信息是“当前最优值”和“下界”。分支限界法围绕优化目标维护界，用界判断某个分支是否还有机会优于已知解；没有机会就剪掉。
选项分析
正确。下界不优于当前最优值时可安全淘汰该分支。
错误。题干显然在维护部分路径、下界和当前最优解。
错误。递归是一种实现手段，不能仅凭递归判断算法范式。
错误。散列能加快键查找，不能直接解决组合优化问题。
本题为什么容易错
把“剪枝”一律等同于回溯，是这类题最常见的失分点。两者都有剪枝，真正要辨认的是剪枝根据：违反约束，还是不可能得到更优目标值。
简短答案
旅行商问题求最短路线，为什么常用下界剪枝的分支限界法，正确答案是 A（分支限界法，利用目标函数界限淘汰不可能更优的活结点）。题干的决定性信息是“当前最优值”和“下界”。分支限界法围绕优化目标维护界，用界判断某个分支是否还有机会优于已知解；没有机会就剪掉。
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 分支限界法，利用目标函数界限淘汰不可能更优的活结点 | 本题正确答案 | 正确。下界不优于当前最优值时可安全淘汰该分支。 | 看到题干核心场景时优先联想到它 |
| 顺序查找，不保留任何搜索状态 | 本题干扰项 | 错误。题干显然在维护部分路径、下界和当前最优解。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 简单递归，只要递归就一定属于回溯法 | 本题干扰项 | 错误。递归是一种实现手段，不能仅凭递归判断算法范式。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 哈希查找，通过散列地址直接得到最短回路 | 本题干扰项 | 错误。散列能加快键查找，不能直接解决组合优化问题。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 顺序查找，不保留任何搜索状态：错误。题干显然在维护部分路径、下界和当前最优解。
- 简单递归，只要递归就一定属于回溯法：错误。递归是一种实现手段，不能仅凭递归判断算法范式。
- 哈希查找，通过散列地址直接得到最短回路：错误。散列能加快键查找，不能直接解决组合优化问题。
知识点详解
分支限界法把问题拆成多个子问题，为活结点计算界，并按FIFO、优先队列等策略选择下一结点。最小化问题常用下界：若某分支的下界已不小于当前最优上界，就不可能产生更好解。回溯法通常沿一条路径深入，违反约束后退。
备考速记
回溯先问能不能走，分支限界再问走下去值不值得。
旅行商问题在旅行商问题场景中的作用
旅行商中可用已走代价加剩余结点最小可能连接代价构造下界。下界越紧，剪枝越多；但它必须保持乐观，不能把真正可能的最优路线提前剪掉。
同类题怎么考
- 根据剪枝依据判断回溯法或分支限界法。
- 判断目标函数界限必须满足的安全性条件。
旅行商问题在软件设计师软考中的考法
看到“求最优、维护当前最好、用上下界淘汰”选分支限界；看到“枚举可行方案、违反约束立即退回”更接近回溯。
解题思路
不要只看它用了递归还是队列，要看剪枝证据。这里不是“该路径违反城市不能重复”这种可行性约束，而是“即使继续走也不可能比当前答案更便宜”的优化界，典型属于分支限界，选A。
考点定位
回溯与分支限界都搜索状态空间，也都能剪枝。考试常见区别是：回溯更强调约束与可行解、常深度优先；分支限界更强调目标函数上下界与最优解、常管理活结点表。
易错提醒
- 下界估计大于真实最优剩余代价，错误剪掉可能的最优解。
- 找到第一个可行解就停止，误认为它必然最优。
- 没有及时用更好的完整解更新当前上界，导致剪枝效果很差。
备考提示
- 做题先圈出可行性约束、当前最优值、上界或下界。
- 用装载、旅行商和0/1背包分别练一次状态空间树。
你可能还想了解
- 有剪枝就一定是回溯法吗？
- 分支限界为什么能保证最优解？
- 最小化问题的下界怎么用？
本文小结
题干用部分路径下界与当前最优值比较来剪枝，属于分支限界法；判断关键是目标函数界限，而非是否使用递归。