7 分支定界法简介

1. 公式
   观察依据

   任务集 = {$J_1$, $J_2$, $J_3$, $J_4$}

Jobs

作业调度问题中所有任务的集合。

四个离散任务的集合

1. 公式
   观察依据

   P 等于由 10、5、8 和 3 组成的集合

P

与每个任务关联的利润集合。

四个数值的集合

1. 公式
   观察依据

   d 等于集合 1、2、1、2

d

与每个任务关联的截止时间集合。

四个数值的集合

1. 公式
   观察依据

   $S1 = {J_1, J_4}$

S1

以任务子集形式表示的可变规模解。

任务的子集

1. 公式
   观察依据

   S2 等于集合 {1, 0, 0, 1}

S2

一种固定大小的解，用二进制向量表示哪些工作被选中执行。

长度为4的二进制向量

1. 公式
   观察依据

   白板右侧显示 Jobs = {$J_1$, $J_2$, $J_3$, $J_4$}。

Jobs

作业排序示例中所考虑的四个作业构成的集合。

作业标签的集合

1. 公式
   观察依据

   白板右侧显示 $P = {10, 5, 8, 3}$。

1. 本片段中，视频未口头说明 P 中各元素代表什么。

P

一个与四个作业关联的列表向量；本片段未解释其含义。

1. 公式
   观察依据

   白板右侧显示 $d = {1, 2, 1, 2}$。

1. 本片段中，视频未口头说明 d 中各元素代表什么。

d

一个与四个作业关联的列表向量；本片段未解释其含义。

1. 公式
   观察依据

   白板右侧显示 $S1 = {J_1, J_4}$。

1. 本片段未解释 S1是如何得到的，也未说明其用途。

S1

白板上写出的一个作业子集；本片段未说明其作用。

1. 公式
   观察依据

   白板右侧显示 $S2 = {1, 0, 0, 1}$。

1. 该视频未解释 $0/1$ 模式在 S 中的含义2，本片段中未作说明。

S2

黑板上写有一个 $0/1$ 向量；本片段未解释其含义。

1. 图示
   观察依据

   随着教师展开状态空间树，树节点按 1 至 17 编号。

1,2,...,17

用于追踪所绘制树中各状态扩展顺序的节点标识符。

标记树节点的正整数

1. 公式
   观察依据

   任务集合 = {$J_1$, $J_2$, $J_3$, $J_4$}

Jobs

待排序的任务集合

离散集合

1. 声音
   观察依据

   本节主题是分支限界法。这是又一种问题求解策略，一种用于解决具体问题的方法。

分支限界法是一种用于求解优化问题的问题求解策略，尤其适用于最小化问题。

1. 适用于优化问题

2. 主要适用于最小化问题

1. 声音
   观察依据

   假设我说我正在执行工作一和工作四，这就是我的一个解。那么该解可表示为这些工作构成的一个子集。

2. 公式
   观察依据

   $S1 = {J_1, J_4}$

解被表示为所有可选工作构成的一个子集，其大小随所选工作数量的不同而变化。

1. 解的规模取决于所选任务的数量

1. Jobs

1. 声音
   观察依据

   表示解的第二种方法是：第一个任务执行，第二个和第三个任务不执行，第四个任务执行。因此这是一种可变规模解，而这是一种固定规模解。

2. 公式
   观察依据

   S2 等于集合 {1, 0, 0, 1}

解被表示为一个二进制向量，其中每个位置对应一项任务，其取值表示该任务是否被执行（1）或未被执行（0）。解的规模恒等于任务总数。

1. 解的规模固定，且等于任务数量

1. Jobs

1. 声音
   观察依据

   在回溯法中，我们将考虑下一层；但在此处的分支限界法中，我们还会考虑第二个作业，然后是第三个作业，再然后是第四个作业。

2. 声音
   观察依据

   因此，这类似于广度优先搜索：我们不按深度方向进行，不采用深度优先搜索，而是采用广度优先搜索来探索问题的解。

3. 声音
   观察依据

   因此，回溯法与分支限界法的区别在于：回溯法是深度优先搜索，而分支限界法是广度优先搜索。

该片段在同一作业排序状态空间树上对比了两种搜索策略：回溯法被描述为先沿某一分支向下深入至下一层，再考虑同层兄弟节点；而分支限界法则被描述为先扩展当前层的所有备选节点。教师明确将此总结为：回溯法是深度优先搜索，分支限界法是广度优先搜索。

1. 应用于作业排序的状态空间树。

2. 该比较关注的是探索顺序，而非剪枝规则或代价评估。

1. 含四个作业的作业排序状态空间树

1. 图示
   观察依据

   顶部中央标题为“分支限界法”；右侧列出作业排序问题：作业集 = {$J_1$, $J_2$, $J_3$, $J_4$}，利润向量 $P = {10, 5, 8, 3}$，截止时间向量 $d = {1, 2, 1, 2}$，$S1 = {J_1, J_4}$，$S2 = {1, 0, 0, 1}$。

2. 声音
   观察依据

   一旦我选择第一个作业，那么后续可能的解有哪些？我可以选第二个作业，也可以选第三个作业，之后还可以选第四个作业。

3. 声音
   观察依据

   如果我沿其中一条路径走，就表示我执行了第一个作业和第四个作业，而未选择第二个和第三个作业。

1. 该片段未定义目标函数，也未解释数值向量 P 和 d 的含义。

该例题是一个含四个作业 $J_1$, $J_2$, $J_3$, $J_4$ 的作业排序问题。授课教师绘制了一棵根树，其每条分支对应从剩余作业中选择下一个作业；从根节点出发的一条路径记录了一个已选作业的有序部分序列；例如，先沿标记为 $J_1$ 的分支、再沿标记为 $J_4$ 的分支行进，表示依次执行作业 1 和作业 4，而此时作业 2 与作业 3 尚未被选取。

1. 共有四个互不相同的作业。

2. 每条边的标签表示将一个作业追加到当前的部分序列末尾。

3. 该片段仅构建了树的结构，未进行可行性或最优性评估。

1. 声音
   观察依据

   现在这一层已全部完成。请看，我已逐一考虑了所有作业。

