有界广度优先搜索：如何寻找合作任务的完成路径

广度优先搜索（BFS）是一种逐层探索图的方法：先检查一步能到的状态，再检查两步、三步能到的状态。ToWow 的联合行动形成研究用它分析一个具体问题：给定当前状态、允许的动作、完成条件和资源预算，能否找到把任务做完的动作序列？找到时返回路径；没有找到时，还要判断动作清单是否足以支持“不可达”的结论。

一个接口已经存在，权限也已经给了，但开关没有打开。此时问系统“任务能不能完成”，可能得到两个完全不同的答案。只尝试当前可用的操作，会说不能；如果允许先打开接口，再完成任务，就能找到一条路。

这不是措辞差异。它决定系统遇到障碍时，是马上返回失败，还是给出一个具体、可检查的准备动作。

本文解释的是一项有限合成模型中的搜索实现。我们先说明模型怎样表示完成条件和动作前提，再展示队列如何找到路径，最后检查搜索失败究竟能说明什么。

研究模型中的任务包含转移、投影、接受、读回几个动作。为方便阅读，可以把它理解为一条简化的数据处理流程：转移数据，生成目标表示，确认接受，再读回检查。这里的动作是程序里的抽象状态变化，并不代表已经连接了真实服务。

完成也有具体条件：转移和投影各发生一次，接受与读回已经发生，授权有效，任务没有被偷换，价值底线没有失效，并且没有超过预算。只看到“执行过”还不够，因为执行结果可能没有被接受，或者执行过程中换掉了原任务。

接下来，模型要规定每个动作什么时候能做。例如，转移需要通路可用且已有授权；投影要等转移发生；接受要等目标表示生成。如果接口关闭，直接转移就没有后继状态。这种约束把“可能下一步做什么”变成了可以逐项检查的问题。

搜索从当前状态开始，把它放进一个队列。取出队首状态后，依次尝试允许的动作；动作条件满足，就计算新状态，把尚未见过的新状态放到队尾。随后继续取队首。

关键在于先进先出。一步产生的状态先被检查，再轮到两步产生的状态。因此，只要每条边代表一个动作，第一次找到目标时，得到的是动作步数最少的一条路径。这正是标准广度优先搜索的性质。BreadthFirstDirectedPaths

用一个与历史场景分开的教学分叉看队列的作用。起点有两条路：起点→A→A1→目标，以及 起点→B→目标。即使先遇见 A，算法也不会沿 A 一直走到底。检查起点后队列为 [A,B]；取出 A，加入 A1，队列变成 [B,A1]。接下来轮到 B，它已能产生目标。最终先找到的是两步的 B 路线，而不是三步的 A 路线。队列保存的是搜索顺序，因此先列出的动作不会独占全部探索。

在历史记录里的 enable 构造场景中，只允许原有执行动作时，初始接口关闭，没有可走的完成路径。加入“打开接口”这个已有但尚未执行的准备动作后，搜索找到了：

打开接口 → 转移 → 投影 → 接受 → 读回

这五步把笼统的“缺少能力”改成了一个更窄、更有用的判断：这个模型缺的是激活条件。它不需要在此处发明新的传输方式。

这条记录也给了我们一个直接的变体。若将步数上限从 10 收紧到 4，并保持其余动作条件不变，上面这条五步路线就不再可达。搜索失败的含义随之变化：它无法在四步内完成，不能再说完全没有完成办法。

步数和成本还要分开。一条两步路线可能比另一条三步路线更贵。当前搜索按层推进，因此先找到较短路线；它会检查成本是否超预算，却不会在所有可行路线里保证成本最低。需要最低成本时，应改用相应的带权最短路方法，并明确边成本的条件。

有限搜索之所以能查完，是因为我们给它划了边界。那一轮研究设置了最多 10 步、成本上限 10、隐私成本上限 2，以及至多一次人工额度；可选动作和状态变量也是有限的。随着动作增多、路径变长，可能状态会迅速增加。这些预算决定模型正在回答哪个问题。在历史实验的十种小世界里，预算一次也没有把搜索截断：每个动作能做的次数都有上限，所以每一次搜索都在预算起作用之前就结束了，要么找到路径，要么已经没有新的状态可查。模型更大时，控制计算规模也要靠这些预算。

在这个范围里找到路径，可以拿出完整动作序列，逐步检查前提和状态变化。找不到路径时，则必须再看一个问题：动作清单完整吗？

如果清单被声明为完整，所有允许状态也都查完，模型会给出有界的不可达结论。如果清单本身承认不完整，它会返回“未知”。例如，现实中也许可以请人制作新工具，但模型没有列出如何制作、需要谁同意、花多少资源。此时没有搜索到路径，不能排除那条尚未表达的路。

模型本身只返回一条路径或一个结论，但有了这一区分，人能看出下一步该往哪里做。预算太紧，可以讨论是否增加预算；某个前提关闭，可以检查能否激活；动作清单不完整，则需要补充真实可用的办法。把所有情况都写成“失败”，会让这些方向一起消失。

历史实验共构造了十种小世界。我们让三个具备相同动作能力的调度版本在这些世界里运行。这三个版本都是按规则出计划的规划器，并不做搜索：一个从目标往回推，一个按固定的异常转办流程走，第三个是我们为新调度方法准备的候选。每个版本只查看一次世界的状态，然后要么执行自己的计划，要么停下。三个版本在同样的六种世界里完成了任务，在另外四种里停下。在这四种世界里停下意味着什么，由有界搜索判定：其中三种是预算内不可达，一种是“未知”，因为那个世界的动作清单自己承认不完整。三种不可达都不是预算问题：一种是价值底线已经失效；一种是所有者拒绝；还有一种所有者也拒绝，而且通路不可用，也无法打开。这三个版本共享实现基础，所以也不构成三个独立系统的验证。候选方案没有获得独占的成功场景。

这个结果没有支持“需要一种新调度算法才能解决这些任务”。它支持的是更具体的设计判断：只要把准备动作、授权条件和完成判据写进同一模型，经典搜索已经能够区分其中一部分原先混在一起的障碍。真正承重的工作，常常在于有没有把可改变的条件表达出来。

现实比这十个小世界复杂得多。人可能拒绝，动作可能失败，新工具也可能出现。有限模型不能穷尽这些变化。但当我们需要审视一个具体流程时，一条五步见证路径仍然比“理论上可以完成”更有用：每一步都能继续追问，前提是谁提供的，能否实际执行，执行后怎样确认。研究因而有了走向现实的下一处接口。

实现与证据。 搜索器（实现定位保留于编辑档案）；状态和动作模型（实现定位保留于编辑档案）；原始搜索输出（实现定位保留于编辑档案）。证据范围为本地有限合成自测；文中四步上限是从动作前提推出的教学变体，不冒充该历史运行的另一项实测。

更正（2026年10月26日）：初版有三处说法与研究代码和运行记录不符。一是说预算“同时也限制计算规模”，实际在历史实验的十种小世界里预算从没截断过搜索，搜索能查完靠的是每个动作的次数上限；二是说这一区分“使系统能给出不同的后续动作”，实际模型只返回路径或结论，后续怎么做由人来定；三是说三个调度版本“三种都不可达，一种都保持未知”，实际三个版本都是按规则出计划的规划器，只在四种世界里停下，在这四种世界里停下意味着什么由有界搜索判定。三处已在正文改正。

本篇另备有明亮、适合手机连续阅读的公众号排版稿，配图按照本文机制单独绘制。查看公众号版，或下载 Markdown、HTML、PNG 与 SVG 配图包。