• m 叉树深度搜索解决地图着色问题


    一 问题描述

    给定无向连接图 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 叉树。

    二 算法设计

    1 定义问题的解空间

    问题的解空间为{x1,x2,x3...xn,}

    2 确定解空间的组织结构

    问题的解空间组织结构是一棵满 m 叉树,树的深度为 n。

    3 搜索解空间

    3.1 约束条件

    例如,假设当前扩展节点 z 在第 4 层,则说明前 3 个节点的色号已经确定,如下图所示。

    在前 3 个已着色的节点中,节点 4 与节点1、3 有边相连,那么节点 4 的色号不可以与节点 1、3 的色号相同。

    3.2 限界条件

    因为只找可行解就可以了,不是求最优解,因此不需要限界条件。

    3.3 搜索过程

    扩展节点沿着第 1 个分支扩展,判断约束条件,如果满足,则进入深一层继续搜索;如果不满足,则扩展生成的节点被剪掉,换下一个色号尝试。如果所有的色号都尝试完毕,则该节点变成死节点,向上回溯到离其最近的活节点,继续搜索,搜索到叶子节点时,找到一种着色方案。搜索到全部活节点变成死节点为止。

    三 图解

    原始图

    1 开始搜索第 1 层

    2 扩展节点 B

    3 扩展节点 C

    4 扩展节点 D

    5 扩展节点 E

    6 扩展节点 F

    7 扩展节点 G

    8 扩展节点 H,无法再扩展,找到一个可行解,输出该可行解{1,2,3,2,1,2,3}。回溯到最近的活节点 G。

    9 重新扩展节点 G。节点 G 的 3 个孩子均已考察完毕,成为死节点,回溯到最近的活节点 F。

    10 继续搜索,又找到第 2 种着色方案,输出该可行解{1,3,2,3,1,3,2}。搜索过程和着色方案如下。

    11 继续搜索,又找到 4 个可行解,分别是{2,1,3,1,2,1,3}、{2,3,1,3,2,3,1}、{3,1,2,1,3,1,2}、{3,2,1,2,3,2,1}。

    四 算法实现说明

    1 约束函数

    假设当前扩展节点处于解空间的第 t 层,那么从 1 个节点到第 t-1 个节点状态(着色的色号)已经确定。接下来沿着扩展节点的第 1 个分支进行扩展,此时需要判断第 t 个节点的着色情况。第 t 个节点的着色情况要与前 t-1 个节点中与其有边相连的节点颜色不同,如果有一个颜色相同的,则第 t 个节点不能用这个色号,换下一个色号尝试,如下图所示。

    2 按约束条件搜素求解

    t 表示当前扩展节点在第 t 层。如果 t>n,则表示已经到达叶子,sum 累计第几个着色方案,输出可行解。否则,扩展节点沿着第 1 个分支扩展,判断是否满足约束条件,如果满足,则进入深一层继续搜索;如果不满足,则扩展生成的节点被剪掉,换下一个色号尝试。如果所有色号都尝试完毕,则该节点变成死节点,向上回溯到离其最近的活节点,继续搜索。搜索到叶子时,找到一种着色方案。搜素到全部活节点都变成死节点为止。

    五 代码

    1. package com.platform.modules.alg.alglib.p923;
    2. public class P923 {
    3. public String output = "";
    4. private int n, m;
    5. private int a = 1, b = 1;
    6. int sum = 0;
    7. int graph[][] = new int[20][20];
    8. int color[] = new int[20];
    9. public String cal(String input) {
    10. String[] line = input.split("\n");
    11. String[] word = line[0].split(" ");
    12. n = Integer.parseInt(word[0]);
    13. m = Integer.parseInt(word[1]);
    14. for (int i = 1; i < line.length; i++) {
    15. String[] connection = line[i].split(" ");
    16. graph[Integer.parseInt(connection[0])][Integer.parseInt(connection[1])] = 1;
    17. graph[Integer.parseInt(connection[1])][Integer.parseInt(connection[0])] = 1;
    18. }
    19. backtrack(1);
    20. output += sum;
    21. return output;
    22. }
    23. boolean ok(int c) {
    24. for (int k = 1; k <= n; k++) {
    25. if (graph[c][k] == 1 && color[c] == color[k]) {
    26. return false;
    27. }
    28. }
    29. return true;
    30. }
    31. void backtrack(int cur) {
    32. if (cur > n) {
    33. for (int i = 1; i <= n; i++) {
    34. output += color[i] + " ";
    35. }
    36. sum++;
    37. output += "\n";
    38. } else {
    39. for (int i = 1; i <= m; i++) {
    40. color[cur] = i;
    41. if (ok(cur)) {
    42. backtrack(cur + 1);
    43. }
    44. color[cur] = 0;
    45. }
    46. }
    47. }
    48. }

    六 测试

    1 输入

    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

    2 输出

  • 相关阅读:
    华为欧拉系统安装
    SSM+网上订餐系统 毕业设计-附源码221558
    Chrome 配置samesite=none方式
    博客园商业化之路-众包平台:500位驭码好汉,等你来发单挑战
    Java中类的方法重载和方法重写
    mysql面试题6:MySQL索引的底层原理,是如何实现的?B+树和B树的区别?
    java毕业生设计忆居民宿管理计算机源码+系统+mysql+调试部署+lw
    ES13 新增特性
    《计算机视觉技术与应用》-----第五章 边缘和轮廓
    如何使用 apt-get 安装特定版本的软件包
  • 原文地址:https://blog.csdn.net/chengqiuming/article/details/126315969