2. 声音
   观察依据

   现在，一旦我选择第一个作业，那么后续可能的解有哪些？我可以选第二个作业，也可以选第三个作业，之后还可以选第四个作业。

3. 声音
   观察依据

   现在我该扩展哪个节点？是扩展这个，还是这个？接下来是这个。

4. 图示
   观察依据

   在完成节点1的子节点后，教师依次扩展节点2、节点3、节点4、节点5，并在深入下一层之前先遍历当前前沿的所有节点。

在生成根节点的子节点后，教师将该整层视为已完成，然后从左到右依次扩展当前前沿上的节点。直观过程为：先完成所有从根节点出发的直接选择，再扩展节点2，接着是节点3、节点4、节点5，并依此类推。这体现了候选序列的按层生成方式，而非先将某一条路径探索至最大深度。

1. 该树按层级逐层进行探索。

2. 在每个节点处，仅追加那些在从根节点到该节点的路径上尚未使用过的作业。

3. 该片段仅展示结构上的扩展，不涉及基于界值的剪枝。

1. 分支限界法采用广度优先扩展，而回溯法则不然。
2. 含四个作业的作业排序状态空间树

1. 声音
   观察依据

   因此，这就是您所关注的解对应的状态空间树。

2. 图示
   观察依据

   白板上展示了一棵树状结构，其节点标记为1至14，边标记为$J_1$至$J_4$。

状态空间树以树状结构中的节点和分支表示所有可能的解（即作业序列的所有排列）。每个节点对应一个作业的部分序列。

1. 适用于作业排序等组合优化问题。

1. 声音
   观察依据

   若我考察任意一个节点，该节点表示我正在考虑第二项作业和第四项作业；而该节点则表示我正在考虑第三项作业和第四项作业。

2. 图示
   观察依据

   讲师指向树中特定的节点。

状态空间树中的每个节点都代表一个特定的作业部分序列。例如，某个节点可能表示包含第二项作业和第四项作业的序列。

1. 节点通过每次向序列中添加一个作业来生成。

1. 作业排序问题的状态空间树

1. 声音
   观察依据

   在生成过程中，我会将这些节点压入栈中……接下来我应该扩展哪个节点？我应该扩展第五个节点……弹出这个节点并进行扩展……

2. 图示
   观察依据

   讲师绘制一个表示栈的竖直矩形，并在其中写入数字，以表示节点被压入和弹出的过程。

第二种方法使用栈来管理状态空间树的探索：节点生成后被压入栈中，而从栈顶弹出以进行扩展，从而实现深度优先搜索的顺序。

1. 需要一种后进先出（LIFO）的数据结构。

2. 用于在不使用递归的情况下系统性地探索状态空间树。

1. 作业排序问题的状态空间树

1. 公式
   观察依据

   教师在白板上写下 Queue -> FIFO。

2. 声音
   观察依据

   他说，若使用队列，则称为先进先出分支限界法。

本讲中，先进先出分支限界法通过使用队列来选择下一个待探索节点加以定义。

1. 当从队列中选取下一个节点时，适用于分支限界搜索。

1. 本分支限界法场景中的广度优先扩展规则

1. 公式
   观察依据

   教师在白板上写下“Stack → LIFO”。

2. 声音
   观察依据

   他指出，若使用栈，则该分支限界法称为LIFO分支限界法。

本讲中，LIFO分支限界法通过使用栈来选择下一个待探索节点加以定义。

1. 当从栈中选取下一个节点时，该方法适用于分支限界搜索。

1. 本分支限界法场景中的广度优先扩展规则

1. 公式
   观察依据

   教师在白板上写下“Least cost → LC-BB”，随后在主标题下方补充写上“Least Cost - BB”。

2. 声音
   观察依据

   他介绍了最小代价分支限界法，并将其简称为LC分支限界法。

1. 本片段提到了LC-BB这一名称，但尚未给出其完整的节点选择规则，仅引入了节点代价的概念。

本讲介绍了一种名为最小代价分支限界法的第三种分支限界方法，缩写为LC-BB。

1. 作为分支限界法框架内的另一种方法予以呈现。

1. 先进先出分支限界法
2. LIFO分支限界法

1. 声音
   观察依据

   但它仅适用于求解优化问题中的最小化问题，不适用于最大化问题。不过，我们总能将最大化问题转化为最小化问题，进而用该方法求解。

分支限界法适用于求解优化问题，特别是最小化问题。最大化问题可通过转化变为最小化问题，从而使用该方法求解。

1. 该问题是一个优化问题

1. 声音
   观察依据

   因此，回溯法与分支限界法的区别在于：回溯法采用深度优先搜索，而分支限界法采用广度优先搜索。

1. 这是教师针对本例所作的总结，并非带有前提条件的完全一般性定理。

在本讲片段中，教师指出：回溯法通过深度优先搜索探索解空间，而分支限界法则通过广度优先搜索探索解空间。

1. 讨论聚焦于对组合问题（如作业排序）的状态空间树进行搜索。

本片段中所比较的各类方法。

1. 声音
   观察依据

   因此，若我沿某一条路径行进，该路径表明我执行第一项工作和第四项工作，而不执行第二项和第三项工作。这便是其含义。

沿所绘制树中的某条路径行进，对应于按该路径顺序选取相应的工作；例如，先经过 $J_1$ 再经过 $J_4$ 的路径，表示执行工作 1 和工作 4，且在该部分路径中不执行工作 2 和工作 3。

1. 该树即为黑板上所画出的工作排序问题的状态空间树。

针对所展示树中的路径。

1. 声音
   观察依据

   讲师将此前的方法与当前方法进行对比，随后指出先进先出、后进先出及最小代价这三种方法。

2. 公式
   观察依据

   黑板上列出了1。FIFO-BB、2。LIFO-BB、3。LC-BB。

在本讲段中，分支限界法以三种变体形式呈现：FIFO-BB、LIFO-BB 和 LC-BB。

1. 讨论内容是针对作业排序状态空间树的分支限界搜索方法。

针对本片段中介绍的这些方法。

