模拟退火算法思想在求解四色问题中的应用

黄仁帅

摘 要：四色问题又称四色猜想，是世界近代三大数学难题之一。对四色问题的研究，促进了一系列数学新思维的产生，为推动数学的发展起到了重要的作用。模拟退火算法是求解复杂工程问题的重要算法之一。文章基于模拟退火算法的思想，结合四色问题的特殊性，给出了一种求解四色问题的快速算法。

关键词：模拟退火；四色问题；智能算法

中图分类号：O29 文献标志码：A 文章编号：2095-2945（2018）24-0164-02

Abstract： The four-color problem， also known as the four-color conjecture， is one of the three modern mathematical problems in the world. The research on the four-color problem promotes a series of new mathematical thinking and plays an important role in promoting the development of mathematics. Simulated annealing is one of the most important algorithms for solving complex engineering problems. Based on the idea of simulated annealing algorithm and the particularity of the four-color problem， a fast algorithm for solving the four-color problem is presented in this paper.

Keywords： simulated annealing； four-color problem； intelligent algorithm

1 概述

四色问题又称四色猜想， 是世界近代三大数学难题之一。1852年，G.Frederick在从事地图着色工作时发现的一个现象，即“每幅地图都可以用四种颜色着色， 使得有共同边界的国家被染上不同的颜色”。四色问题从诞生开始，就因其简单的外表而神秘的内涵，引起无数数学家的研究兴趣。但直至1976年，才由Appel与Haken借助计算机给出一个并不十分完善的机器证明[1]，期间整整经历了一个多世纪。时至今日，虽然四色问题的正确性已经得到数学界公认，但对其非计算机证明的研究仍不得其解。而正是由于数学家对该问题非计算机证明的不懈探索，发展出了浩瀚的图的染色体理论，极大的促进了图论的发展。

模拟退火算法（Simulated Annea-ling， SA）的思想来源于固体退火原理，于1953年由N. Metropolis等人最先提出。经过半个多世纪的研究改进，目前已在生产调度、机器学习、信号处理等工程领域中得到了广泛应用。近年来，众多学者围绕四色图问题的数值计算方法展开了研究，得到了许多不同的计算方法[2-4]。而在众多算法中，模擬退火算法是求解四色图问题的有效算法之一。

2 算法设计

基于模拟退火算法的思想，针对四色图问题的特殊性，设计求解四色图问题的快速算法。

2.1 地图模型的构建

以10个连续地区着色问题为例，其简化地图如图1，每个顶点表示一个地区，每根连线代表这两个地区相邻。

3 实验结果

在MATLAB下进行编程实验，计算邻接矩阵为Vk时获得100个可行着色方案的总时间（s），获得每个可行着色方案的平均时间（s），运行结果如下（表2）。

当问题的规模n=160时，计算获得100个可行着色方案需花费大量时间，最后只统计获得一个可行方案的时间。另外，由于算法具有一定的随机性，故上述时间只是一个参考值。

4 结束语

本文基于模拟退火算法的思想，设计了一种求解四色图问题新的快速算法，实验表明新算法是可行有效的. 同时，随着问题规模的增大，每次计算所花费的时间也在不断的增加，希望在以后的研究中能加以改进。

参考文献：

[1]AppelK， Haken W. The Solution of the Four-color-map Problem[J]. Scientific American，1997，10：108-121.

[2]宋宇航.基于混沌神经网络的四色图解法研究与优化[D].哈尔滨理工大学，2011.

[3]火善栋.用遗传算法实现四色图问题[J].计算机时代，2015（3）：56-57.

[4]王宁.应用模拟退火算法求解四色图问题[J].电脑迷，2016（7）：178.