回溯法解决地图填色问题

2023-12-07 13:10
文章标签 问题 解决 地图 回溯 填色

本文主要是介绍回溯法解决地图填色问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

回溯法

最大度优先

最少可选颜色优先

向前探测

随机产生不同规模的图，分析算法效率与图规模的关系（四色）

回溯法

回溯法的基本思想是采用递归和深度优先搜索的方法，尝试在一组可能的解中搜索出符合要求的解，在搜索过程中，若发现当前所选的方案不能得到正解，就回溯到前面的某一步（即撤销上一次的选择），换一种可能性继续尝试，直到找到符合要求的解或者所有的可能性都已尝试完毕。

在地图填色中，回溯法从某一区域开始，如图4所示，尝试使用不同的颜色进行填充，然后递归地尝试填充相邻的区域，如果发现当前填充颜色与相邻区域的颜色冲突，则回溯到之前的状态重新选择一种颜色进行填充，如此往复直到所有的区域都被填充上颜色或者无解。

图4 回溯法地图填色示例

伪代码

C++代码 

#include<iostream>
#include<fstream>
#include<chrono>
#include<sstream>using namespace std;
void fillColor(const int);
int map[450][450] = {0};
int color[450] = {0};
const int colorNumber = 4;
int vertexNumber = 0;
int edgeNumber = 0;
int solution = 0;
int done=0;
fstream file("C:\\Users\\Yezi\\Desktop\\C++\\MapColoring\\Map\\le9_4.txt");
string line, word;int main() {if (!file.is_open()) {cout << "File error.\n";return 1;}getline(file, line);istringstream iss(line);iss >> word >> word >> vertexNumber >> edgeNumber;int head, tail;for (int i = 0; i < edgeNumber; i++) {getline(file, line);istringstream ISS(line);ISS >> word >> head >> tail;map[tail - 1][head - 1] = map[head - 1][tail - 1] = 1;}auto start = chrono::high_resolution_clock::now();fillColor(0);auto end = chrono::high_resolution_clock::now();auto consume = chrono::duration_cast<chrono::milliseconds>(end - start);cout << "There is " << solution << " solutions.\n" << "The time consumed is " << consume.count()<< " ms.\n";return 0;
}bool conflict(const int &vertex) {for (int i = 0; i < vertexNumber; i++) {if (map[vertex][i] && color[vertex] == color[i])return true;}return false;
}void fillColor(const int vertex) {if(done==vertexNumber){solution++;for(int i=0;i<vertexNumber;i++)cout<<color[i]<<' ';cout<<endl;return;}for(int i=1;i<=colorNumber;i++){color[vertex]=i;if(!conflict(vertex)){done++;fillColor(vertex + 1);done--;}color[vertex]=0;}
}

运行结果

如图5所示，对于小规模地图，回溯法成功在323毫秒内找出480个解，并将每个解打印出来，验证了算法的正确性。

图5 回溯法小规模地图填色

对附件中给定的地图数据填涂；

首先还是用经典回溯法试跑一下，只找一个解的情况，如表1所示。

表1 经典回溯法大规模地图填色

由结果可以看出，当规模大时，回溯法的搜索空间会变得非常庞大，从而需要耗费大量的时间和内存资源来完成搜索过程，这将导致算法的运行时间呈指数级增长，短时间内无法求解。因此，我们需要对回溯法进行优化。

最大度优先

经典回溯法的问题在于解的空间太大，回溯次数太多，而优先选择邻边个数最多的顶点进行填色则会对剩下未填色的顶点产生更多的限制，从而减少回溯的次数，如图6所示，每次填色，我们都优先填度最大的区域。

图6 最大度优先地图填色示例

伪代码

C++代码 

