黃仁帥

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

關(guān)鍵詞：模擬退火；四色問(wèn)題；智能算法

中圖分類號(hào)：O29 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 概述

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

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

2 算法設(shè)計(jì)

基于模擬退火算法的思想，針對(duì)四色圖問(wèn)題的特殊性，設(shè)計(jì)求解四色圖問(wèn)題的快速算法。

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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