使用计算机给一个看似四色猜想的反例上色

下面这个图中有四个地图,其中图4是一个看起来很像四色猜想的反例的地图。想要手工给图4上色是很困难的,至少对我来说是很困难的。我曾经花费了应该有超过1小时的时间来尝试给这个地图上色,但最终结果是两个相邻区域的颜色相同了。

此图片来源:Matrix67

手工上色失败以后,我就想用电脑进行上色,于是就有了这篇文章。
首先给地图的每一个区域编号,对于这个地图,有110个区域,我就给这些区域编号从1到110(如下图所示,黄色编号表示100以后的编号,比如黄色的5就表示105)。编号完成以后,就手工写出每个区域周围相邻的区域,以便读入程序。虽然说要写110个区域不是个容易的事情,但是总比手工上色要容易得多。于是我用了大约40分钟的时间完成了这个文件。文件的格式是,每一行的第一个数字是区域编号,紧接着是与这个区域相邻的区域的编号(该文件可在本文后下载)。写好这个文件以后,就可以开始写代码了。

因为我的算法水平很低,而时间又有很多,于是就采用暴力算法,打算连续计算几天以得到结果。
算法是这样的,使用递归的方法,给一个区域使用一个颜色进行上色,然后判断这个颜色是否和相邻区域的颜色相同,如果相同则使用下一种颜色。如果使用4种颜色都会与相邻区域颜色相同,则取消该区域的上色,并返回上一个上色的区域,继续使用这样的方法进行处理。
于是程序代码就写出来了,我尝试运行想估计一下大约要多久才能出结果。可没想到根据调试信息,似乎不用多久就能出结果。于是我就等着了。虽然我想可能要等待几个小时,可是才几分钟,程序就停止运行了。我还以为是程序有误,不过一看也有结果输出,于是就试试使用这个结果给地图上色。大约十分钟以后,我把所有的区域都根据计算出来的结果涂上颜色了,没想到这个结果还真是正确的啊。看来虽然是使用暴力算法,对于四色问题来说时间也不算不能接受。
结果如下图,果然计算机是我们的好帮手啊
PS.实际上如果不输出调试信息的话不到1秒就出结果了

程序源代码和输入文件

fourcolor.cfourcolor.in
—–12月24日———–
补上一个流程图,不过这个流程图里面的变量和上面的源码里面的变量名不同

本文发表于 零零散散,并添加了 , , 标记。保存永久链接到书签。

发表评论

电子邮件地址不会被公开。