#include<iostream>
#include<fstream>
#include<chrono>
#include<sstream>using namespace std;
struct Vertex{int degree=0;int place;
}vertex[450];
void fillColor(const int);
int map[450][450] = {0};
int color[450] = {0};
const int colorNumber = 15;
int vertexNumber = 0;
int edgeNumber = 0;
int solution = 0;
int done=0;
fstream file("C:\\Users\\Yezi\\Desktop\\C++\\MapColoring\\Map\\le450_15b.txt");
string line, word;int main() {if (!file.is_open()) {cout << "File error.\n";return 1;}getline(file, line);istringstream iss(line);iss >> word >> word >> vertexNumber >> edgeNumber;int head, tail;for (int i = 0; i < edgeNumber; i++) {getline(file, line);istringstream ISS(line);ISS >> word >> head >> tail;map[tail - 1][head - 1] = map[head - 1][tail - 1] = 1;}for(int i=0;i<vertexNumber;i++){vertex[i].place=i;for(int j=0;j<vertexNumber;j++){vertex[i].degree+=map[i][j];}}sort(vertex,vertex+vertexNumber,[](const Vertex&a,const Vertex&b){return a.degree>b.degree;});auto start = chrono::high_resolution_clock::now();fillColor(0);auto end = chrono::high_resolution_clock::now();auto consume = chrono::duration_cast<chrono::milliseconds>(end - start);cout << "We had found " << solution << " solutions.\n" << "The time consumed is " << consume.count()<< " ms.\n";return 0;
}bool conflict(const int &vertexIndex) {for (int i = 0; i < vertexNumber; i++) {if (map[vertexIndex][i] && color[vertexIndex] == color[i])return true;}return false;
}void fillColor(const int vertexIndex) {if(done==vertexNumber){solution++;return;}for(int i=1;i<=colorNumber;i++){color[vertex[vertexIndex].place]=i;if(!conflict(vertex[vertexIndex].place)){done++;fillColor(vertexIndex + 1);if(solution>0)return;done--;}color[vertex[vertexIndex].place]=0;}
}

运行结果

先在小规模地图上验证算法的正确性，如图7所示，最大度优先可以在325毫秒内找出480个解。

图7 最大度优先小规模地图填色

然后尝试填涂三个大规模地图，只找一个解的情况，如表2所示。

表2 最大度优先大规模地图填色

由结果可知，我们的最大度优先优化策略略显成效，但是第一个和第二个地图还是无法在短时间内找到解，我们需要继续努力。

最少可选颜色优先

每次选择区域进行填色时优先选择剩余可用颜色最少的区域进行填色，这样可以减少剩余可用颜色最多的地区需要尝试不同颜色的次数，如图8所示，每填完一个区域就更新邻近区域的可选颜色，然后优先选择可选颜色最少的区域进行填色。

图8 最少可选颜色优先地图填色示例

伪代码

C++代码 

