基于ArcPy的四色地图着色算法研究开题报告

1. 研究目的与意义

?研究背景

地图着色问题一直是困扰人们的问题，“四色猜想”是近代世界数学三大难题之一。1852年英国的制图员francis guthrie在绘制英格兰分郡地图时，发现许多地图都只需要四种颜色染色，这就是“四色猜想”，但他未能证明。本课题研究四色地图的着色算法，利用回溯算法对地图进行四色填充，使相邻区域具有不同的颜色。电子计算机问世以来，由于演算效率提高，加之人机对话的出现，大大加快了对四色猜想的证明的进程。1976年，美国数学家阿佩尔和哈肯与计算机科学家科赫合作，用计算机证明了著名的“四色猜想”，但是当时的情况下，这个算法证明时长打1260小时，其正确性无法用人工证明。尽管如此，人们都默认这一猜想是正确的。具体结论是：在任意无飞地的多边形区域，可以用四种颜色进行着色，并使相邻的多边形具有不同的颜色。

?国内外研究现状

2. 研究内容和预期目标

主要研究内容：

（1）研究回溯算法的思想，对地图的斑块生成邻接矩阵，并利用深度优先遍历的思想对地图着色；

（2）基于arcgis开发平台，利用python语言编程实现四色地图着色的回溯算法，并利用多组矢量数据进行实验验证。本课题可以为各种专题图的制作提供色彩鲜明的底图。

3. 研究的方法与步骤

?地图着色主要研究算法---回溯法

回溯法有“通用的解题法”之称。用它可以系统的搜索一个问题的所有解或任一解。是一个既带有系统性又带有跳跃性的搜索算法。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。在用回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率。其一是用约束函数在扩展结点处剪去不满足约束的子树；其二是用限界函数剪去不能得到最优解得子树。这两类函数统称剪枝函数。

运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间

4. 参考文献

[1]王青平,陈琳,林岩钊,等.基于matlab的四色地图自动生成[j].测绘与空间地理信息, 2014, 37(2): 22-24.

[2]乔永利,王建强,胥海滨.深度优先搜索的地图着色算法[j].测绘科学, 2011, 36(5): 175-176.

[3]朱安平.一种平面图四着色算法及其实现[j].硅谷, 2011, 7: 100-101.

5. 计划与进度安排

（1）接受任务，内容理解，指导教师讲解、讨论、阅读指导教师规定的文献，撰写开题报告（2022.3.26-2022.3.30）；

（2）收集相关参数，通过网络、期刊、报纸、书籍进行相关资料搜集（2022.3.31-2022.4.6）；

（3） 四色地图回溯算法实现：基于arcgis平台，利用python语言编程实现四色地图回溯算法，构建原型系统（2022.4.7-2022.4.20）；