在这个例子中，状态空间树是如何逐层扩展的？

适用条件

• 树是逐层探索的。
• 在每个节点，只追加从根节点路径上尚未使用的作业。
• 视频仅展示了结构扩展，没有展示按界限剪枝。

理解与推导

1. 从代表空部分序列的根节点开始。
2. 为每个可能的第一个作业选择创建一个子节点：$J_1$, $J_2$, $J_3$, $J_4$。
3. 完成根节点的所有直接选择，然后扩展节点 2，接着节点 3，节点 4，节点 5。
4. 继续以类似的方式跨其余前沿扩展，直到所有显示的节点达到深度 4。

例子

讲师说：“现在这一层完成了。看，我已经逐一考虑了所有作业，”然后继续扩展前沿上的下一个节点，而不是深入刚创建的子节点下方。

容易误解的地方

• 假设树是按深度优先扩展的，先沿着一条分支向下到全深度，然后再移到兄弟节点。
• 认为在每个节点都可以追加所有作业，而忽略了路径上已经使用的作业。

观看对应讲解

继续追问

• 在作业排序树中，从根到节点的路径意味着什么？
• 为什么这段视频说分支限界法是广度优先而不是深度优先？
• 最小成本分支限界法如何决定接下来探索哪个节点？