模擬退火算法思想在求解四色問題中的應用

黃仁帥

摘 要：四色問題又稱四色猜想，是世界近代三大數(shù)學難題之一。對四色問題的研究，促進了一系列數(shù)學新思維的產(chǎn)生，為推動數(shù)學的發(fā)展起到了重要的作用。模擬退火算法是求解復雜工程問題的重要算法之一。文章基于模擬退火算法的思想，結(jié)合四色問題的特殊性，給出了一種求解四色問題的快速算法。

關鍵詞：模擬退火；四色問題；智能算法

中圖分類號：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 概述

四色問題又稱四色猜想， 是世界近代三大數(shù)學難題之一。1852年，G.Frederick在從事地圖著色工作時發(fā)現(xiàn)的一個現(xiàn)象，即“每幅地圖都可以用四種顏色著色， 使得有共同邊界的國家被染上不同的顏色”。四色問題從誕生開始，就因其簡單的外表而神秘的內(nèi)涵，引起無數(shù)數(shù)學家的研究興趣。但直至1976年，才由Appel與Haken借助計算機給出一個并不十分完善的機器證明[1]，期間整整經(jīng)歷了一個多世紀。時至今日，雖然四色問題的正確性已經(jīng)得到數(shù)學界公認，但對其非計算機證明的研究仍不得其解。而正是由于數(shù)學家對該問題非計算機證明的不懈探索，發(fā)展出了浩瀚的圖的染色體理論，極大的促進了圖論的發(fā)展。

模擬退火算法（Simulated Annea-ling， SA）的思想來源于固體退火原理，于1953年由N. Metropolis等人最先提出。經(jīng)過半個多世紀的研究改進，目前已在生產(chǎn)調(diào)度、機器學習、信號處理等工程領域中得到了廣泛應用。近年來，眾多學者圍繞四色圖問題的數(shù)值計算方法展開了研究，得到了許多不同的計算方法[2-4]。而在眾多算法中，模擬退火算法是求解四色圖問題的有效算法之一。

2 算法設計

基于模擬退火算法的思想，針對四色圖問題的特殊性，設計求解四色圖問題的快速算法。

2.1 地圖模型的構(gòu)建

以10個連續(xù)地區(qū)著色問題為例，其簡化地圖如圖1，每個頂點表示一個地區(qū)，每根連線代表這兩個地區(qū)相鄰。

3 實驗結(jié)果

在MATLAB下進行編程實驗，計算鄰接矩陣為Vk時獲得100個可行著色方案的總時間（s），獲得每個可行著色方案的平均時間（s），運行結(jié)果如下（表2）。

當問題的規(guī)模n=160時，計算獲得100個可行著色方案需花費大量時間，最后只統(tǒng)計獲得一個可行方案的時間。另外，由于算法具有一定的隨機性，故上述時間只是一個參考值。

4 結(jié)束語

本文基于模擬退火算法的思想，設計了一種求解四色圖問題新的快速算法，實驗表明新算法是可行有效的. 同時，隨著問題規(guī)模的增大，每次計算所花費的時間也在不斷的增加，希望在以后的研究中能加以改進。

參考文獻：

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

[2]宋宇航.基于混沌神經(jīng)網(wǎng)絡的四色圖解法研究與優(yōu)化[D].哈爾濱理工大學，2011.

[3]火善棟.用遺傳算法實現(xiàn)四色圖問題[J].計算機時代，2015（3）：56-57.

[4]王寧.應用模擬退火算法求解四色圖問題[J].電腦迷，2016（7）：178.