标签：剪枝颜色着色搜索会场回溯解决顶点

此为课题组所指导本科生和低年级硕士生学习组合优化问题汇报
所用教材：北京大学屈婉玲教授《算法设计与分析》
课程资料：https://www.icourse163.org/course/PKU-1002525003
承诺不用于任何商业用途，仅用于学术交流和分享

更多内容请关注许志伟课题组官方中文主页：https://JaywayXu.github.io/zh-cn/

1. 回溯法解决图着色问题（9.5）

1.1 图着色问题的描述

图着色问题的输入是一个无向连通图 $G$，以及 $m$ 种可用颜色的集合。要求使用这些颜色对图的所有顶点进行着色，且满足以下条件：

每个顶点只能使用一种颜色。
每条边的两个端点必须着不同的颜色。

输出为所有可能的着色方案；如果无法找到任何方案，则输出“NO”。

7顶点3原色例子

1.2 解向量的描述

解向量是一个表示图的各顶点着色情况的 向量 $X = \langle x_1, x_2, \dots, x_n \rangle$。其中：

每个分量 $x_i \in \{1, 2, \dots, m\}$，代表第 $i$ 个顶点的颜色编号。
如果 $x_i = 2$，表示第 $i$ 个顶点着色为第 2 种颜色。

解向量的部分解表示已经为某些顶点选择了颜色。例如，向量 $X = \langle 1, 2, \_, \dots, \_ \rangle$ 表示第一个顶点选了颜色 1，第二个顶点选了颜色 2，而其他顶点尚未着色。

1.3 图着色的算法设计

搜索树：图的着色问题可以建模为一棵 $m$ 叉树。
- 每个节点可以选择 $m$ 种颜色之一进行着色。
约束条件：
- 当处理第 $k+1$ 个顶点时，如果它与部分解中的某些顶点相邻，那么这些已用过的颜色将不再可用。
搜索策略：采用 深度优先搜索（DFS）。
- 如果无法为某个顶点找到合适的颜色，算法会回溯到父节点，尝试其他可能的着色方案。
多米诺性质：
- 如果部分解中某些顶点的着色方案已导致颜色冲突，则继续扩展解是无效的，需要进行回溯。
时间复杂度：
- 图着色问题的时间复杂度主要受以下两个因素影响：

搜索树的大小：
- 搜索树是一棵 $m$ 叉树，共有 $n$ 层（每层代表一个顶点的着色）。
- 最坏情况下，搜索树的叶节点数量为 $m^n$，即 $m$ 的 $n$ 次方。这是因为每个顶点可以选择 $m$ 种颜色。
每个节点的冲突检测：
- 在搜索的过程中，需要判断当前顶点与相邻顶点的颜色是否冲突。
- 冲突检测的时间复杂度为 $O(n)$，因为在最坏情况下，每个顶点都与其他 $n-1$ 个顶点相邻。

因此，总时间复杂度为：

\[O(m^n \cdot n) \]

这是因为我们需要遍历所有 $m^n$ 个节点，并在每个节点进行 $O(n)$ 的冲突检测。

1.4 运行实例

7顶点3色着色实例

示例：七个顶点的图

在本实例中，我们通过一个具体的图着色问题，详细展示其解的搜索和回溯过程。我们使用三种颜色对一个七个顶点的图进行着色，每个顶点都必须满足与邻接顶点颜色不同的约束。

初始设置

输入：无向连通图，7个顶点，使用3种颜色进行着色。
约束条件：每条边连接的两个端点不能使用相同的颜色。
解的表示：使用向量形式 $x_1, x_2, \dots, x_n$，其中每个分量的值代表该顶点所选颜色。

搜索树的构建

这是一个三叉树结构，每个顶点最多可以使用3种颜色，因此每个节点都有最多3个分支。在每个分支上，算法选择当前顶点的一种颜色，然后递归地为下一个顶点着色。

详细着色过程

步骤 1：1号顶点的着色

选择红色作为1号顶点的颜色。

步骤 2：2号顶点的着色

