回溯法解决地图填色问题

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。

相关文章

springboot循环依赖问题案例代码及解决办法

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖（即BeanA依赖BeanB,而BeanB又依赖BeanA）,会导致Spring的... 目录1. 什么是循环依赖？2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1：使用 @La
阅读更多...
Spring事务中@Transactional注解不生效的原因分析与解决

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3
阅读更多...
mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言：第一步：第二步：第三步：总结：前言：当你想通过命令窗口想打开mysql时候发现提http://www.cpp
阅读更多...
SpringBoot启动报错的11个高频问题排查与解决终极指南

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突：NoSuchMethodError 的终极解法2. Bean注入失败：No qu
阅读更多...
springboot报错Invalid bound statement (not found)的解决

springboot报错Invalid bound statement (not found)的解决

《springboot报错Invalidboundstatement(notfound)的解决》本文主要介绍了springboot报错Invalidboundstatement(not... 目录一. 问题描述二.解决问题三. 添加配置项 四.其他的解决方案4.1 Mapper 接口与 XML 文件不匹配
阅读更多...
MySQL新增字段后Java实体未更新的潜在问题与解决方案

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更（如新增字段）后,开发人员可... 目录引言1. 问题背景：数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作
阅读更多...
Python中ModuleNotFoundError: No module named ‘timm’的错误解决

Python中ModuleNotFoundError: No module named ‘timm’的错误解决

《Python中ModuleNotFoundError:Nomodulenamed‘timm’的错误解决》本文主要介绍了Python中ModuleNotFoundError:Nomodulen... 目录一、引言二、错误原因分析三、解决办法1.安装timm模块2. 检查python环境3. 解决安装路径问题
阅读更多...
如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》：本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错
阅读更多...
如何解决Spring MVC中响应乱码问题

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》：本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解
阅读更多...
Java报NoClassDefFoundError异常的原因及解决

Java报NoClassDefFoundError异常的原因及解决

《Java报NoClassDefFoundError异常的原因及解决》在Java开发过程中,java.lang.NoClassDefFoundError是一个令人头疼的运行时错误,本文将深入探讨这一问... 目录一、问题分析二、报错原因三、解决思路四、常见场景及原因五、深入解决思路六、预http://www
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2