1. 声音
   观察依据

   他指出，我们对全部三种方法都这样做——无论采用 FIFO、LIFO 还是 LC——只有这样，才能求解最小化问题。

1. 该片段并未证明为何需要节点代价，而是将其作为解释的一部分直接陈述。

根据授课教师的说法，为求解最小化问题，在 FIFO、LIFO 和 LC 这三种方法中均需赋予节点代价。

1. 正在求解的问题是一个最小化问题。

2. 搜索被组织为一棵分支限界状态空间树。

针对本片段中所命名的这三种分支限界法。

1. 声音
   观察依据

   我将首先采用子集法，即这种可变规模解的方法。因此，我可以绘制状态空间树，并说明我正在考虑第一个任务。

2. 动画
   观察依据

   绘制一个根节点，以及一条标有 J1 的左分支。

1. 公式

   $$$$
   解释

   选择子集法（变长解）来表示解。

   步骤依据

   明确偏好采用子集法。

   视频直接表达
2. 公式

   $$$$
   解释

   为状态空间树绘制一个根节点。

   步骤依据

   状态空间树的标准初始化。

   视频直接表达
3. 公式

   $$$$
   解释

   从根节点向左引出一条分支，并标记为 J1。

   步骤依据

   表示决定考虑第一个作业。

   视频直接表达

演示了使用子集法构造作业排序问题的状态空间树的初始步骤。

1. 声音
   观察依据

   但在此处的分支限界法中，我们还会考虑第二项工作，然后是第三项工作，再然后是第四项工作。

2. 图示
   观察依据

   从根节点 1 出发，讲师画出四条向外的边，分别标记为 $J_1$、$J_2$、$J_3$、$J_4$，并指向节点 2、3、4、5。

1. 公式

   $$$$
   解释

   从代表空的部分序列的根节点开始。

   步骤依据

   该树是为四项可用工作进行工作排序而构建的。

   视频直接表达
2. 公式

   $$$$
   解释

   为每一种可能的首项工作选择创建一个子节点：$J_1$、$J_2$、$J_3$、$J_4$。

   步骤依据

   教师指出，分支限界法在此阶段考虑第二、第三和第四项工作，图中展示了从根节点出发的全部四个一级分支。

   视频直接表达
3. 公式

   $$$$
   解释

   从左到右依次将新创建的节点编号为2、3、4、5。

   步骤依据

   黑板在画出这些节点后，清晰地标出了它们的标签。

   视频直接表达

状态空间树的第一层包含所有仅含一项工作的部分序列，体现了替代方案的广度优先生成。

1. 声音
   观察依据

   现在这一层已完成。请看，我已经逐个考虑了所有工作。

2. 声音
   观察依据

   现在，一旦我先选取第一项工作，那么接下来可能的解有哪些呢？我可以选取第二项工作，也可以选取第三项工作，还可以选取第四项工作。

3. 图示
   观察依据

   从节点2出发，教师画出三个子节点，分别标记为$J_2$、$J_3$、$J_4$，并将其编号为6、7、8。

1. 公式

   $$$$
   解释

   取对应于部分序列($J_1$)的节点。

   步骤依据

   这是根节点最左侧的子节点，由边$J_1$标记。

   视频直接表达
2. 公式

   $$$$
   解释

   将每个剩余未使用的工作——即$J_2$、$J_3$和$J_4$——依次追加，从而形成三个子节点。

   步骤依据

   教师明确指出：在选取第一项工作之后，可接着选取工作2、或工作3、或工作4。

   视频直接表达
3. 公式

   $$$$
   解释

   将一条路径（例如 root → $J_1 \to J_4$）理解为部分序列：先执行任务1，再执行任务4，且该路径上不包含任务2和任务3。

   步骤依据

   讲师指出，沿某一条路径行进意味着执行第一项任务和第四项任务，而不执行第二项和第三项任务。

   视频直接表达

节点2展开为所有以 $J_1$ 开头的两任务部分序列。

1. 声音
   观察依据

   接下来我该展开哪个节点？是展开这个，还是这个？那么下一个就是这个。

2. 声音
   观察依据

   我正在执行第二项任务，正在考虑第二项任务。但下一项任务呢？我将执行第三项任务或第四项任务。

3. 声音
   观察依据

   注意，第一项任务我们已经舍弃了，不再考虑它，也不选择它。接下来是第三项任务和第四项任务。而此处仅剩第四项任务。

4. 图示
   观察依据

   讲师将节点3展开为节点9、10、11；将节点4展开为节点12；将节点5展开为节点13；然后继续处理节点14、15、16、17。

1. 某些后续节点编号被快速念出，但黑板上清晰可见的编号支持整体从左到右的前沿扩展顺序。

1. 公式

   $$$$
   解释

   在完成节点2的所有子节点后，转至同一前沿上的下一个未展开节点，即节点3。

   步骤依据

   讲师询问接下来应展开哪个节点，随后转向相邻节点，而非进一步深入节点2的子树。

   视频直接表达
2. 公式

   $$$$
   解释

   通过在节点 3 的路径上追加尚未使用的工作，展开该节点，生成标号为 $J_1$、$J_3$、$J_4$ 的子节点。

   步骤依据

   音频指出，当考虑第二个工作时，接下来的可能选择是第三个工作或第四个工作，而白板上显示节点3下方有三个子节点。

   视频直接表达
3. 公式

   $$$$
   解释

   通过仅追加剩余未使用的作业 $J_4$ 来展开节点 4，因为 $J_1$ 和 $J_2$ 已位于该路径上。

   步骤依据

   讲师说：第一个工作我们已经排除……接着是第三个工作和第四个工作。那么此处只剩第四个工作，与节点4下方唯一的子节点相匹配。

   视频直接表达
4. 公式

   $$$$
   解释

   以类似方式继续遍历其余前沿节点，直至所有已显示节点均达到深度4。

   步骤依据

   最终白板展示了一棵完整的四层排列树，节点编号至17。

   视频直接表达

该树通过从左到右依次展开当前层节点的方式生长，印证了前文所述的广度优先过程。

1. 声音
   观察依据

   我们来看第二种方法……首先生成第一个节点……将这些节点压入栈中……弹出这个节点并进行扩展……

