数学建模 / 英语

用分支定界法解指派问题

Lets Try · YouTube · 10:31

YouTube · Lets Try原视频

选中时刻 · 5:45 · 章节点是时间参考，不表示实时播放进度。

视频中的要点

01指派问题的目标函数
02以分支定界法作为求解方法
03下界思想

来自学习笔记

\begin{pmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 8 \\ 7 & 6 & 2 & 4 \end{pmatrix}

$4\times 4$ 成本矩阵示例

选中时刻

选择最具潜力的分支并扩展搜索树

建议预备知识

费用表或费用矩阵的基本概念
基础的最小化表述
熟悉人员与任务的匹配问题
指派问题的建模
成本矩阵的含义
基础的分枝定界搜索树
最小化问题的下界
对矩阵的理解
对优化问题的基本认识
对树形数据结构的熟悉
线性代数（矩阵）
离散数学（图论／树）
优化概念
指派问题基础
最小化问题的界：下界与上界
部分指派的搜索树表示

阅读与收藏

把讲解展开来看。

被收藏 0

已审核学习内容 · 视频分析 · 中文

阅读完整概览

这段 631 秒的白板视频用分支定界法求解四人、四项工作的指派问题。原始成本矩阵各行最小值为 2、3、1、2，因此根节点有效下界为 8。按人员 a 分支后，下界依次为 18、12、20、17；在 $a=2$ 下， $b=1$ 、3、4 的下界分别为 13、14、15。 $a=2$ 、 $b=1$ 的两个叶节点成本为 13 和 18。因此 $a=2$ 、 $b=1$ 、 $c=3$ 、 $d=4$ 是最优指派，总成本 13。早期自动笔记曾把 c 到工作 4 的成本误读为 3；原片实际写的是 8。

在学习检查器中查看要点和时刻，或切换阅读标签查看完整笔记。

章节

0:00主题引入：指派问题与分支限界法 0:10指派问题所要求解的内容 0:44下界的含义 1:03带人员与工作标注的成本矩阵示例 1:46基于各行最小值计算下界 LB 2:30根节点与第二层分支 3:20子节点下界规则 3:38当

a = 1

时计算出的下界 4:25当

a = 2

时计算出的下界 4:52当

a = 3

时下界的起始计算 5:00指派问题的分支定界法简介 5:15初始分支下界的计算 5:45选择最具潜力的分支并扩展搜索树 6:30第二层分支下界的计算 7:30问题建模与初始下界 7:48探索人员 b 的各分支 8:04选择下一个节点并评估叶节点 9:45结论：最优指派方案 10:00可行的叶节点指派与上界 10:08将LB = 8与UB = 13合并为最优成本范围 10:21总结：分支定界法求解指派问题

学习解说文稿

依据视频画面与讲解整理，并非逐字语音转写。

片段以手写标题页开场，页面上写着‘指派问题’与‘分支限界法’。主讲人将本课定位为演示如何运用分支限界法求解指派问题。

讲述者用自然语言解释问题背景：存在若干人员与若干工作，每名人员应被分配一项工作，目标是选择一组指派方案，使得总成本尽可能小。此说明在展示任何矩阵之前即确立了优化目标。

接下来引入的概念是下界。主讲人非正式地将其描述为一个与最小可能成本相关联的数值，表明分支限界法将首先估算总指派成本的下限，而非立即枚举所有可能的指派方案。

一个具体的 $4\times 4$ 成本矩阵出现。行标签为 a、b、c、d，代表人员；列标签为1、2、3、4，代表工作。矩阵中的各项表示各人员-工作组合的成本，因此该示例将抽象的指派问题转化为一张表格，最终需从每行每列中各选出一个元素。

在进行算术运算之前，讲解者指出了该方法的下一阶段：在找到初始下界后，搜索将继续遍历一个状态空间树。该树在此片段中被提及，但并未实际构建。

随后直接在矩阵上执行下界计算。对每一行，选取其中最小的元素：第a行贡献2，第b行贡献3，第c行贡献1，第d行贡献2。

这四个最小值在带方框的行中相加：LB = $2 + 3 + 1 + 2 = 8$ 。圆圈标出的8被作为本例的初始下界，为分支开始前的总成本提供了一个数值下限。

黑板上展示了一个用分枝限界法求解的指派问题。一个 $4\times 4$ 的成本矩阵被写出，其中行代表人员 a、b、c、d，列代表工作 1、2、3、4。其下方，搜索树的根节点标记为 $LB = 2+3+1+2 = 8$ 。

讲解者现在通过对人员 a 所分配的工作进行分枝，构建状态空间树的第二层。画出了四个子节点，并标记为 $a=1$ 、 $a=2$ 、 $a=3$ 和 $a=4$ 。

对每个子节点，任务是估算在该分配已固定的前提下，完成整个指派可能的最低总成本。视频中采用的规则是：加上人员 a 的固定成本，然后对每一个剩余工作，在尚未分配人员的那些行中，取该列的最小值。

对于分枝 $a=1$ ，固定成本即矩阵中第 a 行、第 1 列的元素，也就是 $9$ 。由于第 a 行已被使用，剩余各列的最小值仅从第 b、c、d 行中选取。

在第 2 列中，第 b、c、d 行的元素为 $4,8,6$ ，因此最小值为 $4$ ；在第 3 列中，第 b、c、d 行的元素为 $3,1,2$ ，因此最小值为 $1$ ；在第 4 列中，第 b、c、d 行的元素为 $7,8,4$ ，因此最小值为 $4$ 。

将这些贡献相加，得到该子节点的下界 $9+4+1+4=18$ ，并将其写在节点 $a=1$ 的下方。

对于分枝 $a=2$ ，固定成本即第 a 行、第 2 列的元素，也就是 $2$ 。同样地，在为其余各列选取最小值时，第 a 行被排除。

在第 1 列中，第 b、c、d 行的元素为 $6,5,7$ ，因此最小值为 $5$ ；在第 3 列中，第 b、c、d 行的最小值为 $1$ ；在第 4 列中，第 b、c、d 行的最小值为 $4$ 。

因此，节点 $a=2$ 的下界为 $2+5+1+4=12$ ，该值写在对应分支下方。

主讲人随后表示，将对 $a=3$ 和 $a=4$ 重复执行相同步骤，并从 $a=3$ 情形开始，指出其固定成本为 $7$ ；但视频片段在此计算完成前结束。

视频首先计算人员‘a’被指派至工作‘3’这一分支的下界。其固定成本为7。在排除‘a’所在行后，其余各列（1、2和4）中对应未分配行的最小成本分别为5、4和4。将这些数值相加，得到下界： $7 + 5 + 4 + 4 = 20$ 。

接着计算分支‘ $a=4$ ’的下界。其固定成本为8。在排除‘a’所在行后，其余各列（1、2和3）中对应未分配行的最小成本分别为5、4和1。总下界为： $8 + 5 + 4 + 1 = 17$ 。

比较全部四个初始分支（18、12、20、17）的下界后，算法选出最具潜力的一个，即‘ $a=2$ ’，其下界为12。这意味着人员‘a’暂被指派至工作‘2’。

随后，搜索树从节点‘ $a=2$ ’继续扩展。下一层分支将考虑人员‘b’的指派；由于工作‘2’已被‘a’占据，因此‘b’只能被指派至工作‘1’、‘3’或‘4’。由此生成三条新分支。

为计算新分支的下界，需将人员‘a’所在行与工作‘2’所在列从后续考虑中剔除。视频通过指向成本矩阵中相应部分来演示这一过程。

在 $a=2$ 、 $b=1$ 下，固定成本为 2 和 6；剩余工作 3、4 在 c、d 两行中的最小成本分别为 1 和 4。原片写出的下界 $2+6+1+4=13$ 是正确的。

视频开始计算分支‘ $b=3$ ’（位于‘ $a=2$ ’之下）的下界。该指派的固定成本为3。随后，它在第一列中寻找最小值，得到5。但该计算在完成前即被中断。

视频开头评估分支定界树中的一个节点，其中人员‘a’被指派承担工作‘2’。主讲人计算下界，并口述：‘第二个是二，加上第四项的最小值四’，得出结果为14。然而，黑板上该节点（标注为 $b=3$ ）所写的计算式为‘ $3+5+2+4=14$ ’，其数值与口述内容或矩阵原始值均不完全吻合。

接下来，讲话者评估将人员“b”分配给工作“4”的分支（在主分支 $a=2$ 下）。他们将 $b\to 4$ 的成本（即 7）与人员 c 和 d 剩余各列的最小值相加：5 对应工作 1，2 对应工作 3，以及 1 对应工作 3（等等，工作 3 最小值是 1，任务 1 最小值是 5）。说话者说‘七加最小值……等于五……二……一’，得出 15。黑板上显示‘ $7+5+2+1=15$ ’。

算法随后选择最有希望的分支。比较节点“ $a=2$ ”的子节点的下界（分别为13、14和15），说话者选取下界最小的节点13，该节点对应赋值“ $b=1$ ”。这意味着人员“a”承担工作“2”，人员“b”承担工作“1”。

在人员“a”和“b”均已分配后，仅剩人员“c”和“d”可分配至工作“3”和“4”。说话者识别出两种可能的完整赋值（树中的叶节点）：要么c承担工作3且d承担工作4，要么c承担工作4且d承担工作3。

说话者计算第一个叶节点的总成本： $a\to 2$ （成本2）， $b\to 1$ （成本6）， $c\to 3$ （成本1）， $d\to 4$ （成本4）。将这些相加得 $2 + 6 + 1 + 4 = 13$ 。该结果与黑板上所写的计算一致。

第二个叶节点指派为 $a=2$ 、 $b=1$ 、 $c=4$ 、 $d=3$ 。原始矩阵中 c 到工作 4 的成本是 8，因此 $2+6+8+2=18$ ，与白板一致。

两个叶节点成本为 13 和 18。其余竞争分支的下界都高于 13，因此 $a=2$ 、 $b=1$ 、 $c=3$ 、 $d=4$ 是全局最优指派，成本为 13。

本视频聚焦于一个手写的分支定界树，用于求解含变量a、b、c、d的指派问题。在被高亮的叶节点处，完整指派为 $a=2$ , $b=1$ , $c=3$ , $d=4$ 。该方框下方写出总成本为 $2+6+1+4=13$ ，数字13被标记为UB，表示一个上界。

随后，主讲人将这一可行成本与树顶已标出的根节点下界LB = $2+3+1+2 = 8$ 关联起来。基于这两个已展示的数值，讲解得出结论：最优指派成本必介于8与13之间。

该区间是例题演算得出的结果：下界给出了8这一下限，而可行的赋值方案则提供了13这一上限。旁白将此描述为给出了本页问题实例的最优解范围及最优成本信息。

片段最后总结了该方法本身：通过分枝定界法求解指派问题，借助部分赋值构成的搜索树、各节点的成本总和，以及上下界的比较来实现。本片段中未显示完整的成本矩阵，因此页面上所展示的算术运算即为当前可得的直接依据。

知识卡片

指派问题的目标函数

视频将指派问题定义为：将人员与工作一一匹配，使得每个人恰好被分配一项工作，且总成本最小。这正是分支定界法所要优化的目标。

以分支定界法作为求解方法

分支定界法被引入为求解指派问题的方法。在此片段中，强调的第一步是在探索状态空间树之前，先计算一个初始下界。

下界思想

下界被非正式地描述为与可能的最低成本相关联的一个值。它作为一个初始估计值，用于指导分支定界法的搜索过程。

$4\times 4$ 成本矩阵示例

该例题涉及四个人（行a、b、c、d）和四项工作（列1、2、3、4）。矩阵中每个元素表示将对应人员分配至对应工作的成本。

\begin{pmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 8 \\ 7 & 6 & 2 & 4 \end{pmatrix}

基于各行最小值的初始下界

为计算本课的起始下界，取每行的最小元素并求和。对于所显示的矩阵，各行的最小值分别为2、3、1和2。

LB = 2 + 3 + 1 + 2 = 8

接下来是状态空间树

求得下界后，讲解者指出剩余的分支限界过程将通过状态空间树进行。本片段中并未展示该树本身。

注意：该下界尚不能证明为最优解

口述内容可能使8听起来像是最终的最优费用，但本片段仅演示了初始下界计算，此处并未完成完整的分支验证。

指派问题的分枝定界法设置

该例使用一个 $4\times 4$ 的成本矩阵，人员为a、b、c、d，工作为1、2、3、4。状态空间树的根节点携带下界 $LB = 2+3+1+2 = 8$ 。下一步是对人员a的指派进行分枝。

状态空间树的第二层

对人员a进行分枝，产生四个子节点，分别对应四种可能的工作： $a=1$ 、 $a=2$ 、 $a=3$ 和 $a=4$ 。这些节点代表已固定该指派的子问题。

a=1,\ a=2,\ a=3,\ a=4

如何计算子节点的下界

在子节点处，首先取已固定指派的成本；然后，对每个剩余工作，在未指派人员所对应的行中取最小成本；将这些项相加，即得该节点的下界。

分支 $a = 1$ 的下界

当 a 指派至 $a=1$ 时，固定成本为 $9$ 。排除第 a 行后，列2、3和4中的最小值分别为 $4$ 、 $1$ 和 $4$ 。因此下界为 $9+4+1+4=18$ 。

9+4+1+4=18

为何要排除已指派的行

一旦人员a已被指派给某项工作，则该人员在后续指派中不可重复使用。因此，其余各列的最小值只能从尚未指派的行中选取，而不能包含第a行。

分支 a 的下界 = 2

在 $a=2$ 条件下，固定成本为 $2$ 。排除第 a 行后，列 1、3 和 4 中的最小值分别为 $5$ 、 $1$ 和 $4$ 。因此下界为 $2+5+1+4=12$ 。

2+5+1+4=12

分支定界法

一种系统性算法，用于求解指派问题等优化问题。该方法通过将问题划分为更小的子问题（分支），并为每个子问题估算可能的最优解（定界），从而剪除搜索树中无希望的路径。

下界计算

在指派问题中，一个部分指派的下界等于已确定指派的成本之和，加上在每一未指派列中、仅考虑未指派人所在行的剩余最小成本之和。

LB = \sum_{\text{fixed } i} C_{i, j_i} + \sum_{\text{unassigned } k} \min_{j \in \text{available}} C_{k, j}

搜索树扩展

在分支定界树中生成新节点的过程。在选出最有希望的节点（即下界最小的节点）后，通过将下一个未指派人分配给每一个尚空闲的工作，来创建新的子节点。

常见误区：下界计算错误

一个常见错误是将固定成本与各列全局最小值相加，而非将固定成本与受限列最小值（即排除已指派行后的列最小值）相加。务必确保所取最小值仅来自仍可供指派的行与列。

指派问题成本矩阵

该问题涉及将4项工作分配给4名人员（a、b、c、d），以使总成本最小。各项成本以一个 $4\times 4$ 矩阵给出，其中行代表人员，列代表工作。

\begin{bmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 3 \\ 7 & 6 & 2 & 4 \end{bmatrix}

分支定界法

一种系统化求解优化问题的方法。它遍历状态空间树，并为部分赋值计算“下界”（LB）。若某分支的下界高于当前已知最优解，则剪除该分支。

下界计算

在树中任一节点处，下界等于已确定赋值的成本之和，加上剩余未分配工作所能产生的最小可能成本（仅考虑尚可分配的人员）。

LB = \sum C_{fixed} + \sum \min(C_{remaining\_jobs})

最优解识别

叶节点 $a=2$ 、 $b=1$ 、 $c=3$ 、 $d=4$ 的成本为 $2+6+1+4=13$ ；同一分支的另一个叶节点成本为 $2+6+8+2=18$ 。其他分支下界高于 13，故前者最优。

指派问题的分枝定界树

该页面展示了一棵关于四个变量 a、b、c、d 的赋值搜索树。每一分支固定一个变量，各节点标有手写的成本总和。该方法通过将这些总和与上下界进行比较，逐步缩小最优赋值的范围。

根节点下界 LB = 8

在树的顶端，下界被明确写出为 LB = $2 + 3 + 1 + 2 = 8$ 。在口述总结中，8被认定为指派成本的下界。

LB = 2 + 3 + 1 + 2 = 8

给出上界 UB = 13的可行赋值

树的一个叶节点给出了完整赋值： $a = 2$ ， $b = 1$ ， $c = 3$ ， $d = 4$ 。其总成本计算为 $2 + 6 + 1 + 4 = 13$ ，该值被标记为 UB，即最优值的一个上界。

a=2,\ b=1,\ c=3,\ d=4,\quad 2+6+1+4=13\ (UB)

详细学习笔记

按知识点查看条件、步骤和证据。补充解释与视频直接内容分别标明。

符号定义 · 23

LB

依据清楚

视频直接表达

来源依据

公式
观察依据
主讲人写出方框中的表达式：LB = $2 + 3 + 1 + 2 = 8$ 。
声音
观察依据
说话人指出，这给出了下界值，即八。

符号

含义

给定成本矩阵的总分配成本的下界。

适用范围

示例中由各行最小值导出的非负整数成本值。

a, b, c, d

依据清楚

视频直接表达

来源依据

图示
观察依据
一个 $4\times 4$ 表格，左侧有行标签 a、b、c、d。
声音
观察依据
说话人指出这些代表人员。

符号

a, b, c, d

含义

表示分配示例中四名人员的行标签。

适用范围

四名人员的集合。

1, 2, 3, 4

依据清楚

视频直接表达

来源依据

图示
观察依据
同一个 $4\times 4$ 表格，顶部有列标签1、2、3、4。
声音
观察依据
说话人指出这些代表工作。

符号

1, 2, 3, 4

含义

表示分配示例中四项工作的列标签。

适用范围

四项工作的集合。

cost matrix

依据清楚

视频直接表达

来源依据

图示
观察依据
可见的矩阵元素为：第a行：9、2、7、8；第b行：6、4、3、7；第c行：5、8、1、8；第d行：7、6、2、4。
声音
观察依据
主讲人称其为成本矩阵。

符号

cost matrix

含义

一个4行4列的表格，其中第i行第j列的元素表示将第i个人分配给第j项工作的成本。

适用范围

一个以人员和工作为索引的有限整数值矩阵。

Cost matrix entries

依据清楚

视频直接表达

来源依据

图示
观察依据
一个 $4\times 4$ 的手写成本矩阵，其行标记为a、b、c、d，列标记为1、2、3、4。
声音
观察依据
主讲人将各行称为人员，各列称为工作。

符号

Cost matrix entries

含义

人员a、b、c、d与工作1、2、3、4之间的指派成本。

适用范围

表格中显示的正整数。

LB

依据清楚

视频直接表达

来源依据

公式
观察依据
根节点写作LB = $2+3+1+2 = 8$ 。
声音
观察依据
主讲人在构建状态空间树时讨论下界。

符号

含义

分支限界搜索树中某节点的下界。

适用范围

用于最小化问题的整数值下界。

$a = j$

依据清楚

视频直接表达

来源依据

公式
观察依据
子节点写作 $a = 1$ 、 $a = 2$ 、 $a = 3$ 、 $a = 4$ 。
声音
观察依据
主讲人表示将选取A行，即第一个人，并为A等于1、2、3和4分别建立四个分支。

符号

$a = j$

含义

分支标签表明人员a被指派给工作j。

适用范围

j 属于集合 {1,2,3,4}。

a

依据清楚

视频直接表达

来源依据

图示
观察依据
成本矩阵的行标签为 a、b、c、d。
声音
观察依据
说话人提到将人员 A 分配至工作2。

符号

含义

指指派问题中的人员 a（或 A）。

适用范围

人员集合 {a, b, c, d}。

b

依据清楚

视频直接表达

来源依据

图示
观察依据
成本矩阵的行标签为 a、b、c、d。
声音
观察依据
说话人讨论为人员 b、c 和 d 寻找指派方案。

符号

含义

指派问题中的人员 b。

适用范围

人员集合 {a, b, c, d}。

c

依据清楚

视频直接表达

来源依据

图示
观察依据
成本矩阵的行标签为 a、b、c、d。
声音
观察依据
说话人讨论为人员 b、c 和 d 寻找指派方案。

符号

含义

指派问题中的人员 c。

适用范围

人员集合 {a, b, c, d}。

d

依据清楚

视频直接表达

来源依据

图示
观察依据
成本矩阵的行标签为 a、b、c、d。
声音
观察依据
主讲人讨论为人员 b、c 和 d 寻找指派方案。

符号

含义

指派问题中的人员 d。

适用范围

人员集合 {a, b, c, d}。

1, 2, 3, 4

依据清楚

视频直接表达

来源依据

图示
观察依据
成本矩阵的列在标题‘工作 →’下方标有 1、2、3、4。

符号

1, 2, 3, 4

含义

成本矩阵中的工作编号或列。

适用范围

工作集合 {1, 2, 3, 4}。

知识点 · 16

指派问题的目标

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出，在指派问题中，我们需要将某些工作分配给某些人员，每人至少分配一项工作，然后验证总成本是否最低。
声音
观察依据
主讲人进一步说明，我们必须生成一个优化解，即对各项工作的最优指派方案。

定义

解释

视频从操作层面定义了指派问题：每个人被指派一项特定工作；在所有此类指派方案中，寻找总成本最小的解。口述内容在示例中强调了一对一指派，但一般性描述最初提到工作数量可以任意，且每人至少分配一项工作。

公式

适用条件

存在需要匹配的人员与工作。
在所演示的例题中，每个人被分配了一项特定工作。
目标是最小化总成本。

分支定界法在指派问题中的应用

依据清楚

视频直接表达

来源依据

字幕依据
观察依据
页面标题为“指派问题与分支定界法”。
声音
观察依据
主讲人表示，本视频将展示如何使用分支定界法求解指派问题。

方法

解释

该片段将分支定界法介绍为求解指派问题的方法。在此节选中，仅陈述了初始思路：该方法首先求出一个下界，再据此在状态空间树中进一步展开。

公式

适用条件

当前讨论的问题是一个指派问题。

先修条目

指派问题的目标

下界作为最小成本估计值

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人说：‘首先，我们将检查并找出最低的下界’，即该下界是能给出最小成本的一个解。

待核验内容

‘最低的下界’这一说法表述不够严谨；实际演算示例中，LB 被视为由各行最小值所得到的一个单一的下界估计值。

定义

解释

在视频的非正式讲解中，下界被描述为与可能达到的最小总成本相关联的一个数值。后续计算表明，该下界是通过将成本矩阵中每一行的最小元素相加而得到的。

公式

适用条件

已提供一个成本矩阵。
该方法正被用于估计可实现的最小总成本。

先修条目

指派问题的目标

利用各行最小值计算初始下界

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人说，下界是通过对这些项分别取最小值得到的。
公式
观察依据
书面计算式为 LB = $2 + 3 + 1 + 2 = 8$ 。
图示
观察依据
笔尖依次指向第a、b、c、d行的行最小值2、3、1和2。

方法

解释

对于所展示的 $4\times 4$ 成本矩阵，视频通过取每行的最小元素并将这四个最小值相加，来计算初始下界。这可在分支过程开始前，快速得到最小总分配成本的一个可行估计值。

公式

LB = 2 + 3 + 1 + 2 = 8

适用条件

该矩阵以人员为行、工作为列进行组织。
所演示的规则仅使用各行最小值。

先修条目

下界作为最小成本估计值
已演算的 $4\times 4$ 分配成本矩阵

已演算的 $4\times 4$ 分配成本矩阵

依据清楚

视频直接表达

来源依据

图示
观察依据
一个手写的 $4\times 4$ 矩阵出现，其行标签为a、b、c、d，列标签为1、2、3、4。
声音
观察依据
主讲人指出共有四名人员和四项工作，此处给出的成本应为最小值。

定义

解释

该例题将指派问题实例化为四名人员与四项工作的情形。矩阵中的元素表示将每名人员分配至每项工作的成本，任务是从每行和每列各选一个元素，使得总成本最小。

公式

\begin{pmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 8 \\ 7 & 6 & 2 & 4 \end{pmatrix}

适用条件

各行对应人员a、b、c、d。
各列对应工作1、2、3、4。
各项均为非负整数成本。

先修条目

指派问题的目标

状态空间树作为下一阶段

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人表示，后续步骤将通过状态空间树来完成。

待核验内容

在此150秒的片段中，并未实际绘制或讲解任何状态空间树。

方法

解释

在介绍下界步骤后，主讲人指出，分支限界法的其余部分将通过状态空间树进行。该片段在该树被构建或分析之前就结束了。

公式

适用条件

已计算出一个初始下界。

先修条目

分支定界法在指派问题中的应用
利用各行最小值计算初始下界

对第一个分配变量进行分支

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人说：‘状态空间树第二层’，然后解释选取A行/第一个人，并划分为四个块。
图示
观察依据
一个根节点框标注为 LB = $2+3+1+2 = 8$ ，展开为四个子节点框，分别标注为 $a = 1$ 、 $a = 2$ 、 $a = 3$ 、 $a = 4$ 。

方法

解释

在此分配问题示例中，状态空间树的下一层通过固定分配给人员 a 的工作来构建。根节点的下界被分支为四个子节点，分别对应 $a = 1$ 、 $a = 2$ 、 $a = 3$ 和 $a = 4$ 。

公式

适用条件

该问题是一个含四个人员与四项工作的分配问题。
分支操作通过对选定人员分配一项工作来完成。

在固定一项分配后，子节点处的下界

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人表示，他们需要求出将 1、2、3 和 4 分配给人员 A 的最低成本。
公式
观察依据
在 $a = 1$ 下方写有表达式 $9+4+1+4 = 18$ ；在 $a = 2$ 下方写有表达式 $2+5+1+4 = 12$ 。

方法

解释

对每个子节点，下界通过以下方式计算：先加上人员 a 的已固定分配成本，再对每一项剩余工作，在所有尚未分配的人员中取其最小成本。视频明确演示了该规则在 $a = 1$ 和 $a = 2$ 情形下的应用。

公式

适用条件

当前节点已固定一项分配。
剩余工作通过在尚未分配的人员所在行中取最小值来评估。

先修条目

对第一个分配变量进行分支

指派问题的分枝定界法

依据清楚

视频直接表达

来源依据

图示
观察依据
纸上的标题为‘指派问题：分枝限界法’。
动画
观察依据
视频逐步展示搜索树的绘制与扩展过程。

方法

解释

一种通过遍历部分指派构成的搜索树来系统求解指派问题的方法。在每个节点处，计算出任意一个能扩展该部分指派的完整指派的费用下界。算法每次选择最有希望的节点（通常为下界最小的节点）进行下一步扩展。

公式

适用条件

适用于指派问题等组合优化问题。
需要一种能为部分指派计算有效下界的方法。

下界计算

依据清楚

视频直接表达

来源依据

图示
观察依据
树节点上展示了形如“LB = $2+3+1+2 = 8$ ”和“ $9+4+1+4 = 18$ ”的计算。
声音
观察依据
主讲人讲解如何在固定某项指派后，从剩余各列中找出最小值。

公式

解释

对于给定的部分指派，其下界由两部分之和构成：已固定的指派费用，以及未指派行与可用列中所能取到的最小剩余费用。

公式

LB = \sum_{\text{fixed } i} C_{i, j_i} + \sum_{\text{unassigned } k} \min_{j \in \text{available}} C_{k, j}

适用条件

可用列的集合必须排除已被固定行所占用的列。
未指派行的集合必须排除已被固定的行。

先修条目

指派问题的分枝定界法

指派问题的成本矩阵。

依据清楚

视频直接表达

来源依据

图示
观察依据
绘制了一个 $4\times 4$ 的成本矩阵，其行标记为 a、b、c、d，列标记为 1、2、3、4。

定义

解释

该问题由一个 $4\times 4$ 矩阵定义，其中行代表人员（a、b、c、d），列代表工作（1、2、3、4）。每个单元格中的数值表示将该特定工作分配给该特定人员的成本。

公式

\begin{bmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 3 \\ 7 & 6 & 2 & 4 \end{bmatrix}

适用条件

每人必须被分配且仅被分配一项工作。
每项工作必须被分配且仅被分配给一个人。

分支限界法状态空间树

依据清楚

视频直接表达

来源依据

图示
观察依据
状态空间树绘制在矩阵下方，从一个标记为“LB = $2+3+1+2 = 8$ ”的根节点开始分支。

方法

解释

通过状态空间树探索解：根节点通过求各列最小成本之和，计算出初始下界；后续节点则通过固定某人对某项工作的分配进行分支，并针对剩余未分配的工作重新计算下界。

公式

适用条件

用于系统性地探索指派问题的解空间。
剪除那些下界超过当前已知最优可行解的分支。

先修条目

指派问题的成本矩阵。

定理与条件 · 3

本例的初始下界等于8

依据清楚

视频直接表达

来源依据

公式
观察依据
方框中的结果为 LB = $2 + 3 + 1 + 2 = 8$ 。
声音
观察依据
主讲人称，这给出了下界值，即八；且该指派方案的总成本最低为八。

待核验内容

口头得出的结论比所展示的计算本身所能证明的更强；视频将8呈现为由行最小值所得的下界，而非最优性的完整证明。

命题

对于所展示的 $4\times 4$ 成本矩阵，通过求各行最小值之和所计算出的初始下界为8。

前提

矩阵元素如图所示。
行代表人员，列代表工作。
下界通过将每行的最小元素相加得到。

量词

针对视频中展示的具体例题矩阵。

分枝定界法可用于求解指派问题

依据清楚

视频直接表达

来源依据

声音
观察依据
“因此，我们通过使用分枝定界法来确定指派方案，并求解指派问题。”

命题

所展示的指派问题实例，是通过对部分指派与成本界构成的搜索树应用分枝定界法而求解的。

前提

给出一个含变量 a、b、c、d 的指派问题。
在可行的指派方案上构建一棵分支定界树。
节点代价与界值按图中所示方式计算。

量词

针对视频片段中展示的例题。

最优代价介于所显示的下界与上界之间。

依据清楚

视频直接表达

来源依据

声音
观察依据
“该代价值介于八（即下界）与十三之间。”
公式
观察依据
可见数值为 LB = 8，UB = 13。

待核验内容

该视频片段未重述界定法背后的通用定理；而是将这一思想应用于本例。

命题

对于视频片段中的这个例题，最优指派代价介于下界8与上界13之间。

前提

LB = 8对该问题成立。
UB = 13来源于一个可行的完整指派方案。

量词

针对视频片段中展示的这一特定指派问题实例。

推导与证明 · 18

从费用矩阵推导初始下界

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人解释说，下界是通过对每一行取最小值来求得的。
图示
观察依据
笔尖标出了每行的最小值：第a行是2，第b行是3，第c行是1，第d行是2。
公式
观察依据
板书公式变为 LB = $2 + 3 + 1 + 2 = 8$ 。

数值验证

步骤

公式
$\min(9,2,7,8)=2$
解释
第a行中最小的费用是2。
步骤依据
直接观察所展示矩阵的第一行。
视频直接表达
公式
$\min(6,4,3,7)=3$
解释
第b行中最小的费用是3。
步骤依据
直接观察所展示矩阵的第二行。
视频直接表达
公式
$\min(5,8,1,8)=1$
解释
第c行中最小的费用是1。
步骤依据
直接观察所展示矩阵的第三行。
视频直接表达
公式
$\min(7,6,2,4)=2$
解释
从第 d 行出发，最小成本为2。
步骤依据
直接观察所展示矩阵的第四行。
视频直接表达
公式
$LB = 2 + 3 + 1 + 2 = 8$
解释
将四行的最小值相加，得到初始下界。
步骤依据
视频指出，下界是通过取每行的最小值，再将这些最小值求和而得到的。
视频直接表达

结论

该示例的初始下界为8。

分支 $a = 1$ 的下界推导

依据清楚

视频直接表达

来源依据

声音
观察依据
说话人说：“因此，对于A1……我们在此处写九。九加……第二个数我们要写最小值四，但这个数除外……接下来是一。然后是四。”
公式
观察依据
在 $a = 1$ 下方所写的等式为： $9+4+1+4 = 18$ 。
图示
观察依据
钢笔指向元素 (a,1)=9，然后指向行 b、c、d 中各列的最小值：4 在第 2 列，1 在第 3 列，以及4 在第 4 列。

数值验证

步骤

公式
$9$
解释
从矩阵中提取人员a被指派至工作1的固定指派成本。
步骤依据
这是所选分支 $a = 1$ 的成本。
视频直接表达
公式
$4$
解释
对于工作2，在剩余人员b、c、d中取最小成本。
步骤依据
因人员a已被指派，故排除第a行；在第b、c、d行中，第2列可见的数值分别为4、8、6，因此最小值为4。
视频直接表达
公式
$1$
解释
对于工作3，在剩余人员b、c、d中取最小成本。
步骤依据
在第b、c、d行中，第3列可见的数值分别为3、1、2，因此最小值为1。
视频直接表达
公式
$4$
解释
对于工作4，在剩余人员b、c、d中取最小成本。
步骤依据
在第b、c、d行中，第4列可见的数值分别为7、8、4，因此最小值为4。
视频直接表达
公式
$9+4+1+4=18$
解释
将固定成本与剩余三列的最小值相加，得到该节点的下界。
步骤依据
这是页面上显示并由主讲人念出的求和式。
视频直接表达

结论

节点 $a = 1$ 处的下界为 18。

分支 $a = 2$ 对应下界的推导过程

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人说：‘现在来看 A 等于二的情形……接下来，我们在第一列（即 A 所在列）中，排除第一行（即 a 所在行）后寻找最小值。这个最小值是五。再加上这一列的最小值一，以及这一列的最小值四，结果为十二。’
公式
观察依据
在 $a = 2$ 下方写出的等式为 $2+5+1+4 = 12$ 。
图示
观察依据
钢笔指向元素 (a,2)=2，然后指向行 b、c、d 中各列的最小值：5 在第列 1，1 在第列 3，以及 4 在第列 4。

数值验证

步骤

公式
$2$
解释
从矩阵中取出人员 a 分配至工作 2 的固定指派成本。
步骤依据
这是所选分支 $a = 2$ 的成本。
视频直接表达
公式
$5$
解释
对于工作 1，在其余人员 b、c、d 中取最小成本。
步骤依据
b、c、d 行在第1列中可见的元素为 6、5、7，因此最小值为 5。
视频直接表达
公式
$1$
解释
对于工作 3，在其余人员 b、c、d 中取最小成本。
步骤依据
行b、c、d中可见的第3列元素分别为3、1、2，因此最小值为1。
视频直接表达
公式
$4$
解释
对于工作4，在剩余人员b、c、d中取最小成本。
步骤依据
行b、c、d中可见的第4列元素分别为7、8、4，因此最小值为4。
视频直接表达
公式
$2+5+1+4=12$
解释
将固定成本与其余三列的最小值相加，得到该节点的下界。
步骤依据
这是页面上所展示且讲解人所口述的求和式。
视频直接表达

结论

节点 $a = 2$ 处的下界为12。

根下界的推导

依据清楚

视频直接表达

来源依据

图示
观察依据
根节点显示“LB = $2+3+1+2 = 8$ ”。
声音
观察依据
说话人说：“第一个的最小值是2，第二个是3，第三个是1，第四个是2。”

数值验证

步骤

公式
$\min(9, 6, 5, 7) = 5$
解释
第1列的最小成本。
步骤依据
观察成本矩阵的第一列。
依据视频推导
公式
$\min(2, 4, 8, 6) = 2$
解释
第2列的最小成本。
步骤依据
观察成本矩阵的第二列。
依据视频推导
公式
$\min(7, 3, 1, 2) = 1$
解释
第3列的最小成本。
步骤依据
观察成本矩阵的第三列。
依据视频推导
公式
$\min(8, 7, 5, 4) = 4$
解释
第4列的最小成本。
步骤依据
观察成本矩阵的第四列。
依据视频推导

结论

视频采用各行最小值 $2+3+1+2=8$ ，得到有效的根节点下界。另按各列最小值求和 $5+2+1+4=12$ ，也得到一个有效且此例中更紧的下界。

分支 $a=1$ 下界推导

依据清楚

视频直接表达

来源依据

图示
观察依据
节点‘ $a=1$ ’显示‘ $9+4+1+4 = 18$ ’。
声音
观察依据
说话人说：“从9开始……第二项最小值为4，第三项为1，第四项为4……结果为18。”

数值验证

步骤

公式
$C_{a,1} = 9$
解释
将人员 a 分配至工作1的固定成本。
步骤依据
来自成本矩阵。
视频直接表达
公式
$\min(4, 8, 6) = 4$
解释
在成本矩阵第2列中，排除第 a 行后的最小成本。
步骤依据
来自成本矩阵，忽略第 a 行。
依据视频推导
公式
$\min(3, 1, 2) = 1$
解释
在成本矩阵第3列中，排除第 a 行后的最小成本。
步骤依据
来自成本矩阵，忽略第 a 行。
依据视频推导
公式
$\min(7, 5, 4) = 4$
解释
在成本矩阵第4列中，排除第 a 行后的最小成本。
步骤依据
来自成本矩阵，忽略第 a 行。
依据视频推导
公式
$9 + 4 + 1 + 4 = 18$
解释
将固定成本与剩余各项最小成本相加。
步骤依据
应用下界公式。
视频直接表达

结论

人员a被分配到工作1的分支的下界为18。

分支 $a=2$ 的下界推导

依据清楚

视频直接表达

来源依据

图示
观察依据
节点“ $a=2$ ”显示“ $2+5+1+4 = 12$ ”。
声音
观察依据
说话人说：“以2开头……第一个最小值为5，第三个为1，第四个为4……得到12。”

数值验证

步骤

公式
$C_{a,2} = 2$
解释
将人员a分配到工作2的固定成本。
步骤依据
来自成本矩阵。
视频直接表达
公式
$\min(6, 5, 7) = 5$
解释
在成本矩阵中，列1中排除第a行的最小成本。
步骤依据
来自成本矩阵，忽略第a行。
依据视频推导
公式
$\min(3, 1, 2) = 1$
解释
在成本矩阵中，列3中排除第a行的最小成本。
步骤依据
来自成本矩阵，忽略第a行。
依据视频推导
公式
$\min(7, 5, 4) = 4$
解释
在成本矩阵中，列4中排除第a行的最小成本。
步骤依据
来自成本矩阵，忽略第a行。
依据视频推导
公式
$2 + 5 + 1 + 4 = 12$
解释
将固定成本与最小剩余成本相加。
步骤依据
应用下界公式。
视频直接表达

结论

当人员 a 被分配至工作2的分支，其下界为12。

分支 $a=3$ 的下界推导

依据清楚

视频直接表达

来源依据

图示
观察依据
节点“ $a=3$ ”显示“ $7+5+4+4 = 20$ ”。
声音
观察依据
说话人说：“从7开始……第一个最小值是5，第二个是4，第四个是4……得到20。”

数值验证

步骤

公式
$C_{a,3} = 7$
解释
将人员 a 分配至工作3的固定成本。
步骤依据
来自成本矩阵。
视频直接表达
公式
$\min(6, 5, 7) = 5$
解释
在成本矩阵中，排除第 a 行后，第1列的最小成本。
步骤依据
来自成本矩阵，忽略第 a 行。
依据视频推导
公式
$\min(4, 8, 6) = 4$
解释
在成本矩阵中，排除第 a 行后，第2列的最小成本。
步骤依据
来自成本矩阵，忽略第 a 行。
依据视频推导
公式
$\min(7, 5, 4) = 4$
解释
排除第a行后，第4列的最小成本。
步骤依据
从成本矩阵中，忽略第a行。
依据视频推导
公式
$7 + 5 + 4 + 4 = 20$
解释
将固定成本与剩余各项最小成本相加。
步骤依据
应用下界公式。
视频直接表达

结论

当人员a被分配至工作3时，该分支的下界为20。

分支 $a=4$ 的下界推导

依据清楚

视频直接表达

来源依据

图示
观察依据
节点“ $a=4$ ”显示“ $8+5+4+1 = 17$ ”。
声音
观察依据
说话人说：“以8开头……第一个最小值是5，第二个是4，第三个是1……得到17。”

数值验证

步骤

公式
$C_{a,4} = 8$
解释
将人员a分配至工作4的固定成本。
步骤依据
来自成本矩阵。
视频直接表达
公式
$\min(6, 5, 7) = 5$
解释
排除第a行后，第1列的最小成本。
步骤依据
从成本矩阵中，忽略第a行。
依据视频推导
公式
$\min(4, 8, 6) = 4$
解释
排除第a行后，第2列的最小成本。
步骤依据
从成本矩阵中忽略第a行。
依据视频推导
公式
$\min(3, 1, 2) = 1$
解释
排除第a行后，第3列的最小成本。
步骤依据
从成本矩阵中忽略第a行。
依据视频推导
公式
$8 + 5 + 4 + 1 = 17$
解释
将固定成本与剩余各项最小成本相加。
步骤依据
应用下界公式。
视频直接表达

结论

在人员a被指派给工作4的分支中，其下界为17。

分支 $b=1$ （已知 $a=2$ ）的下界推导过程。

依据清楚

视频直接表达

来源依据

图示
观察依据
节点 ' $b=1$ ' 位于 ' $a=2$ ' 下方，显示 ' $6+2+1+4 = 13$ '。
声音
观察依据
说话人说：‘b等于1时的值为6……第二行的最小值为2，第三列为1，第四列为8……总和为13’。

数值验证

步骤

公式
$C_{a,2}+C_{b,1}=2+6=8$
解释
把两个已固定指派的成本相加。
步骤依据
读取原始成本矩阵。
依据视频推导
公式
$\min(C_{c,3},C_{d,3})=\min(1,2)=1$
解释
求未指派工作 3 的最小成本。
步骤依据
仅 c 和 d 尚未指派。
依据视频推导
公式
$\min(C_{c,4},C_{d,4})=\min(8,4)=4$
解释
求未指派工作 4 的最小成本。
步骤依据
仅 c 和 d 尚未指派。
依据视频推导
公式
$LB=2+6+1+4=13$
解释
固定成本加上两个剩余工作的最小成本。
步骤依据
该分支的有效下界。
视频直接表达

结论

在 $a=2$ 下， $b=1$ 分支的下界为 13，与原片手写计算一致。

分支 $b=3$ 的下界推导（已知 $a=2$ ）

依据清楚

视频直接表达

来源依据

图示
观察依据
节点 ' $b=3$ ' 位于 ' $a=2$ ' 下方，显示 ' $3+5$ +…。
声音
观察依据
说话人说：‘b等于3是3……第一行的最小值是5……3加5加最小值……’

待核验内容

所提供的片段中，计算尚未完成。

数值验证

步骤

公式
$C_{a,2}+C_{b,3}=2+3=5$
解释
固定指派成本之和。
步骤依据
原始成本矩阵。
依据视频推导
公式
$\min(C_{c,1},C_{d,1})=\min(5,7)=5$
解释
剩余工作 1 的最小成本。
步骤依据
剩余行 c 和 d。
依据视频推导
公式
$\min(C_{c,4},C_{d,4})=\min(8,4)=4$
解释
剩余工作 4 的最小成本。
步骤依据
剩余行 c 和 d。
依据视频推导
公式
$LB=2+3+5+4=14$
解释
求该分支的下界。
步骤依据
固定成本加上剩余工作列最小值。
视频直接表达

结论

在 $a=2$ 下， $b=3$ 分支的下界为 14。

根节点下界计算

依据清楚

视频直接表达

来源依据

图示
观察依据
根节点显示 LB = $2 + 3 + 1 + 2 = 8$ 。
声音
观察依据
讲解者说明取各列的最小值。

数值验证

步骤

公式
$\min(9, 6, 5, 7) = 5$
解释
找出工作1列中的最小成本。
步骤依据
列最小值计算。
依据视频推导
公式
$\min(2, 4, 8, 6) = 2$
解释
在工作2列中找出最小成本。
步骤依据
列最小值计算。
依据视频推导
公式
$\min(7, 3, 1, 2) = 1$
解释
在工作3列中找出最小成本。
步骤依据
列最小值计算。
依据视频推导
公式
$\min(8,7,8,4)=4$
解释
在工作4列中找出最小成本。
步骤依据
列最小值计算。
依据视频推导
公式
$LB=5+2+1+4=12$
解释
将各列最小值相加，得到初始下界。
步骤依据
指派问题中下界的定义。
依据视频推导

结论

原片根下界 8 来自各行最小值；另推得各列最小值之和为 12。两者均为有效下界，此例中 12 更紧。

节点的下界： $a=2$ ， $b=1$

依据清楚

视频直接表达

来源依据

图示
观察依据
节点“ $a=2$ ”有一个子节点“ $b=1$ ”，其计算过程为 $6 + 2 + 1 + 4 = 13$ 。
声音
观察依据
说话人说：“该值为6……再加上第四个的最小值4……得到结果14。”

待核验内容

音频读作14，但书面计算及最终圈出的数字是13。

数值验证

步骤

公式
$C_{b,1} = 6$
解释
将工作1分配给人员b的成本。
步骤依据
从成本矩阵中读取。
视频直接表达
公式
$C_{a,2} = 2$
解释
将工作2分配给人员a的成本。
步骤依据
从成本矩阵中读取。
视频直接表达
公式
$\min(C_{c,3}, C_{d,3}) = \min(1, 2) = 1$
解释
在可用人员c和d中，剩余工作3的最小成本。
步骤依据
未分配行对应的列最小值。
依据视频推导
公式
$\min(C_{c,4},C_{d,4})=\min(8,4)=4$
解释
在可用人员c和d中，剩余工作4的最小成本。
步骤依据
未分配行对应的列最小值。
依据视频推导
公式
$LB=6+2+1+4=13$
解释
固定成本与剩余最小成本之和。
步骤依据
下界计算方法。
依据视频推导

结论

原片写出 $6+2+1+4=13$ ；固定 $a=2$ 、 $b=1$ 后，这是正确的下界。

例题详解 · 5

四人四任务的指派示例

依据清楚

视频直接表达

来源依据

图示
观察依据
展示了一个 $4\times 4$ 的手写成本矩阵，行标签为 a、b、c、d，列标签为1、2、3、4。
声音
观察依据
主讲人指出，共有四个人和四项工作，我们需要为每个人分配一项特定工作，使得总成本最小。
公式
观察依据
下界计算式 LB = $2 + 3 + 1 + 2 = 8$ 写在矩阵下方。

待核验内容

本片段中并未找到完整的最优指派方案。

题目

给定一个用于四人四任务的 $4\times 4$ 成本矩阵，开始用分支定界法求解指派问题，并计算初始下界。

已知条件

人员：a、b、c、d。
任务：1、2、3、4。
费用矩阵：[[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 2, 4]]。

目标

在进入状态空间树之前，先求出总分配费用的初始下界。

步骤

公式
$\text{Identify the minimum entry in each row.}$
解释
该方法从逐行扫描每个人对应行中最低的可选任务费用开始。
步骤依据
主讲人指出，下界是通过取这些值中的最小值获得的。
视频直接表达
公式
$2,\ 3,\ 1,\ 2$
解释
各行的最小值分别为：a 行为2，b 行为3，c 行为1，d 行为2。
步骤依据
这些数值直接来自屏幕上显示的矩阵。
视频直接表达
公式
$LB = 2 + 3 + 1 + 2 = 8$
解释
将四个行最小值相加，即可得到初始下界。
步骤依据
这正是方框中所写的计算过程。
视频直接表达

结果

下界 LB = 8

检验

算式 $2 + 3 + 1 + 2 = 8$ 正确无误，且所选数字与矩阵中可见的各行最小值完全一致。

指派问题的第二层分支示例

依据清楚

视频直接表达

来源依据

图示
观察依据
页面标题为‘指派问题’与‘分支定界法’，含一个 $4\times 4$ 的成本矩阵及一棵部分构建的状态空间树。
声音
观察依据
讲解人说明如何构建状态空间树的第二层，并计算分支 $a = 1$ 与 $a = 2$ 的下界。

待核验内容

关于 $a = 3$ 与 $a = 4$ 的计算仅口头开始，未在本片段内完成。

题目

给定一个 $4\times 4$ 的指派成本矩阵，人员为a、b、c、d，工作为1、2、3、4，通过对人员a所分配的工作进行分支，构建分支定界法状态空间树的第二层，并计算所得子节点的下界。

已知条件

成本矩阵各行： $a = (9,2,7,8)$ ， $b = (6,4,3,7)$ ， $c = (5,8,1,8)$ ， $d = (7,6,2,4)$ 。
根节点下界表示为 LB = $2+3+1+2 = 8$ 。
分支变量是分配给人员 a 的工作。

目标

创建子节点 $a = 1$ 、 $a = 2$ 、 $a = 3$ 、 $a = 4$ ，并使用所演示的规则计算它们的下界。

步骤

公式
$a=1,\ a=2,\ a=3,\ a=4$
解释
根据人员 a 可能承担的四项工作，将根节点分为四个子节点。
步骤依据
这便是状态空间树第二层的构造描述。
视频直接表达
公式
$9+4+1+4=18$
解释
计算节点 $a = 1$ 的下界。
步骤依据
固定成本 $c_{a1}=9$ ，加上行 b、c、d 对工作 2、3、4 的列最小值之和。
视频直接表达
公式
$2+5+1+4=12$
解释
计算节点 $a = 2$ 的下界。
步骤依据
固定成本 $c_{a2}=2$ ，加上行 b、c、d 对工作 1、3、4 的列最小值之和。
视频直接表达
公式
$7+\cdots$
解释
开始对节点 $a = 3$ 进行下界计算，先写出固定成本 7。
步骤依据
说话人说：‘类似地，我们还需处理 A 等于三的情形……因此此处 A 等于三的值为七’，但该片段未完成后续内容。
视频直接表达

结果

本片段中已完成计算的子节点下界为： $a = 1$ 得到 18， $a = 2$ 得到 12；而分支 $a = 3$ 和 $a = 4$ 已被提出，但在该段结束前尚未完成计算。

检验

页面上写出的加法算式与口头叙述的算术一致： $9+4+1+4=18$ ，以及 $2+5+1+4=12$ 。

使用分支定界法求解 $4\times 4$ 指派问题

依据清楚

视频直接表达

来源依据

图示
观察依据
提供了一个 $4\times 4$ 的成本矩阵，并构建了一棵分支定界树来求解它。

题目

在给定成本矩阵的前提下，为4个人（a、b、c、d）分配4项工作（1、2、3、4），使总成本最小，求最优指派方案。

已知条件

成本矩阵 $C = [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 5], [7, 6, 2, 4]]$

目标

确定指派顺序及最小总成本。

步骤

公式Calculate root LB
解释
计算整个问题的初始下界。
步骤依据
分支定界法的标准第一步。
视频直接表达
公式Branch on person a
解释
创建四个子节点，分别表示 $a=1$ 、 $a=2$ 、 $a=3$ 、 $a=4$ 。
步骤依据
枚举第一个人的所有可能指派。
视频直接表达
公式Calculate LB for each 分支 of a
解释
对每个子节点，在 a 的指派已固定的前提下，计算其下界。
步骤依据
用于评估各分支的潜力。
视频直接表达
公式Select most promising 分支
解释
选择下界最小的分支（ $a=2$ ，LB=12）进行进一步扩展。
步骤依据
一种高效的贪心策略，用于寻找最优解。
视频直接表达
公式Branch on person b
解释
在 $a=2$ 节点下，为 $b=1$ 、 $b=3$ 、 $b=4$ 创建子节点（ $b=2$ 被排除，因为任务 2 已被分配）。
步骤依据
继续探索部分赋值。
视频直接表达
公式Calculate LB for branches of b
解释
计算新节点的下界。
步骤依据
以指导下一步的选择。
视频直接表达

结果

该视频在 150 秒的片段内未得出最终答案，仅演示了计算下界及扩展搜索树的过程。

检验

该方法的正确性依赖于下界是对任意部分赋值之完整扩展的真实代价的有效低估。

通过分支定界法求解指派问题

依据清楚

视频直接表达

来源依据

图示
观察依据
整个问题设定（含矩阵与树形图）始终可见。
声音
观察依据
讲解者全程口述指派问题的求解过程。

题目

在给定成本矩阵的前提下，将4项工作指派给4个人，使得总成本最小，求最优指派方案。

已知条件

成本矩阵：[[9,2,7,8],[6,4,3,7],[5,8,1,3],[7,6,2,4]]
行对应人员 a、b、c、d；列对应工作1、2、3、4。

目标

确定使总成本最小的指派方案。

步骤

公式
$\text{Explore \text{分支} } a=2$
解释
选择人员“a”承担工作“2”，因其对应成本较低。
步骤依据
用于启动分支的启发式选择。
视频直接表达
公式
$\text{Explore sub-branches } b=1, b=3, b=4$
解释
对剩余人员，为人员“b”分配可选工作并计算下界。
步骤依据
对状态空间进行系统性探索。
视频直接表达
公式
$\text{Select node with lowest LB } (b=1, LB=13)$
解释
选择下界最小的分支继续探索。
步骤依据
分支定界剪枝策略。
视频直接表达
公式
$\text{Evaluate leaves under } b=1$
解释
计算剩余两种可能的完整指派方案的精确总成本。
步骤依据
得到一个可行解需要为所有人分配任务。
视频直接表达
公式
$\text{Compare leaf costs: } 13 \text{ vs } 18$
解释
在已评估的可行解中找出最小成本。
步骤依据
目标是最小化。
视频直接表达

结果

视频得出的最优分配方案是 $a=2$ , $b=1$ , $c=3$ , $d=4$ ，总成本为 13。

检验

独立枚举全部 24 种完整指派，确认 13 为全局最小值；树上的下界也排除了其他分支。

例题：给出一个可行分配方案，其上界 UB = 13

依据清楚

视频直接表达

来源依据

图示
观察依据
手写树上的一个叶节点框内写着“ $a = 2$ , $b = 1$ , $c = 3$ , $d = 4$ ”，其下方为“ $2 + 6 + 1 + 4 = 13$ UB”。
声音
观察依据
B负责工作一，C负责工作三，D负责工作四。由此得到上界……介于八……与十三之间。

待核验内容

本片段中未显示完整的原始成本矩阵，因此仅能验证画面中展示的运算过程。

题目

根据分配问题的分支定界树，评估完全分配 $a=2$ 、 $b=1$ 、 $c=3$ 、 $d=4$ ，并用它来界定最优成本。

已知条件

为含变量 a、b、c、d 的分配问题绘制了一棵分支定界树。
根节点的下界标为 LB = $2 + 3 + 1 + 2 = 8$ 。
其中一个叶节点的分配方案标为 $a = 2$ 、 $b = 1$ 、 $c = 3$ 、 $d = 4$ 。
该叶节点对应的成本和写作 $2 + 6 + 1 + 4 = 13$ 。

目标

求出画面中所示可行分配的总成本，并写出由此得出的最优成本的界区间。

步骤

公式
$a=2,\ b=1,\ c=3,\ d=4$
解释
从叶节点直接读出完整的可行分配方案。
步骤依据
直接显示在手写方框内。
视频直接表达
公式
$2+6+1+4=13$
解释
利用叶节点下方标出的成本，计算该分配方案的总成本。
步骤依据
页面上写出的显式算术运算。
视频直接表达
公式
$UB=13$
解释
将这一可行的总成本视为最优值的一个上界。
步骤依据
页面将该值标记为“UB”，而讲解者称其为上界。
视频直接表达
公式
$LB=8$
解释
回顾已写在树顶的根节点下界。
步骤依据
可见公式：“LB = $2 + 3 + 1 + 2 = 8$ ”。
视频直接表达
公式
$8 \leq \text{optimal cost} \leq 13$
解释
结合下界与上界，描述包含最优值的区间。
步骤依据
针对最小化问题的界定论证；视频片段中以口头方式陈述。
依据视频推导

结果

可行分配 (a,b,c,d)=(2,1,3,4) 的成本为 13，因此最优成本满足 8 ≤ 最优成本 ≤ 13。

检验

答案与页面上可见的标签“LB = 8”和“13 UB”一致，也与讲解者所说的“成本介于八与十三之间”这一陈述一致。

图示与动画 · 9

标题页，含主题标题

依据清楚

视频直接表达

来源依据

图示
观察依据
镜头持续对准一张白纸，其上用红色手写字体标有标题“指派问题”和“分支限界法”。

图中对象

白纸
红色手写标题：指派问题
红色手写副标题：分枝定界法

变化过程

画面构图略有移动，但同一标题持续可见。

不变量

两个红色标题在整个时段内始终保留在屏幕上。

数学含义

在引入任何数值例题之前，画面已明确确立本课主题。

成本矩阵及其坐标轴的引入

依据清楚

视频直接表达

来源依据

图示
观察依据
一张新纸张展开，显示一个4x4矩阵，行标签为 a、b、c、d，列标签为1、2、3、4。
动画
观察依据
讲解者在行旁手写“人员”，在列旁手写“工作”。

图中对象

4x4手写矩阵
行标签 a、b、c、d
列标签1、2、3、4
手写标签“人员”与“工作”

变化过程

矩阵成为关注焦点。
添加坐标轴标注，以明确行代表人员、列代表工作。

不变量

在此区间内，矩阵的数值元素保持不变。

数学含义

该图示将抽象的指派问题转化为具体的费用表格。

书写并框出下界计算式

依据清楚

视频直接表达

来源依据

动画
观察依据
在矩阵下方绘制一个矩形框。
公式
观察依据
在框内，讲解者写下 LB = $2 + 3 + 1 + 2 = 8$ ，并圈出最终的8。
图示
观察依据
书写求和过程时，笔尖指向矩阵中各行的最小值。

图中对象

矩形答案框
表达式 LB = $2 + 3 + 1 + 2 = 8$
圈出的最终值8

变化过程

方框已绘制完成。
依次填入各项2、3、1和2。
写出总和8，并用圆圈强调。

不变量

底层成本矩阵仍保留在方框上方可见。

数学含义

动画突出显示为分支定界法提供初始下界的计算步骤。

根节点展开为四个分支

依据清楚

视频直接表达

来源依据

动画
观察依据
一只手从根节点框 LB = $2+3+1+2 = 8$ 向下画出连线，连接至四个子节点框，分别标为 $a = 1$ 、 $a = 2$ 、 $a = 3$ 、 $a = 4$ 。
图示
观察依据
成本矩阵始终显示在树结构上方，而新添加的节点位于其下方。

图中对象

根节点框，标注 LB = $2+3+1+2 = 8$
四个子节点框，分别标为 $a = 1$ 、 $a = 2$ 、 $a = 3$ 、 $a = 4$
连接各分支的连线

变化过程

该树由一个根节点生长出四个子节点。
每个子节点均标有一个标签，指明分配给人员 a 的工作。

不变量

成本矩阵本身不发生变化。
根节点的下界仍为8。

数学含义

这一可视化展开表示对人员 a 的指派决策进行分支，为每一项可能的工作创建一个子问题。

在子节点下方书写下界表达式

依据清楚

视频直接表达

来源依据

动画
观察依据
笔书写 $9+4+1+4=18$ 在节点 a 下等于 1 并随后写下 $2+5+1+4=12$ 在节点 a 下等于 2。
图示
观察依据
书写过程中，钢笔指向每个求和式所用到的特定矩阵元素。

图中对象

表达式 $9+4+1+4=18$ 在 a = 下1
表达式 $2+5+1+4=12$ 在 a = 下2
钢笔所引用的成本矩阵单元格

变化过程

数值型下界表达式被添加在前两个子节点的下方。
钢笔在矩阵元素与已写出的求和式之间移动。

不变量

分支标签 $a = 1$ 和 $a = 2$ 保持不变。
矩阵数值保持固定。

数学含义

所写出的表达式表明：每个子节点的下界均由一个固定的指派成本与剩余各行中各列的三个列最小值组合而成。

分支限界搜索树的构建

依据清楚

视频直接表达

来源依据

动画
观察依据
一只手在纸上逐次绘制树形结构，边添加节点与边，边书写计算过程。

图中对象

代价矩阵
搜索树节点
连接节点的边
手写计算

变化过程

随着分支的探索，新节点被添加到树中。
每个节点旁会计算并标注下界值。
用连线将父节点与子节点连接起来。

不变量

成本矩阵在整个片段中保持不变。
整棵树的结构从单一的根节点向下生长。

数学含义

该视觉过程展示了分支定界算法的逐步执行过程，说明搜索空间是如何被系统性地探索与评估的。

状态空间树状图

依据清楚

视频直接表达

来源依据

图示
观察依据
在纸上绘制一棵层次化的树状图，从一个单独的根方框开始，向下分叉展开。

图中对象

根节点方框
分支连线
子节点方框
方框内的成本计算

变化过程

随着讲解者探索不同分配方案，不断添加新的节点。
直线连接父节点与子节点。
计算过程写在节点方框内部。

不变量

整体结构仍为一棵树。
根节点位于顶部。

数学含义

该图示表示分支定界算法中对可能分配方案的系统性探索。

指派问题的分支定界树

依据清楚

视频直接表达

来源依据

图示
观察依据
页面展示了一棵手绘的树：根节点标有 LB = $2 + 3 + 1 + 2 = 8$ ；分支标有 $a=1$ 、 $a=2$ 、 $a=3$ 、 $a=4$ ；子分支标有 $b=1$ 、 $b=3$ 、 $b=4$ ；叶节点方框内为完整赋值及对应的成本总和。
动画
观察依据
一支笔指向不同节点，而摄像机基本固定在纸面上。

待核验内容

部分右侧节点被截断或模糊，因此并非所有分支标签都清晰可辨。

图中对象

根节点，其下界 LB = 8
分支节点标记为 $a=1$ 、 $a=2$ 、 $a=3$ 、 $a=4$
子分支节点标记为 $b=1$ 、 $b=3$ 、 $b=4$
叶节点方框中标注了若干指派方案，例如 $a=2$ , $b=1$ , $c=3$ , $d=4$ 和 $a=2$ , $b=1$ , $c=4$ , $d=3$
手写的成本总和及圈出的合计数值

变化过程

笔尖指向叶节点指派方案 $a=2$ , $b=1$ , $c=3$ , $d=4$ 及其对应成本 13
视频末尾视角略微向上并向左偏移，从而展现出更多左上角表格区域
讲话者在树下方书写或强调区间 8–13

不变量

整段视频中，树的结构始终保持不变
根节点的下界始终显示为 8
被高亮标出的可行叶节点成本始终显示为 13

数学含义

视觉布局编码了对赋值的搜索：每条路径固定变量 a、b、c、d 的取值，所标注的求和结果即为各节点的代价，用于剪枝定界。

强调下界与上界

依据清楚

视频直接表达

来源依据

图示
观察依据
树形图下方，数字8和13在口述与书写中均被强调为上下界。
声音
观察依据
“该代价值将介于八（即下界）与十三之间。”

待核验内容

区间表示中手写标点的具体形式在每一帧中均不够清晰。

图中对象

来自根节点下界（LB）的数字8
来自可行叶节点上界（UB）的数字13
树形图下方的手写区间表示法

变化过程

注意力从叶节点代价13回溯至全局界比较。
区间8–13被呈现为该示例的结果。

不变量

8仍被标识为下界。
13仍被标识为上界。

数学含义

本片段通过视觉与语言方式，直观总结了分支定界法所得的上下界结果。

易错点 · 6

将初始下界与已证实的最优解混淆

依据清楚

依据视频推导

来源依据

声音
观察依据
讲解者称该指派的总成本最低值为八。
公式
观察依据
仅展示行最小值之和构成的下界 LB = 8；未呈现任何完整指派。

待核验内容

此问题被标记为措辞可能引发的误解，而非该方法数学过程中的确凿错误。

误区

人们可能从讲解者的口头表述中推断，8已是最终最优指派的成本。

说明

该片段实际演示的是基于各行最小值计算初始下界的过程；本片段中视频尚未展示完整的分支搜索，也未在此部分验证出最优指派。

计算其余最小值时，不得重复使用已分配的行。

依据清楚

视频直接表达

来源依据

声音
观察依据
说话人说：‘对于第二个，我们必须写出除这个以外的最小值，即四；我们不能包含这一个。’
图示
观察依据
在计算 $a = 1$ 的界时，笔跳过第 a 行，仅从第 b、c、d 行中选取最小值。

误区

有人可能错误地从所有行（包括当前节点已分配的行）中取各列的最小值。

说明

在固定 $a = j$ 后，其余贡献只能来自尚未分配的人，因此第 a 行被排除在其余各列的最小值计算之外。

行下界与列下界都有效

依据清楚

依据视频推导

来源依据

声音
观察依据
在0:00处，说话人将根节点的下界（LB）计算为“ $2+3+1+2=8$ ”，这对应的是各行的最小值，而非各列的最小值。
图示
观察依据
分配问题的标准解法通常以各列最小值作为初始下界。

误区

只有沿一个方向求最小值才能构造下界。

说明

行最小值之和为 8，列最小值之和为 12；两者都是最优成本的下界，哪一个更紧取决于具体矩阵。

不要重复计入已分配工作

依据清楚

依据视频推导

来源依据

图示
观察依据
在2:00处，节点“ $b=1$ ”的计算式写作“ $6+2+1+4=13$ ”。
声音
观察依据
主讲人口头描述了该计算的各项组成，但板书所写的数值并未正确体现该方法的应用。

误区

固定 $a=2$ 、 $b=1$ 后，再次把工作 2 当作剩余工作计入。

说明

固定成本为 $2+6=8$ ；只剩工作 3 和 4，其最小成本为 1 和 4，所以下界为 $8+1+4=13$ 。

回查原始矩阵中的数字

依据清楚

依据视频推导

来源依据

图示
观察依据
原始表与第二个叶节点都显示 c 到工作 4 的成本为 8；第二个叶节点总成本 $2+6+8+2=18$ 。
声音
观察依据
讲解者有时口头陈述一个结果（例如14），却与所写数字（例如13）相矛盾。

误区

把手写的 c 到工作 4 的成本 8 误读为 3。

说明

按 8 计算，原片各分支下界与叶节点成本均成立；早期自动提取误读为 3，产生了错误的纠错说明。

上界并不自动等同于已证明的最优解，除非所有更优的分支均已被排除。

时间近似

补充解释

来源依据

声音
观察依据
讲话者指出成本将介于8与13之间，并称此为该示例的最优解范围。
公式
观察依据
本页将13标记为UB，而非在此片段中明确将其表述为该范围内的唯一最优解。

待核验内容

这一提醒并未在片段中明确陈述，而是作为概念性说明额外添加的。

误区

人们可能误以为，任何被标记为UB的可行成本值，无需进一步剪枝或比较，即可立即视为最终最优值。

说明

在分支定界法中，一个可行解为最小成本提供了上界；而要确认最优性，则需确保所有未探索的分支均无法产生更小的成本。本片段中，讲话者所作的结论将8–13视作该例题的上下界结果。

概念关系 · 12

分支定界法在指派问题中的应用 → 指派问题的目标

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人表示，本视频将使用分支定界法来解决指派问题。
字幕依据
观察依据
标题将“指派问题”与“分支定界法”配对呈现。

应用

解释

分支定界法被作为求解指派问题所采用的方法予以介绍。

利用各行最小值计算初始下界 → 状态空间树作为下一阶段

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人首先指出要找出下界，然后说明后续步骤将通过状态空间树来完成。

先修

解释

在口述的工作流程中，计算初始下界先于状态空间树的探索。

已演算的 $4\times 4$ 分配成本矩阵 → 指派问题的目标

依据清楚

视频直接表达

来源依据

图示
观察依据
抽象讨论之后，给出一个具体的 $4\times 4$ 成本矩阵。
声音
观察依据
主讲人说：“我们通过一个例子来理解这一点。”

特例

解释

该 $4\times 4$ 矩阵是前述一般指派问题的一个具体实例。

利用各行最小值计算初始下界 → 下界作为最小成本估计值

依据清楚

视频直接表达

来源依据

声音
观察依据
下界的定义先以口头方式给出，再应用具体的数值规则。
公式
观察依据
后续框出的计算过程，正是将这一思想应用于示例矩阵。

应用

解释

按行取最小值再求和的步骤，是本视频所介绍的非正式下界概念的具体实现。

对第一个分配变量进行分支 → 在固定一项分配后，子节点处的下界

依据清楚

视频直接表达

来源依据

图示
观察依据
先画出子节点 $a = 1$ 、 $a = 2$ 、 $a = 3$ 、 $a = 4$ ，再在其下方写出下界表达式。
声音
观察依据
讲话者首先描述划分四个块，然后表示需要找出这些指派的最低成本。

应用

解释

分支步骤生成了子问题，而子节点下界规则将应用于这些子问题。

在固定一项分配后，子节点处的下界 → 指派问题的第二层分支示例

依据清楚

视频直接表达

来源依据

公式
观察依据
该通用规则在例题中具体化为 $9+4+1+4=18$ 和 $2+5+1+4=12$ 。

应用

解释

该例题在具体的矩阵数据上展示了子节点下界法。

指派问题的分枝定界法 → 下界计算

依据清楚

视频直接表达

来源依据

图示
观察依据
标题明确将“指派问题”与“分支定界法”关联起来。

应用

解释

分支定界法被用于求解指派问题，其核心机制依赖于对部分指派计算下界。

分支限界法状态空间树 → 指派问题的成本矩阵。

依据清楚

视频直接表达

来源依据

图示
观察依据
标题“指派问题的分支定界法”将这两个概念关联起来。

应用

解释

分支定界法被用于求解由成本矩阵所定义的指派问题。

用分支定界法求解指派问题 → 根节点下界 LB = 8

依据清楚

视频直接表达

来源依据

声音
观察依据
讲话者将指派问题的解直接与分支定界法关联起来。
图示
观察依据
该树状图在方法展示过程中同时标出了LB与UB的数值。

包含

解释

分支定界求解法包含在根节点处计算并使用下界。

用分支定界法求解指派问题 → 由可行指派 (a,b,c,d)=(2,1,3,4) 得到的上界

依据清楚

视频直接表达

来源依据

图示
观察依据
树的一个叶节点产生了标记为UB = 13的值。
声音
观察依据
讲话者称该指派给出了上界。

包含

解释

同样的分支定界过程也会从一个可行的完整指派中生成一个上界。

根节点下界 LB = 8 → 最优成本介于 8 与 13 之间

依据清楚

视频直接表达

来源依据

声音
观察依据
“成本值将在八……和……十三之间。”
公式
观察依据
下界 LB = 8 和上界 UB = 13 均可见。

应用

解释

根节点的下界与可行的上界共同用于确定最优成本区间。

由可行指派 (a,b,c,d)=(2,1,3,4) 得到的上界 → 最优成本介于 8 与 13 之间

依据清楚

视频直接表达

来源依据

声音
观察依据
说话者将上界13与下界8合并为最终的范围。
公式
观察依据
叶节点的值13被标记为 UB。

应用

解释

可行指派的成本被用作界定区间的上端点。

问题定位 · 17

本节分支限界法课程中的指派问题是什么？

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人将任务定义为：以最低成本将工作分配给人员。

涉及知识点

指派问题的目标

本视频中，如何从成本矩阵计算初始下界？

依据清楚

视频直接表达

来源依据

公式
观察依据
手写行 LB = $2 + 3 + 1 + 2 = 8$ 展示了所采用的确切规则。

涉及知识点

利用各行最小值计算初始下界
下界作为最小成本估计值

为何该例题得出 LB = 8？

依据清楚

视频直接表达

来源依据

公式
观察依据
框出的结果为 LB = 8。

涉及知识点

从费用矩阵推导初始下界
本例的初始下界等于8

在分支限界法中，下界计算之后的步骤是什么？

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出，后续步骤将通过状态空间树来完成。

涉及知识点

状态空间树作为下一阶段

在指派问题示例中，应如何理解这个 $4\times 4$ 矩阵？

依据清楚

视频直接表达

来源依据

图示
观察依据
行由人员标记，列由工作标记。

涉及知识点

已演算的 $4\times 4$ 分配成本矩阵

在此指派问题的分支限界示例中，状态空间树的第二层代表什么？

依据清楚

视频直接表达

来源依据

声音
观察依据
讲话者明确说道：‘状态空间树第二层’。
图示
观察依据
从根节点引出四个子节点。

涉及知识点

对第一个分配变量进行分支
根节点展开为四个分支

下界 18 对于节点 $a = 1$ 从成本矩阵计算得出？

依据清楚

视频直接表达

来源依据

公式
观察依据
书面表达式 $9+4+1+4=18$ 出现在节点 $a = 1$ 下方。
声音
观察依据
主讲人解释先选定9，再从剩余各行中分别选取极小值4、1和4。

涉及知识点

在固定一项分配后，子节点处的下界
分支 $a = 1$ 的下界推导

为何在为子节点计算剩余各列的最小值时要排除第 a 行？

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出，在寻找最小值时不能包含已选定的行。

涉及知识点

计算其余最小值时，不得重复使用已分配的行。
在固定一项分配后，子节点处的下界

下界如何12 节点 a 的 = 2 得到？

依据清楚

视频直接表达

来源依据

公式
观察依据
书面表达式 $2+5+1+4=12$ 出现在节点 $a = 2$ 下方。
声音
观察依据
主讲人说，第一列中除第 A 行外的最小值依次为五、一、四，总和为十二。

涉及知识点

在固定一项分配后，子节点处的下界
分支 $a = 2$ 对应下界的推导过程

在指派问题中，使用分支定界法时，如何计算某一特定分支的下界？

依据清楚

依据视频推导

来源依据

声音
观察依据
主讲人反复讲解如何针对不同分支计算下界。

涉及知识点

下界计算
分支 $a=1$ 下界推导
分支 $a=2$ 的下界推导

在分支定界搜索树中，选择下一个待扩展节点的规则是什么？

依据清楚

依据视频推导

来源依据

动画
观察依据
视频通过可视化方式展示了搜索树的展开过程。

涉及知识点

指派问题的分枝定界法
分支限界搜索树的构建

根据视频，最优指派方案及其成本是多少？

依据清楚

依据视频推导

来源依据

声音
观察依据
讲话者在视频片段结尾处给出了最优指派方案。

涉及知识点

指派问题的成本矩阵。
分支限界法状态空间树
通过分支定界法求解指派问题

覆盖情况与待核验内容

已覆盖 · 封面页及口头介绍：用分支限界法求解指派问题。

已覆盖 · 对指派问题的口头讲解，以及最小化成本这一目标的说明。

已覆盖 · 下界的非正式定义，以及向具体示例的过渡。

已覆盖 · $4\times 4$ 成本矩阵已给出，标注为‘人员与之对比工作’，并命名了下一步的计算阶段。

已覆盖 · 执行按行取最小值的下界计算，并将结果框出：LB = 8。

已覆盖 · 该片段以指派问题板面及根节点下界开场，随后主讲人讲解并绘制状态空间树的第二层，分支为 $a = 1$ 、 $a = 2$ 、 $a = 3$ 、 $a = 4$ 。

已覆盖 · 主讲人计算了前两个子节点的下界，写出 $9+4+1+4=18$ 与 $2+5+1+4=12$ ，并在片段结束前开始但未完成对 $a = 3$ 的讨论。

已覆盖 · 本片段完整涵盖了运用分支定界法求解指派问题的初始设置与步骤，包括下界计算与搜索树展开。

已覆盖 · 整个视频片段涵盖了指派问题的分支定界法建模与求解全过程，包括各项计算及最终结论。

已覆盖 · 视频片段从分支定界树开始，高亮显示一个可行的叶节点指派： $a=2$ , $b=1$ , $c=3$ , $d=4$ ，其成本为13，并标记为UB。

已覆盖 · 主讲人将根节点下界8与可行上界13合并，得到最优成本的区间8–13。

已覆盖 · 镜头在整棵分支定界树上停留，主讲人总结指出：该指派问题通过分支定界法得以求解。

探索视频中的知识

已审核的主题路径

用分支定界法解指派问题

把讲解展开来看。

章节

学习解说文稿

知识卡片

指派问题的目标函数

以分支定界法作为求解方法

下界思想

4×44\times 44×4成本矩阵示例

基于各行最小值的初始下界

接下来是状态空间树

注意：该下界尚不能证明为最优解

指派问题的分枝定界法设置

状态空间树的第二层

如何计算子节点的下界

分支 a=1a = 1a=1 的下界

为何要排除已指派的行

分支 a 的下界 = 2

分支定界法

下界计算

搜索树扩展

常见误区：下界计算错误

指派问题成本矩阵

分支定界法

下界计算

最优解识别

指派问题的分枝定界树

根节点下界 LB = 8

给出上界 UB = 13的可行赋值

详细学习笔记

LB

a, b, c, d

1, 2, 3, 4

cost matrix

Cost matrix entries

LB

a=ja = ja=j

a

b

c

d

1, 2, 3, 4

指派问题的目标

分支定界法在指派问题中的应用

下界作为最小成本估计值

利用各行最小值计算初始下界

已演算的4×44\times 44×4分配成本矩阵

状态空间树作为下一阶段

对第一个分配变量进行分支

在固定一项分配后，子节点处的下界

指派问题的分枝定界法

下界计算

指派问题的成本矩阵。

分支限界法状态空间树

本例的初始下界等于8

分枝定界法可用于求解指派问题

最优代价介于所显示的下界与上界之间。

从费用矩阵推导初始下界

分支a=1a = 1a=1的下界推导

分支 a=2a = 2a=2 对应下界的推导过程

根下界的推导

分支 a=1a=1a=1 下界推导

分支a=2a=2a=2的下界推导

分支 a=3a=3a=3 的下界推导

分支a=4a=4a=4的下界推导

分支b=1b=1b=1（已知a=2a=2a=2）的下界推导过程。

分支 b=3b=3b=3 的下界推导（已知 a=2a=2a=2）

根节点下界计算

节点的下界：a=2a=2a=2，b=1b=1b=1

四人四任务的指派示例

指派问题的第二层分支示例

使用分支定界法求解4×44\times 44×4指派问题

通过分支定界法求解指派问题

例题：给出一个可行分配方案，其上界 UB = 13

标题页，含主题标题

成本矩阵及其坐标轴的引入

书写并框出下界计算式

根节点展开为四个分支

在子节点下方书写下界表达式

分支限界搜索树的构建

$4\times 4$ 成本矩阵示例

分支 $a = 1$ 的下界

$a = j$

已演算的 $4\times 4$ 分配成本矩阵

分支 $a = 1$ 的下界推导

分支 $a = 2$ 对应下界的推导过程

分支 $a=1$ 下界推导

分支 $a=2$ 的下界推导

分支 $a=3$ 的下界推导

分支 $a=4$ 的下界推导

分支 $b=1$ （已知 $a=2$ ）的下界推导过程。

分支 $b=3$ 的下界推导（已知 $a=2$ ）

节点的下界： $a=2$ ， $b=1$

使用分支定界法求解 $4\times 4$ 指派问题

已演算的 $4\times 4$ 分配成本矩阵 → 指派问题的目标

在指派问题示例中，应如何理解这个 $4\times 4$ 矩阵？

下界 18 对于节点 $a = 1$ 从成本矩阵计算得出？