给定无向连接图 G 和 m 种颜色,找出所有不同的着色方案,使相邻的区域有不同的颜色。如果把地图上的每一个区域都退化为一个点,将相邻的区域用线连接起来,地图就变成一个无向连通图,给地图着色相对于给该无向连通图的每个点都着色,要求有连线的点不能有相同的颜色,这就是图的 m 着色问题。
该地图有 7 个区域,分别是 A、B、C、D、E、F、G,按上面的顺序编号1~7,对每个区域都用一个节点表示,相邻的区域有连线,地图就转化成一个无向连通图,如下图所示。
如果用 3 种颜色给该地图着色,那么该问题中每个节点所有着的颜色均有 3 种选择,7 个节点所有颜色组成是一个可能解,例如{1,2,3,2,1,2,3}。
每个节点都有 m 种选择,即在解空间树中每个节点都有 m 个分支,称为 m 叉树。
问题的解空间为{x1,x2,x3...xn,}
问题的解空间组织结构是一棵满 m 叉树,树的深度为 n。
3.1 约束条件
例如,假设当前扩展节点 z 在第 4 层,则说明前 3 个节点的色号已经确定,如下图所示。
在前 3 个已着色的节点中,节点 4 与节点1、3 有边相连,那么节点 4 的色号不可以与节点 1、3 的色号相同。
3.2 限界条件
因为只找可行解就可以了,不是求最优解,因此不需要限界条件。
3.3 搜索过程
扩展节点沿着第 1 个分支扩展,判断约束条件,如果满足,则进入深一层继续搜索;如果不满足,则扩展生成的节点被剪掉,换下一个色号尝试。如果所有的色号都尝试完毕,则该节点变成死节点,向上回溯到离其最近的活节点,继续搜索,搜索到叶子节点时,找到一种着色方案。搜索到全部活节点变成死节点为止。
原始图
假设当前扩展节点处于解空间的第 t 层,那么从 1 个节点到第 t-1 个节点状态(着色的色号)已经确定。接下来沿着扩展节点的第 1 个分支进行扩展,此时需要判断第 t 个节点的着色情况。第 t 个节点的着色情况要与前 t-1 个节点中与其有边相连的节点颜色不同,如果有一个颜色相同的,则第 t 个节点不能用这个色号,换下一个色号尝试,如下图所示。
t 表示当前扩展节点在第 t 层。如果 t>n,则表示已经到达叶子,sum 累计第几个着色方案,输出可行解。否则,扩展节点沿着第 1 个分支扩展,判断是否满足约束条件,如果满足,则进入深一层继续搜索;如果不满足,则扩展生成的节点被剪掉,换下一个色号尝试。如果所有色号都尝试完毕,则该节点变成死节点,向上回溯到离其最近的活节点,继续搜索。搜索到叶子时,找到一种着色方案。搜素到全部活节点都变成死节点为止。
- package com.platform.modules.alg.alglib.p923;
-
- public class P923 {
- public String output = "";
- private int n, m;
- private int a = 1, b = 1;
- int sum = 0;
- int graph[][] = new int[20][20];
- int color[] = new int[20];
-
- public String cal(String input) {
- String[] line = input.split("\n");
- String[] word = line[0].split(" ");
- n = Integer.parseInt(word[0]);
- m = Integer.parseInt(word[1]);
- for (int i = 1; i < line.length; i++) {
- String[] connection = line[i].split(" ");
- graph[Integer.parseInt(connection[0])][Integer.parseInt(connection[1])] = 1;
- graph[Integer.parseInt(connection[1])][Integer.parseInt(connection[0])] = 1;
- }
- backtrack(1);
- output += sum;
- return output;
- }
-
- boolean ok(int c) {
- for (int k = 1; k <= n; k++) {
- if (graph[c][k] == 1 && color[c] == color[k]) {
- return false;
- }
- }
- return true;
- }
-
- void backtrack(int cur) {
- if (cur > n) {
- for (int i = 1; i <= n; i++) {
- output += color[i] + " ";
- }
- sum++;
- output += "\n";
- } else {
- for (int i = 1; i <= m; i++) {
- color[cur] = i;
- if (ok(cur)) {
- backtrack(cur + 1);
- }
- color[cur] = 0;
- }
- }
- }
- }
7 3
1 2
1 3
1 4
2 3
2 5
3 4
3 5
4 5
4 7
5 6
5 7
6 7