2. 图示
   观察依据

   讲师依次绘制节点1-9，并更新栈示意图，展示压栈和弹栈操作。

1. 公式

   $$$$
   解释

   生成根节点1，并将它的子节点（节点2、3、4、5）压入栈中。

   步骤依据

   在状态空间树中对根节点进行初始扩展。

   视频直接表达
2. 公式

   $$$$
   解释

   从栈中弹出节点5。它代表最后一个作业，因此无法进一步扩展。

   步骤依据

   深度优先搜索优先探索最深层的节点；叶节点没有子节点。

   视频直接表达
3. 公式

   $$$$
   解释

   从栈中弹出节点4，并将其扩展以生成节点6。将节点6压入栈中。

   步骤依据

   节点4表示一个部分序列，可通过添加剩余作业来扩展。

   视频直接表达
4. 公式

   $$$$
   解释

   从栈中弹出节点6。它代表一个完整序列，因此无法扩展。

   步骤依据

   该分支中已考虑全部作业。

   视频直接表达
5. 公式

   $$$$
   解释

   从栈中弹出节点3，并将其扩展以生成节点7和8。将二者均压入栈中。

   步骤依据

   节点3表示一个部分序列，可通过添加剩余作业来扩展。

   视频直接表达
6. 公式

   $$$$
   解释

   从栈中弹出节点8。它代表一个完整序列，因此无法扩展。

   步骤依据

   该分支中已考虑全部作业。

   视频直接表达
7. 公式

   $$$$
   解释

   从栈中弹出节点7，并将其扩展以生成节点9。将节点9压入栈中。

   步骤依据

   节点7表示一个部分序列，可通过添加剩余作业来扩展。

   视频直接表达

基于栈的方法以深度优先的方式成功遍历状态空间树，系统地生成并扩展节点。

1. 声音
   观察依据

   他说节点9无法进一步探索，因此取出2并进行探索。

2. 动画
   观察依据

   他从节点2画出子节点，标记为$J_2$、$J_3$、$J_4$，并依次编号为10、11、12。

3. 声音
   观察依据

   他说节点编号为10、11和12，并按此顺序压入栈中。

1. 公式

   $$$$
   解释

   在所示树中，当前活跃节点9已无法进一步探索，即为终止节点。

   步骤依据

   由讲师直接陈述。

   视频直接表达
2. 公式

   $$$$
   解释

   因此该算法将节点2从栈中移除并展开它。

   步骤依据

   由讲师直接陈述。

   视频直接表达
3. 公式

   $$$$
   解释

   节点2生成三个子节点，分别对应于在第一个工作已固定的前提下，选择第二个、第三个或第四个工作。

   步骤依据

   讲师在绘制分支时陈述。

   视频直接表达
4. 公式

   $$$$
   解释

   这些新节点编号为10、11和12，并按此相同顺序压入栈中。

   步骤依据

   音频中明确陈述，并在黑板上展示。

   视频直接表达

这通过完全展开一个选定节点，并将所有生成的子节点压入栈中，演示了后进先出（LIFO）分支限界法。

1. 声音
   观察依据

   那么我们来展开这个节点。此时已安排作业二。这里对应作业三，这里对应作业四。假设此处代价为八，此处代价为七。那么我们应该探索哪一个？这个节点。但这是第二个作业与第四个作业组成的叶子节点。因此这就是解。

2. 图示
   观察依据

   节点2（$C=12$）被扩展为节点6（J3，$C=8$）和节点7（J4，$C=7$）。节点7被加下划线标记为解。

1. 公式

   $$$$
   解释

   在根节点的初始子节点中，找出代价最小的节点（节点2的$C=12$）。

   步骤依据

   最小代价选择规则

   视频直接表达
2. 公式

   $$$$
   解释

   扩展节点2以生成其子节点：节点6（J3，$C=8$）和节点7（J4，$C=7$）。

   步骤依据

   算法中的分支步骤

   视频直接表达
3. 公式

   $$$$
   解释

   比较新生成节点的代价，并选择其中代价最小者（节点7的$C=7$）。

   步骤依据

   最小代价选择规则

   视频直接表达
4. 公式

   $$$$
   解释

   认识到节点7表示一个完整的序列（J2, J4），因此即为解。

   步骤依据

   代表完整作业序列的叶节点的终止条件

   视频直接表达

该算法通过仅探索基于成本最具有希望的路径，成功找到解。

1. 声音
   观察依据

   请看，我在此处选取了一个简单示例，即带截止时间的作业排序问题。

2. 公式
   观察依据

   作业集合 = {$J_1$, $J_2$, $J_3$, $J_4$}，利润数组 $P = {10, 5, 8, 3}$，截止时间数组 $d = {1, 2, 1, 2}$

表示一个包含4个作业的作业排序问题的解。

1. 任务集 = {$J_1$, $J_2$, $J_3$, $J_4$}

2. P 等于由 10、5、8 和 3 组成的集合

3. d 等于集合 1、2、1、2

演示两种表示解的方法：子集表示法与二进制向量表示法。

1. 公式

   $$S1 = \{J_1, J_4\}$$
   解释

   将解表示为所选任务构成的子集。

   步骤依据

   第一种表示方法。

   视频直接表达
2. 公式

   $$S2 = \{1, 0, 0, 1\}$$
   解释

   将解表示为一个二进制向量，其中 1 表示该任务已执行，0 表示该任务未执行。

   步骤依据

   第二种表示方法。

   视频直接表达

$S1 = {J_1, J_4}$（变长），$S2 = {1, 0, 0, 1}$（定长）

两种表示法均正确指出：任务 1 和 4 被选中，而任务 2 和 3 未被选中。

1. 图示
   观察依据

   白板标题：分支限界法；右侧内容：工作排序问题，其中工作集合 = {$J_1$, $J_2$, $J_3$, $J_4$}，利润 $P = {10, 5, 8, 3}$，截止时间 $d = {1, 2, 1, 2}$，$S1 = {J_1, J_4}$，$S2 = {1, 0, 0, 1}$。

