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

黃仁帥

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

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

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