思维树（Tree of Thoughts，简称ToT）把大模型的推理过程组织成一棵可回溯、可评估的搜索树，极大提升了复杂任务的解题能力。但很多人在实际使用中发现，ToT的效果虽好，搜索开销却大得惊人：一棵只有分支因子3、深度5的树，全量展开就有超过360个中间节点，每个节点都要调用一次模型生成、若干次模型评估，Token消耗呈指数级增长。此时搜索策略的选择就成了决定性因素——用广度优先（BFS）逐层铺开，还是用深度优先（DFS）一条路走到黑再回溯，两种思路在效率、内存和剪枝配合上的表现截然不同。
一、BFS与DFS在ToT中的核心差异
广度优先搜索的策略是逐层扩展：先生成第一层的所有候选思路，评估后保留较优的一批，再进入第二层。这种方式的优点在于每一步决策都建立在全局比较的基础上——同一层的所有候选站在同一起跑线上被评估，选出的结果更稳定，不容易因为某个思路“开局唬人”而误入歧途。对于思路之间彼此独立、需要横向比较的任务（比如写作大纲的多方案筛选、数学题的多步分解），BFS的层内竞争机制非常有效。
但BFS的代价同样明显：它必须把整层节点都保存在内存和候选队列里，扩展宽度直接决定成本。如果分支因子设为5、深度设为6，中间状态的存储和评估请求会迅速膨胀。此外，BFS天然不适合深度很大的问题——层数多时，你需要在很浅的层次就做出保留哪些节点的判断，而浅层评估往往信息量不足，剪枝过早容易把好苗子剪掉。
深度优先则是另一条路：从根节点出发，沿一条思路一路深挖到底，得到完整答案后评估，不理想再回溯换分支。它的内存占用极小，任一时刻只需保存当前路径上的节点，特别适合解空间深、且中间状态就能判断好坏的任务，比如24点游戏、填字谜题。DFS可以配合提前终止条件——一旦某条路径触发了明确的失败信号（如数值溢出、矛盾状态），立即回溯，避免浪费后续生成。它的弱点是缺乏横向比较，容易陷入局部较优的分支里反复探索。
二、两种策略的代码实现要点
下面用一个简化Python实现来展示两种策略在ToT框架中的结构差异。理解这段代码的关键在于看清节点队列的管理方式：BFS用双端队列逐层弹出，DFS用栈（或递归）沿单链深入。
from collections import deque
class ToTNode:
def __init__(self, state, parent=None):
self.state = state # 当前推理状态（如已生成的部分推理链）
self.parent = parent
self.children = []
self.score = None # 评估得分，由LLM打分
# 广度优先：逐层生成并筛选
def bfs_search(root, gen_fn, eval_fn, breadth, max_depth):
queue = deque([root])
depth = 0
while queue and depth < max_depth:
next_layer = []
for _ in range(len(queue)):
node = queue.popleft()
for child_state in gen_fn(node.state, n=breadth):
child = ToTNode(child_state, parent=node)
child.score = eval_fn(child_state)
node.children.append(child)
next_layer.append(child)
# 只保留得分最高的若干节点进入下一层
next_layer.sort(key=lambda n: n.score, reverse=True)
queue = deque(next_layer[:breadth])
depth += 1
return queue[0] if queue else root
# 深度优先：递归深入，失败即回溯
def dfs_search(node, gen_fn, eval_fn, breadth, max_depth, threshold):
if check_terminal(node.state) or depth_limit(node):
return node if eval_fn(node.state) > threshold else None
for child_state in gen_fn(node.state, n=breadth):
child = ToTNode(child_state, parent=node)
node.children.append(child)
result = dfs_search(child, gen_fn, eval_fn,
breadth, max_depth - 1, threshold)
if result is not None:
return result
return None # 所有分支失败，回溯到上层
从代码可以看出两个关键细节。第一，BFS中的next_layer[:breadth]实现了层内剪枝，breadth参数直接控制每层保留的节点数，它是效率与质量的第一个旋钮：breadth过大则评估请求爆炸，过小则容易误删。第二，DFS的回溯通过函数返回值的失败信号实现，配合threshold阈值可以在中间状态就放弃明显不合格的分支，这是DFS省Token的核心手段。
三、如何根据任务特征选择策略
选BFS还是DFS，本质上取决于三个问题：推理链有多深、中间状态是否可评估、解空间是否有多条可行路径。可以参考下面的对照表来快速判断。
| 任务特征 | 推荐策略 | 理由 |
|---|---|---|
| 推理步数少（3步以内）、候选思路需横向比较 | BFS | 层数少时逐层筛选成本可控，层内竞争提升质量 |
| 推理步数多、可提前判断分支死路 | DFS | 回溯机制剪枝灵活，内存占用小 |
| 创意生成类（大纲、方案设计） | BFS | 浅层思路难以评分，需完整展开后再比较 |
| 约束满足类（谜题、规划） | DFS | 中间状态即可检测违规，早剪枝收益极大 |
除了策略本身，还有两个参数对效率影响巨大。一是每个节点的采样次数：ToT原论文中，DFS路线对同一状态采样多个候选再排序，相当于在深度优先中嵌入了一次微型BFS，实测能显著减少无效回溯。二是评估方式：用一次性打分替代成对比较，可以把评估请求从O(n²)降到O(n)，当分支因子较大时这是最直接的成本优化。
四、进阶思路：混合策略与动态切换
实际的复杂任务往往兼具深与宽的特征，此时硬套单一策略都不理想。一种实用的混合方案是“先宽后深”：前两三层用BFS铺开、严格筛选，把明显不合格的思路在早期淘汰，一旦候选收敛到少数几条优质分支，就切换成DFS快速挖到底。这样既保留了浅层的全局视野，又避免了BFS在深层的成本失控。
另一种思路是动态调整分支宽度：根据当前层的平均评估得分判断探索价值，得分整体偏低说明这一层质量差，直接收缩宽度甚至整层放弃；得分分化明显则说明存在值得深挖的线索，适当加宽。这类似于蒙特卡洛树搜索中的置信上界思想，用反馈信号指导搜索预算的分配，而不是把固定的计算量平均撒到每个节点上。
最后要提醒的是，策略再好也不能替代对任务本身的理解。如果你的任务中间状态根本没有可靠的评估信号，任何剪枝都可能变成盲目赌博，此时不如退一步用BFS小宽度全展开，或者干脆降低树的复杂度，把多步推理拆成多个独立的ToT子问题。搜索策略的终极目标不是穷举聪明，而是把有限的模型调用预算花在最可能产出答案的路径上。