由于2号顶点与1号顶点相邻，不能使用红色。
选择蓝色作为2号顶点的颜色。

步骤 3：3号顶点的着色

3号顶点与2号顶点不相邻，因此可以使用红色。
为3号顶点选择红色。

步骤 4：4号顶点的着色

4号顶点与3号顶点相邻，因此不能使用红色。
为4号顶点选择蓝色。

步骤 5：5号顶点的着色

5号顶点与4号顶点不相邻，因此可以使用红色。
为5号顶点选择红色。

步骤 6：6号顶点的着色

6号顶点与1号、4号、5号顶点相邻。这些顶点已经分别使用了红色和蓝色，因此6号顶点可以使用第三种颜色。

步骤 7：7号顶点的着色

7号顶点与1号、2号、3号、6号顶点相邻。这些顶点已经分别使用了红色和蓝色和灰色，因此7号顶点没有颜色可用。

回溯过程

在回溯时，尝试为5号顶点更换颜色。
为5号顶点选择蓝色，但5号和4号相邻，4号已经使用蓝色，因此五号只能使用灰色。
此时6号顶点与1、4、5号相邻，因为已经使用了三种颜色、则发生冲突，向上回溯直到3号节点、并考虑为4号节点着灰色。

最终解

经过深度优先搜索与回溯调整后，找到一个可行解：
- 1号顶点：红色
- 2号顶点：蓝色
- 3号顶点：红色
- 4号顶点：灰色
- 5号顶点：红色
- 6号顶点：蓝色
- 7号顶点：灰色

1.5 图着色问题中的对称性优化与剪枝示例

在图着色问题的求解过程中，为了提高效率，常常采用对称性优化和剪枝策略。这些技术不仅能减少不必要的搜索，还能显著降低算法的时间复杂度。下面将详细介绍如何在图着色问题中应用这些优化策略，并通过实例展示它们的效果。

搜索树与剪枝策略

1.5.1 对称性优化：减少重复搜索

解的对称性原理

在图着色中，如果两个解仅仅是颜色标签的交换，那么它们本质上是对称解，表示相同的着色方案。比如，对于某个解：
$ \langle 1, 2, 1, 3, 1, 2, 3 \rangle $ 如果将颜色**2与3**对换，得到的解为： $ \langle 1, 3, 1, 2, 1, 3, 2 \rangle $
这两个解实际上表示的是相同的顶点排列，只是颜色标签不同。
因此，只需搜索一个代表性的解，就可以通过颜色的对称交换，生成其余解。这种思路可以显著减少搜索空间。

减少搜索空间的具体方法

以顶点1的颜色选择为基准：
- 当顶点1选择颜色1时，能找到2个对称解。
- 当顶点1选择颜色2时，能找到另外2个对称解。
- 当顶点1选择颜色3时，也会有2个对称解。
总计解的数量：
$ 2 + 2 + 2 = 6 , \text{个解} $
优化后的遍历比例：
- 原本需要遍历三叉树的全部叶子节点，计算复杂度为$ NM^N $。
- 但通过对称性优化，只需遍历总空间的六分之一即可，剩余的解可通过简单的交换生成。

1.5.2 剪枝策略：避免无解分支的遍历

在图着色的回溯过程中，如果某个顶点没有可用颜色，则需要进行回溯。然而，通过合适的剪枝策略，我们可以提前识别并排除无解的分支，避免不必要的搜索。

剪枝示例：识别冲突节点

考虑如下情况：

图的前1、2、3号顶点分别选择了三种不同的颜色：
\[\text{顶点1：红色}, \quad \text{顶点2：蓝色}, \quad \text{顶点3：绿色} \]
这三个顶点都与7号顶点相邻。由于三种颜色已被占用，7号顶点无法选择任何颜色。

提前剪枝的逻辑

如果在某个节点发现其所有相邻顶点已经占用了所有可用颜色，则该节点必然无法着色。这表明该分支不会产生可行解，应立即剪枝，停止该分支的进一步搜索。

1.5.3 剪枝与工作量的权衡