2. 声音
   观察依据

   一旦我选择了第一个工作，那么后续可能的解有哪些？我可以选第二个工作，也可以选第三个工作，然后还可以选第四个工作。

3. 声音
   观察依据

   因此，若我沿其中一条路径行进，它表明我执行的是第一个工作和第四个工作，而不执行第二个和第三个工作。

1. 该片段未计算任何目标函数值、可行性检验或界限值；它仅构建搜索树。

给定四个工作 $J_1$, $J_2$, $J_3$, $J_4$，画出用于通过分支限界法探索工作序列的状态空间树。

1. 任务集合 = {$J_1$, $J_2$, $J_3$, $J_4$}。

2. 黑板上还列出了 $P = {10, 5, 8, 3}$，$d = {1, 2, 1, 2}$，$S1 = {J_1, J_4}$，$S2 = {1, 0, 0, 1}$，但这些在本片段中并未使用。

3. 正在演示的方法是树的广度优先展开。

展示分支定界树中部分任务序列如何逐层生成。

1. 公式

   $$$$
   解释

   从根节点出发，创建四个子节点，分别对应将每个任务作为第一个任务的选择。

   步骤依据

   所有含一个任务的部分序列均置于第一层。

   视频直接表达
2. 公式

   $$$$
   解释

   从节点 ($J_1$) 出发，为其创建子节点：($J_1$,$J_2$)、($J_1$,$J_3$) 和 ($J_1$,$J_4$)。

   步骤依据

   在选取任务 1 后，剩余可选任务为 2、3 和 4。

   视频直接表达
3. 公式

   $$$$
   解释

   接着按从左到右的顺序扩展下一层前沿节点，而非立即深入 ($J_1$,$J_2$) 的子树。

   步骤依据

   讲师明确将分支定界表述为广度优先搜索。

   视频直接表达
4. 公式

   $$$$
   解释

   继续该过程，直至每个已显示路径的长度均达到 4，从而生成黑板上所示的完整排列树。

   步骤依据

   最终图示中的节点编号最大为 17，且所有分支均终止于深度 4。

   视频直接表达

该示例生成了一棵四层的状态空间树，其节点表示四个作业的局部排列，且该树从根节点开始按宽度优先方式展开。

完成后的图板清晰地展示了根节点、四个第一层子节点，以及逐层扩展的结果，最终所有路径长度均为4，这与口头描述的宽度优先探索过程完全一致。

1. 图示
   观察依据

   白板上展示了一个包含4个作业的完整状态空间树，节点编号为1至14。

2. 公式
   观察依据

   作业集合 = {$J_1$, $J_2$, $J_3$, $J_4$}，利润集合 $P = {10, 5, 8, 3}$，截止时间集合 $d = {1, 2, 1, 2}$

构建并解读一个含4个作业的作业排序问题的状态空间树。

1. 作业集合 = {$J_1$, $J_2$, $J_3$, $J_4$}

2. 利润集合 $P = {10, 5, 8, 3}$

3. 截止时间集合 $d = {1, 2, 1, 2}$

理解节点如何表示部分作业序列。

1. 公式

   $$$$
   解释

   画出代表空序列的根节点。

   步骤依据

   状态空间树的起始点。

   视频直接表达
2. 公式

   $$$$
   解释

   分出分支，为每个可能的首个作业（$J_1$, $J_2$, $J_3$, $J_4$）创建子节点。

   步骤依据

   生成树的第一层。

   视频直接表达
3. 公式

   $$$$
   解释

   继续分枝以添加后续作业，为所有可能的排列创建节点。

   步骤依据

   完成状态空间树。

   视频直接表达

所得的树共有14个节点，其中从根节点到每个叶节点的路径都代表4个作业的一种唯一排列。

通过直观检查所绘制的树，可确认所有排列均已表示。

1. 公式
   观察依据

   棋盘右侧标题为‘作业排序’，列出了作业、P、d 和 Si。

2. 动画
   观察依据

   绘制了一棵状态空间树，其根节点为1，已有节点为2至9。

3. 声音
   观察依据

   讲解员口述取出节点2并对其进行探索，然后将节点10、11、12依次压入栈中。

1. 该片段未在此区间内计算该作业序列的目标函数值。

使用栈在作业排序的状态空间树上继续进行分支限界搜索。

1. 作业 = {$J_1$, $J_2$, $J_3$, $J_4$}

2. P 等于由 10、5、8 和 3 组成的集合

3. d 等于集合 1、2、1、2

4. Si = {$J_1$, $J_3$}

5. 一棵已有的树中已包含从1到9的节点。

展开栈中选中的下一个节点，并用其子节点更新栈。

1. 公式

   $$$$
   解释

   节点9被视为不可进一步探索。

   步骤依据

   由教师陈述。

   视频直接表达
2. 公式

   $$$$
   解释

   节点2被从栈中取出以进行探索。

   步骤依据

   由教师陈述。

   视频直接表达
3. 公式

   $$$$
   解释

   从节点2出发，为剩余的工作选择 $J_2$、$J_3$ 和 $J_4$ 分别创建分支。

   步骤依据

   通过所画的边及口头说明展示。

   视频直接表达
4. 公式

   $$$$
   解释

   新节点被标记为10、11和12，并按此顺序压入栈中。

   步骤依据

   明确陈述并写在黑板上。

   视频直接表达

栈接收节点 10、11和12，在扩展节点 2后。

黑板上显示了节点2下方的新子节点以及栈中条目10、11、12。

1. 声音
   观察依据

   他说：‘现在我们来看这种方法——最小代价分支限界法。’

2. 动画
   观察依据

   他擦除旧的树，从根节点1开始构建一棵全新的状态空间树。

3. 公式
   观察依据

   他在根节点旁边写下 $C = \infty$。

4. 声音
   观察依据

   他说明：对每个节点，我们都会计算其代价，并假设该节点的代价为无穷大。

1. 视频片段在第一个子节点的代价被计算出来之前就结束了。

2. 本片段未解释为何将根节点的代价初始化为无穷大。

针对同一作业排序实例，采用最小代价法启动一次新的分支限界搜索。