#include<iostream>
#include<fstream>
#include<chrono>
#include<sstream>
#include<vector>
using namespace std;
void fillColor(const int);
int map[450][450] = {0};
int color[450] = {0};
const int colorNumber = 25;
bool colorAccess[450][colorNumber+1];
int degree[450]={0};
int colorAccessNumber[450];
int vertexNumber = 0;
int edgeNumber = 0;
int solution = 0;
int done=0;
fstream file("C:\\Users\\Yezi\\Desktop\\C++\\MapColoring\\Map\\le450_25a.txt");
string line, word;int main() {if (!file.is_open()) {cout << "File error.\n";return 1;}getline(file, line);istringstream iss(line);iss >> word >> word >> vertexNumber >> edgeNumber;int head, tail;for (int i = 0; i < edgeNumber; i++) {getline(file, line);istringstream ISS(line);ISS >> word >> head >> tail;map[tail - 1][head - 1] = map[head - 1][tail - 1] = 1;}for(int i=0;i<vertexNumber;i++){for(int j=1;j<=colorNumber;j++)colorAccess[i][j]= true;for(int j=0;j<vertexNumber;j++)degree[i]+=map[i][j];}auto start = chrono::high_resolution_clock::now();fillColor(0);auto end = chrono::high_resolution_clock::now();auto consume = chrono::duration_cast<chrono::milliseconds>(end - start);cout << "There is " << solution << " solutions.\n" << "The time consumed is " << consume.count()<< " ms.\n";return 0;
}bool conflict(const int &vertex) {for (int i = 0; i < vertexNumber; i++) {if (map[vertex][i] && color[vertex] == color[i])return true;}return false;
}
int MRV(const int vertex,vector<int>&MRVRecover){for(int i=0;i<vertexNumber;i++){if(map[vertex][i]){if(colorAccess[i][color[vertex]]){MRVRecover.push_back(i);colorAccess[i][color[vertex]]= false;}}}int next=0;int minColor=colorNumber;for(int i=0;i<vertexNumber;i++){colorAccessNumber[i]=0;for(int j=1;j<=colorNumber;j++){if(colorAccess[i][j])colorAccessNumber[i]++;}if(minColor>colorAccessNumber[i]&&color[i]==0){minColor=colorAccessNumber[i];next=i;}}return next;
}
void MRV_Recover(const int vertex,vector<int>&MRVRecover){for(auto&it:MRVRecover){colorAccess[it][color[vertex]]= true;}
}
void fillColor(const int vertex) {if(done==vertexNumber){solution++;
//        for(int i=0;i<vertexNumber;i++)
//            cout<<color[i]<<' ';
//        cout<<endl;return;}for(int i=1;i<=colorNumber;i++){color[vertex]=i;if(!conflict(vertex)){done++;vector<int>MRVRecover;int next= MRV(vertex,MRVRecover);fillColor(next);if(solution>0)return;MRV_Recover(vertex,MRVRecover);done--;}color[vertex]=0;}
}

运行结果

先在小规模地图上验证算法的正确性，如图9所示，可以在321毫秒内找出480个解。

图9 最少可选颜色小规模地图填色

然后尝试填涂三个大规模地图，结果如表3所示

表3 最少可选颜色优先大规模地图填色

由结果可知，最少可选颜色优先的优化策略使得第一个图也可以在2秒内找到解了，通过算法的优化，原本短时间内无解的问题可以迅速解决。

然后我们尝试将最大度优先和最少可选颜色优先结合去填涂三个大规模地图，结果如表4所示。

表4 最少可选颜色+最大度地图填色

由结果可知，将最少可选颜色优先和最大度优先相结合后，三个地图均可以迅速找到解，其中第一个地图需要600毫秒，而第二个地图在3秒内终于找到了一个解。

继续测试，对第一个地图找全部解，对第二个和第三个地图找10万个解，结果如表5所示，可知该优化策略可以迅速找解。

表5 最少可选颜色+最大度找多解

向前探测

每次选择区域进行填色的时候，先判断该填涂的颜色是否会导致邻近的区域无色可填，如果导致了邻近区域无色可填则直接换一种颜色填涂，如图10所示，每填一个区域就更新邻近区域的可用颜色，如果可用颜色为0则说明此处不能填这个颜色，进行剪枝。

图10 向前探测地图填色示例

伪代码

C++代码 

#include<iostream>
#include<fstream>
#include<chrono>
#include<sstream>
#include<vector>
using namespace std;
void fillColor(const int);
int map[450][450] = {0};
int color[450] = {0};
const int colorNumber = 5;
bool colorAccess[450][colorNumber+1];
int colorAccessNumber[450];
int vertexNumber = 0;
int edgeNumber = 0;
int solution = 0;
int done=0;
fstream file("C:\\Users\\Yezi\\Desktop\\C++\\MapColoring\\Map\\le450_5a.txt");
string line, word;int main() {if (!file.is_open()) {cout << "File error.\n";return 1;}getline(file, line);istringstream iss(line);iss >> word >> word >> vertexNumber >> edgeNumber;int head, tail;for (int i = 0; i < edgeNumber; i++) {getline(file, line);istringstream ISS(line);ISS >> word >> head >> tail;map[tail - 1][head - 1] = map[head - 1][tail - 1] = 1;}for(int i=0;i<vertexNumber;i++){for(int j=1;j<=colorNumber;j++)colorAccess[i][j]= true;}auto start = chrono::high_resolution_clock::now();fillColor(0);auto end = chrono::high_resolution_clock::now();auto consume = chrono::duration_cast<chrono::milliseconds>(end - start);cout << "There is " << solution << " solutions.\n" << "The time consumed is " << consume.count()<< " ms.\n";return 0;
}bool conflict(const int &vertex) {for (int i = 0; i < vertexNumber; i++) {if (map[vertex][i] && color[vertex] == color[i])return true;}return false;
}void FC_Recover(const int vertex,vector<int>&FCRecover){for(auto&it:FCRecover){colorAccess[it][color[vertex]]= true;}
}
bool FC(const int vertex,vector<int>&FCRecover){for(int i=0;i<vertexNumber;i++){if(map[vertex][i]){if(colorAccess[i][color[vertex]]){FCRecover.push_back(i);colorAccess[i][color[vertex]]= false;}}}for(int i=0;i<vertexNumber;i++){colorAccessNumber[i]=0;for(int j=1;j<=colorNumber;j++){if(colorAccess[i][j])colorAccessNumber[i]++;}if(colorAccessNumber[i]==0&&color[i]==0){FC_Recover(vertex,FCRecover);return false;}}return true;
}
void fillColor(const int vertex) {if(done==vertexNumber){solution++;
//        for(int i=0;i<vertexNumber;i++)
//            cout<<color[i]<<' ';
//        cout<<endl;return;}for(int i=1;i<=colorNumber;i++){color[vertex]=i;vector<int>FCRecover;if(!conflict(vertex)&&FC(vertex,FCRecover)){done++;fillColor(vertex+1);if(solution>0)return;done--;FC_Recover(vertex,FCRecover);}color[vertex]=0;}
}

运行结果

先在小规模地图上验证算法的正确性，如图11所示，可以在412毫秒内找出480个解。

图11 向前探测小规模地图填色

然后尝试填涂三个大规模地图，结果如表6所示。

表6 向前探测大规模地图填色

由结果可知，单纯的向前探测无法在短时间内找出三个地图的解，下面我们将向前探测和最大度优先结合起来，填涂三个大规模地图，结果如表7所示。

表7 向前探测+最大度地图填色

再加上最少可选颜色优先，填涂三个大地图，结果如表8所示。

表8 向前探测+最少可选颜色+最大度地图填色

对第一个地图找全部解，对第二个和第三个地图找10万个解，结果如表9所示。

表9 向前探测+最少可选颜色+最大度找多解

由此可知，与最大度优先和最少可选颜色优先相比，向前探测的优化效果不是特别明显。

随机产生不同规模的图，分析算法效率与图规模的关系（四色）

（1）固定边

固定图的边数为1000条边，然后随机生成顶点数为100到1000的平面图，测试多组数据取众数，结果如图12所示。

图12 固定边为1000不同顶点数的地图填色

具体数据如表10所示。

表10 固定边为1000不同顶点数的地图填色

由结果可知，边数固定的情况，顶点数越多，消耗的时间和资源也更多，解的搜索空间变大，搜索时间更长。

（2）固定点

固定图的顶点数为100，随机生成边数为100到1000的平面图，测试多组数据取众数，结果如图13所示。

图13 固定点为100不同边数的地图填色

具体数据如表10所示。

表10 固定点为100不同边数的地图填色

由结果分析，算法执行的时间先是随着边数的增加而增加，这是因为解的搜索空间增加了，而后当边数达到一定程度，边密度越大，图变得更加复杂，可选的颜色减少，算法剪枝的效率更高，所以搜索效率会更高。

这篇关于回溯法解决地图填色问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/466005。

相关文章

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题：墙体两侧特征混淆误匹配，导致建图和定位偏差，表现为过门跳变、外月台走歪等 ·解决思路：预期的根治方案IGICP需要较长时间完成上线，先使用切分地图的工程化方案，即墙体两侧切分为不同地图，在某一侧只使用该侧地图进行定位 方案思路 切分原理：切分地图基于关键帧位置，而非点云。 理论基础：光照是直线的，一帧点云必定只能照射到墙的一侧，无法同时照到两侧实践考虑：关
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
如何解决线上平台抽佣高 线下门店客流少的痛点！

如何解决线上平台抽佣高 线下门店客流少的痛点！

目前，许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流，但其费用昂贵。鉴于此，众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台，但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下，商家之间的合作网络逐渐成为一种有效的解决方案，通过资源和客户基础的共享，实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例，该平台融合了环保消费积分系统，在短
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
缓存雪崩问题

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库，瞬间耗尽数据库资源，导致数据库无法使用。 解决方案： 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内，大量缓存数据同时失效，导致所有请求直接涌向数据库，瞬间增加数据库的负载压力，可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
pip-tools：打造可重复、可控的 Python 开发环境，解决依赖关系，让代码更稳定

pip-tools：打造可重复、可控的 Python 开发环境，解决依赖关系，让代码更稳定

在 Python 开发中，管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等，都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools？ pip-tools 是一组命令行工具，旨在简化 Python 依赖关系的管理，确保项目环境的稳定性和可重复性。它主要包含两个核心工具：pip-compile 和 pip
阅读更多...
【VUE】跨域问题的概念，以及解决方法。

【VUE】跨域问题的概念，以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略，该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同，则需要服务器显式地允许这种跨域请求。一般在springbo
阅读更多...
题目1254：N皇后问题

题目1254：N皇后问题

题目1254：N皇后问题 时间限制：1 秒 内存限制：128 兆 特殊判题：否 题目描述： N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。 你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2