尽管剪枝策略能减少搜索空间，但需要在每一步增加判断邻接节点颜色的计算开销。因此，在实际应用中，需要权衡剪枝的计算成本与遍历空间的成本。

两种方案的权衡

增加判断以减少搜索空间：
- 在每个节点进行邻接关系的判断，以提前剪枝。
- 这种方法减少了后续搜索的工作量，但增加了判断的计算开销。
直接遍历整个搜索空间：
- 如果判断开销过大，直接遍历可能更为高效。
- 在图规模较小时，全面搜索的开销尚在可控范围内，此时无需进行剪枝。

1.5.4 完整的搜索树示例与优化分析

搜索树中的解与剪枝

如图所示的搜索树中，部分分支代表了可行解的路径，而其他分支由于颜色冲突没有解。
对称性优化允许我们在遍历了一个分支后，通过交换颜色标签快速生成其他对称解。
剪枝策略则帮助我们提前识别无解的路径，避免对无解分支的深度搜索。

实例分析：第一层的三种颜色选择

顶点1选择颜色1时，找到2个可行解。
顶点1选择颜色2时，通过对称交换，也能找到2个解。
顶点1选择颜色3时，同样找到2个解。

减少搜索量的效果

总共6个解，只需搜索其中的六分之一即可找到所有解，其余解通过对称性生成。
该策略减少了五分之六的搜索工作量，大大提升了求解效率。

1.6 图着色问题的应用：会场分配问题

1.6.1 问题描述

在会场分配问题中，需要将 $n$ 项活动安排在若干个会场中。对于每对活动 $i$ 和 $j$，如果它们的时间存在冲突，则称这两个活动不相容。目标是在保证每个会场的活动相容的前提下，尽量减少会场的使用数量。

1.6.2 模型构建

我们可以将此问题建模为一个图着色问题：

顶点表示活动：每个活动用一个顶点表示。
边表示冲突关系：如果活动 $i$ 和 $j$ 时间上不相容，则在顶点 $i$ 和 $j$ 之间添加一条边。
会场作为颜色标签：不同颜色表示不同的会场。

1.6.3 求解方法

该问题的求解可转换为图的最小着色问题。目标是找到一种着色方案，使得使用的颜色数最少，即会场数量最小。

着色规则：相邻的两个顶点不能拥有相同的颜色，因为它们表示时间上不相容的活动，不能安排在同一个会场。
最小化颜色数量：在保证相邻顶点颜色不同的前提下，尽量减少使用的颜色数量。

1.6.4 例子分析

假设有 5 个活动需要安排，它们之间的冲突关系如下：

活动 $1$ 与活动 $2$、$3$ 冲突。
活动 $3$ 与活动 $4$ 冲突。
活动 $4$ 与活动 $5$ 冲突。

将上述冲突关系建模成一个图后，图的着色可能如下：

活动 1：红色 (会场 1)
活动 2：蓝色 (会场 2)
活动 3：蓝色 (会场 2)
活动 4：红色 (会场 1)
活动 5：蓝色 (会场 2)

在此例子中，成功使用了 2 种颜色表示 2 个会场，且每个会场中的活动都相容。

1.6.5 优化与应用

优化策略：通过对图的结构分析，可以利用回溯和对称性优化，进一步减少着色过程中的计算量。
实际应用：该模型可以广泛应用于：
- 会场和教室的时间表安排。
- 考试排考表的生成，确保同一时间段内安排在不同教室的考试不会有冲突。
- 会议日程规划，保证时间上有冲突的会议不安排在同一会议室内。

1.6.6 小结

通过将会场分配问题建模为图的最小着色问题，我们能够有效求解如何合理安排活动，并减少会场的使用数量。这种方法为其他类似的组合优化问题提供了参考，通过最小化颜色数量，实现资源的优化配置。

标签：剪枝,颜色,着色,搜索,会场,回溯,解决,顶点
From： https://www.cnblogs.com/cloud-ken/p/18508204

回溯法解决图着色问题

1. 回溯法解决图着色问题 （9.5）