1. 作业 = {$J_1$, $J_2$, $J_3$, $J_4$}

2. P 等于由 10、5、8 和 3 组成的集合

3. d 等于集合 1、2、1、2

4. 集合 $S_i$ 包含元素 $J_1$ 和 $J_3$

构建一棵新的状态空间树，并从根节点开始为各节点分配代价。

1. 公式

   $$$$
   解释

   教师清空之前的树，并宣布将再次生成一棵树，具体来说是一棵状态空间树。

   步骤依据

   音频中已说明，且在黑板上可见。

   视频直接表达
2. 公式

   $$$$
   解释

   他画出一个新的根节点，标记为1。

   步骤依据

   白板上显示可见的动画效果。

   视频直接表达
3. 公式

   $$$$
   解释

   他引入了一个新概念：每个节点都将具有一个计算得出的成本值。

   步骤依据

   教师直接陈述。

   视频直接表达
4. 公式

   $$C = \infty$$
   解释

   他将根节点的成本设为无穷大。

   步骤依据

   写在黑板上并口头说出。

   视频直接表达
5. 公式

   $$$$
   解释

   他开始考虑从根节点出发进行分支所对应的作业。

   步骤依据

   在视频片段最后几秒中说明。

   视频直接表达

LC-BB 示例以根节点1和成本 $C = \infty$ 初始化。

黑板在视频片段结束前已显示带有 $C = \infty$ 的新根节点。

1. 图示
   观察依据

   白板展示一棵树结构，节点标记为J1、J2、J3、J4，对应成本为$C=25$、$C=12$、$C=19$、$C=30$、$C=8$、$C=7$。

给定一组具有收益和截止时间的作业，使用最小成本分支限界法求出最优作业序列。

1. 作业集合 = {J1, J2, J3, J4}

2. 收益集合 $P = {10, 5, 8, 3}$

3. 截止时间集合 $d = {1, 2, 1, 2}$

4. 可行解 Si = {J1, J3}

根据问题约束，确定使总成本最小化或收益最大化的作业序列。

1. 公式

   $$$$
   解释

   以无穷大成本（$C = \infty$）初始化根节点。

   步骤依据

   分支限界法中最小化问题的标准初始化

   视频直接表达
2. 公式

   $$$$
   解释

   生成第一层子节点，分别表示包含各任务（J1、J2、J3、J4），并赋予任意成本（$C=25$、$C=12$、$C=19$、$C=30$）

   步骤依据

   分支步骤：探索不同的任务排列顺序

   视频直接表达
3. 公式

   $$$$
   解释

   选择成本最小的节点（节点2，$C=12$）进行扩展

   步骤依据

   最小成本分支限界选择规则

   视频直接表达
4. 公式

   $$$$
   解释

   展开节点 2 以生成其子节点（节点 6 对应 J3，其中 $C=8$，节点 7 对应 J4，其中 $C=7$）。

   步骤依据

   分支步骤：继续探索以J2开头的任务序列

   视频直接表达
5. 公式

   $$$$
   解释

   在新生成的子节点中，选择成本最小的节点（节点7，$C=7$）

   步骤依据

   最小成本分支限界选择规则

   视频直接表达
6. 公式

   $$$$
   解释

   确认节点7代表一个完整序列（J2、J4），并将其确定为解

   步骤依据

   达到终止条件

   视频直接表达

找到的最优序列为J2后接J4，最终成本为7

通过追踪从根节点到所选叶节点的路径来验证解的正确性，确保所有分支规则和选择规则均被严格遵守。

1. 图示
   观察依据

   白板显示标题‘分支限界法’及‘任务排序’问题的数据。

1. 标题“分支定界法”

2. 问题标题“作业排序”

3. 数据集：作业集合、P、d

1. 问题数据在整个片段中持续可见

为本讲——将分支定界法应用于作业排序——设定背景。

1. 动画
   观察依据

   教师画一个圆圈（根节点），并从该圆圈向左下方引出一条线，标注为“J1”。

1. 根节点（圆圈）

2. 左分支标注为“J1”

1. 在黑板左侧绘制一个新的树形结构。

1. 黑板右侧已有的问题数据保持不变。

用子集法直观展示状态空间树生成的起始过程。

1. 图示
   观察依据

   初始时刻，图板上已显示标题“分支限界法”，一个包含根节点1及一条标有$J_1$的边指向节点2的小型初始树片段，以及右侧的作业排序数据。

1. 标题：分支限界法

2. 根节点1

3. 边标签：$J_1$

4. 节点2

5. 右侧列表：Jobs（作业）、P（利润）、d（截止时间）、S1、S2

1. 教师站在图板旁，开始讲解该方法与回溯法的区别。

1. 右侧的作业数据在整个视频片段中始终可见。

该视频片段以一个部分准备好的示例开场，随后实时构建出完整的状态空间树。

1. 动画
   观察依据

   教师从节点1出发，再画出三条边，分别标记为$J_2$、$J_3$、$J_4$，并添加节点3、4、5。

1. 节点1

2. 边$J_1$、$J_2$、$J_3$、$J_4$

3. 节点2、3、4、5

1. 节点1新增了三个子节点。

2. 第一层变为包含全部四种单任务选择的完整集合。

1. 根节点仍表示空的部分序列。

2. 右侧的任务列表保持不变。

这一可视化步骤印证了分支定界法会在当前层级考虑所有直接备选方案这一论断。

1. 动画
   观察依据

   从节点2出发，教师画出三条向下的边，分别标记为$J_2$、$J_3$、$J_4$，并将新节点编号为6、7、8。

1. 节点2

2. 边 $J_2$、$J_3$、$J_4$

3. 节点6、7、8

1. 在节点2下方新增三个第二层节点。

1. 通往每个新节点的路径均以 $J_1$ 开始。

2. 未添加任何剪枝或界标记。

当前棋盘展示了所有以作业1开头的两作业部分序列。

1. 动画
   观察依据

   教师接下来将节点3展开为节点9、10、11，再将节点4展开为节点12，接着将节点5展开为节点13，并持续添加更深层的节点，直至节点17。

1. 部分靠后节点的口头编号不如棋盘上可见标签清晰。

1. 节点3、4、5

2. 它们的子节点为9-13

3. 后续后代14-17

1. 扩展沿当前前沿从左至右进行。

2. 树逐层加深，直至所有分支均达到长度4。

1. 每条边添加一个此前未使用过的工作。

2. 整体策略始终采用广度优先而非深度优先。

这一可视化过程展示了先前用语言描述的‘回溯法’与‘分枝定界法’之间对比的操作含义。

1. 图示
   观察依据

   左侧白板上可见一幅预先绘制好的状态空间树。

1. 带有节点1-14的状态空间树

2. 边标签 $J_1-J_4$

1. 讲师指向不同节点以解释其含义。

1. 本片段中，树的结构保持不变。

该树直观地表示了作业排序问题的整个解空间。

1. 图示
   观察依据

   教师绘制一个竖直的矩形（栈），并在其中写入或弹出数字，同时绘制新的树节点。

1. 栈示意图

2. 新绘制的树节点（1-9）

1. 数字被写入栈中（压栈操作）。

2. 数字从栈顶被擦除（弹栈操作）。

3. 新节点绘制在树中已有节点的下方。

1. 栈始终遵循后进先出的原则运作。

树节点绘制与栈更新的视觉同步，直观展示了使用显式栈进行深度优先遍历的机制。

1. 图示
   观察依据

   黑板左侧预先绘制了一棵名为“分支定界”的树，右侧为一个作业排序数据块，其下方为一个垂直堆栈。

2. 动画
   观察依据

   教师先指向节点9，再移至节点2并画出三条向外的分支。

1. 树中节点1至节点9

2. 节点2

3. 节点9

4. 垂直堆栈示意图

5. 作业排序数据块

1. 注意力从节点9转移到节点2。

2. 在节点2下方新增了三个子节点。

3. 堆栈被更新为包含10、11、12。

1. 右侧底层的作业排序数据保持不变。

2. 树的先前部分保持可见，同时添加新的子节点。

可视化序列展示了基于栈的分支限界搜索如何从死胡同节点回溯，并扩展下一个可用节点。

1. 公式
   观察依据

   教师在黑板上写下：队列 → 先进先出，栈 → 后进先出，最小代价 → LC-BB。

2. 图示
   观察依据

   黑板上出现编号列表：1. FIFO-BB，2. LIFO-BB，3. LC-BB。

1. 队列 → 先进先出

2. 栈 → 后进先出

3. 最小代价 → LC-BB

4. 方法编号列表

1. 新文本被添加到树的下方。

2. 方法列表以 LC-BB 补充完成。

1. 作业排序数据块保留在右侧。

2. 先前的树会一直保持可见，直到后续被擦除。

该可视化概览根据所用数据结构对搜索策略进行分类，该数据结构用于选择下一个节点。

1. 动画
   观察依据

   先前的树和栈被擦除。

2. 公式
   观察依据

   主标题下方写有‘Least Cost - BB’。

3. 动画
   观察依据

   绘制一个新的根节点1，其旁标注 $C = \infty$。

1. 主标题：分支限界法

2. 副标题：最小代价—分支限界法

3. 新根节点1

4. 代价标签 $C = \infty$

1. 旧的状态空间树和栈消失。

2. 添加一个关于最小代价—分支限界法的新标题。

3. 创建一个全新的根节点，并为其分配一个代价。

1. 右侧的作业调度数据保持可见。

2. 编号的方法列表保持可见。

重置操作标志着讲解重点从 FIFO/LIFO 节点选择方式，转向从零开始演示基于代价的分支限界法。

1. 动画
   观察依据

   讲师在白板上绘制一棵树结构，按顺序添加节点和边，并用工作标识符及成本值对它们进行标注。

1. 根节点

2. 子节点（J1、J2、J3、J4）

3. 孙节点（J3、J4）

4. 连接节点的边

5. 成本标签（C=…）

1. 随着算法执行分支操作，节点被逐个添加到树中。

2. 为每个节点分配对应的成本值。

3. 讲师指向特定节点以讲解选择过程。

1. 该树的层次结构始终保持一致。

2. 黑板右侧始终显示问题参数（作业数、P、d、Si）以及方法列表（FIFO、LIFO、LC）。

树的可视化构建展示了分支限界算法如何通过生成和评估作业的部分排列序列，系统性地探索解空间。

1. 声音
   观察依据

   我们不按深度方向进行，不采用深度优先搜索，而是采用广度优先搜索来探索问题的解。

人们可能误以为分枝定界法与回溯法类似，会立即沿着某一分支向下深入至下一层。

在本片段中，讲师明确指出：此处分枝定界法并不按深度方向进行；它采用广度优先方式遍历树结构，即先考察当前层的所有选择，再向更深层推进。

1. 声音
   观察依据

   因此，若我遵循其中一条路径，它表示我执行第一项工作和第四项工作，而不执行第二项和第三项工作，这就是其含义。

像 $J_1$ 然后 $J_4$ 这样的路径，可能被误认为意味着所有工作都已被处理。

讲师澄清：沿该路径行进，表示在该部分路径上执行工作 1 和工作 4，而工作 2 与工作 3 在该路径上并未被选取。

1. 声音
   观察依据

   在指出栈实现的是后进先出（LIFO）分支限界法后，讲师立即补充强调：你必须仅采用广度优先搜索。

2. 声音
   观察依据

   他定义道：一旦选中某个节点，就必须先探索从该节点出发的所有可能子节点，然后才能选择下一个节点。

1. 该片段在分支限界法语境中使用了“广度优先搜索”这一术语，但并未正式将其与深度优先搜索进行对比。

人们可能会推断：后进先出（LIFO）分支限界法是指在选中一个子节点后立即向下继续选择其子节点。

在本讲段中，讲师明确指出：即使使用栈，也必须先生成所选节点的所有可能子节点，然后才能选择下一个节点。

1. 声音
   观察依据

   这与回溯法类似，因为两者都使用状态空间树来求解问题。

分支限界法与回溯法类似，二者均使用状态空间树，但分支限界法专用于优化（最小化）问题。

1. 声音
   观察依据

   因此，回溯法与分支限界法的区别在于：回溯法采用深度优先搜索，而分支限界法采用广度优先搜索。

该片段使用同一棵作业排序树，来对比回溯法的深度优先遍历与分支限界法的广度优先遍历。

1. 声音
   观察依据

   现在这一层已全部完成。请看，我已逐一考虑了所有工作。

2. 动画
   观察依据

   讲师从左到右依次扩展前沿上的节点。

该树的逐步构建，正是所陈述的广度优先扩展规则的具体应用。

1. 声音
   观察依据

   因此，若我沿其中一条路径行进，就表示我执行的是第一项工作和第四项工作，而不执行第二项和第三项工作。

路径编码部分作业序列这一语义规则，是所展示的状态空间树定义的一部分。

1. 声音
   观察依据

   弹出这个节点并展开……再弹出下一个节点并探索它

2. 图示
   观察依据

   栈操作决定了树节点被展开的顺序。

基于栈的方法被用于遍历状态空间树，实现深度优先搜索策略。

1. 公式
   观察依据

   黑板上将「队列 → 先进先出（FIFO）」与「栈 → 后进先出（LIFO）」上下并列书写。

2. 声音
   观察依据

   讲师提问：此前的方法与此方法有何不同？随后通过对比队列与栈来作答。

FIFO-BB 与 LIFO-BB 的区别在于：下一个节点是从队列中取出，还是从栈中取出。

1. 公式
   观察依据

   最小代价法 → LC-BB 作为第三种方法，添加在 FIFO-BB 和 LIFO-BB 之后。

2. 声音
   观察依据

   教师指出还有一种方法，接着说明每个节点都将拥有一个代价。

1. 该片段引入了 LC-BB，但在结束前并未完整展开其节点选择规则。

LC-BB 被呈现为一种额外的分支限界变体，它通过引入节点代价来增强搜索过程，从而将讨论拓展至纯粹的 FIFO/LIFO 节点选取之外。

1. 声音
   观察依据

   教师在讲解最小代价分支限界法时，引入了代价计算。

2. 公式
   观察依据

   他在新的 LC-BB 树的根节点处写下 C = 〔$\infty$〕。

LC-BB 的演示依赖于首先定义节点代价及一个与问题相关的代价函数。

1. 声音
   观察依据

   教师说你可以任选其一，但必须仅遵循广度优先搜索。

所陈述的扩展规则适用于本片段中讨论的 FIFO 方法。

1. 声音
   观察依据

   相同的广度优先扩展说明紧随 LIFO 定义之后直接出现。

所陈述的扩展规则同样适用于本片段中讨论的 LIFO 方法。

1. 声音
   观察依据

   现在我们再回顾一下：FIFO 方法中，我们选择待探索的这个节点进行扩展；LIFO 方法中，我们尝试扩展这个节点；而在最小成本法中，我们从这些节点中选出成本最小的那个进行尝试。

最小成本策略与 FIFO 和 LIFO 形成对比，它依据节点的评估成本而非生成顺序来选择节点。

1. 声音
   观察依据

   这就是 LC 分支限界的思想，它比使用 FIFO 和 LIFO 快得多。

应用最小成本选择规则，可获得避免生成整棵树、更快到达解的效率优势。

1. 声音
   观察依据

   本节主题是分支限界法……适用于求解优化问题，且仅适用于最小化问题。

1. 分支限界法定义

1. 声音
   观察依据

   解可表示为子集……第二种方法……固定大小的解。

2. 公式
   观察依据

   $S1 = {J_1, J_4}$, S2 = {1，0，0，}1}

1. 可变大小解（子集法）
2. 固定规模解（二进制向量法）

1. 声音
   观察依据

   我们不采用深度优先搜索，而是采用广度优先搜索来探索问题的解。

1. 分支限界法采用广度优先扩展，而回溯法则不然。
2. 作业排序树上的广度优先扩展规则

1. 声音
   观察依据

   因此，回溯法与分支限界法的区别在于：回溯法采用深度优先搜索，而分支限界法采用广度优先搜索。

1. 分支限界法采用广度优先扩展，而回溯法则不然。
2. 回溯法是深度优先搜索，分支限界法是广度优先搜索

1. 声音
   观察依据

   因此，如果我沿着其中一条路径走，就表示我选择了第一项工作和第四项工作，而没有选择第二项和第三项工作。

1. 从根节点到某一节点的路径编码了一个部分工作序列。
2. 含四个作业的作业排序状态空间树

1. 声音
   观察依据

   现在这一层已构建完成。请看，我已经逐个考虑了所有工作。

2. 动画
   观察依据

   节点按从左到右的顺序在前沿面上展开。

1. 作业排序树上的广度优先扩展规则
2. 继续在前沿上进行广度优先扩展。

1. 图示
   观察依据

   黑板上列出了 P、d、S1 和 S2，但本片段的口头讲解仅聚焦于树的构建。

1. 该片段未解释这些量。

1. 含四个作业的作业排序状态空间树

1. 声音
   观察依据

   我将把这些节点压入栈中……弹出这个节点并展开

1. 基于栈的深度优先遍历
2. 作业排序问题的状态空间树

1. 公式
   观察依据

   队列 → 先进先出（FIFO）写在黑板上。

2. 声音
   观察依据

   教师命名该分支限界法为先进先出（FIFO）分支限界法。

1. 先进先出分支限界法

1. 公式
   观察依据

   栈 → 后进先出（LIFO）写在黑板上。

2. 声音
   观察依据

   教师命名该分支限界法为后进先出（LIFO）分支限界法。

1. LIFO分支限界法
2. 先进先出分支限界法

1. 声音
   观察依据

   教师指出：一旦选取一个节点，就应探索其所有可能的子节点，之后才选择下一个节点。

1. 本分支限界法场景中的广度优先扩展规则
2. LIFO分支限界法

1. 公式
   观察依据

   最小代价 → LC-BB 与 最小代价 - BB 写在黑板上。

2. 声音
   观察依据

   教师介绍最小代价分支限界法。

1. 最小代价分支限界法（LC-BB）