高 勇，李存華

（淮海工學(xué)院 計算機(jī)工程學(xué)院，江蘇 連云港 222005）

0 引言

一個圖，如果可以將它畫在平面上，使它的邊僅在端點上才能相交，則稱此圖為可平面圖。如果一個可平面圖的每一個面都是三角形，則它是最大可平面圖。地圖的四著色問題最終可歸結(jié)到最大可平面圖的頂點四著色問題，這一點，圖論的眾多文獻(xiàn)中都有介紹［1］，本文不再論述。最大可平面圖的頂點四著色，當(dāng)頂點數(shù)較多時，計算量太大，人工著色的辦法根本不可能，而利用神經(jīng)網(wǎng)絡(luò)方法進(jìn)行編程是可行的。

1 神經(jīng)網(wǎng)絡(luò)方法

人工神經(jīng)網(wǎng)絡(luò)方法是一種模仿動物腦神經(jīng)網(wǎng)絡(luò)某些功能的數(shù)值計算方法。人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)由神經(jīng)元和神經(jīng)元間的連接權(quán)組成，多數(shù)類型的神經(jīng)網(wǎng)絡(luò)將神經(jīng)元以層的形式組織在一起，常見的神經(jīng)元間的連接權(quán)以層間神經(jīng)元的連接權(quán)為主。目前應(yīng)用最廣泛的反向傳播神經(jīng)網(wǎng)絡(luò)，其結(jié)構(gòu)由輸入層、輸出層和至少一個隱含層，以及層間連接權(quán)組成［2］。反饋網(wǎng)絡(luò)有多種，霍普菲爾德網(wǎng)絡(luò)是單層對稱全反饋網(wǎng)絡(luò)，根據(jù)其激活函數(shù)的選取不同，可分為離散型的霍普菲爾德網(wǎng)絡(luò)（DHNN）和連續(xù)型的霍普菲爾德網(wǎng)絡(luò)（CHNN）。DHNN的激活函數(shù)為二值型的，其輸入、輸出為｛－1，1｝的反饋網(wǎng)絡(luò)，主要用于聯(lián)想記憶；CHNN的激活函數(shù)為連續(xù)可微的單調(diào)上升函數(shù)，主要用于優(yōu)化計算（如圖1所示）。

圖1 霍普菲爾德網(wǎng)絡(luò)結(jié)構(gòu)示意圖Fig.1 Schematic diagram of Hopfield neural network

霍普菲爾德網(wǎng)絡(luò)是和電子模擬線路對應(yīng)的，其中每一個神經(jīng)元都有一樣的電路模型。它的工作原理有一定的動態(tài)數(shù)學(xué)方程，其能量函數(shù)可正可負(fù)，但負(fù)向有界，是廣義的李雅普諾夫函數(shù)，如圖1和圖2所示。

圖2 神經(jīng)元電路模型示意圖（第i個）Fig.2 Schematic diagram of neuron circuit model（i）

Rij為第j個輸入與第i個輸入之間的連接導(dǎo)納，Wij＝1／Rij；ri與ci分別為第i個運算放大器的電阻和輸入電容；Ii為外加恒定電流。調(diào)節(jié)其他系數(shù)，可忽略余項。V是輸入矢量，U是狀態(tài)矢量，O是輸出矢量。

輸出：

f（ui）＝ （1＋tanh（λ×ui））／2；

動態(tài)方程：

dui／dt＝ （－ui／qi＋ ∑Wijvj＋I(xiàn)i）／ci，1／qi＝1／ri＋ ∑Wij；

能量函數(shù)：

E＝－（∑Wijvivj）／2－∑viIi＋余項。

2 四著色問題的CHNN的網(wǎng)絡(luò)設(shè)計

2.1 反饋網(wǎng)絡(luò)的穩(wěn)定狀態(tài)

反饋網(wǎng)絡(luò)能夠表現(xiàn)出非線性動力學(xué)系統(tǒng)的動態(tài)特性，它具有如下的主要特性。

（1）網(wǎng)絡(luò)系統(tǒng)具有若干個穩(wěn)定的平衡狀態(tài)。當(dāng)網(wǎng)絡(luò)從某一個初始狀態(tài)開始運動后，網(wǎng)絡(luò)系統(tǒng)總可以收斂到某一個穩(wěn)定的平衡狀態(tài)。

（2）系統(tǒng)穩(wěn)定的平衡狀態(tài)可以通過設(shè)計網(wǎng)絡(luò)的權(quán)值而被存儲到網(wǎng)絡(luò)中［3］。

假設(shè)一個最大可平面圖已被四著色成功，那么它的每一個頂點顏色與其相鄰的頂點顏色都不相同，這是一種穩(wěn)定狀態(tài)，其他情況可視為不穩(wěn)定狀態(tài)。因此，頂點顏色狀態(tài)矩陣需要滿足3個條件：

（1）每列只能有一個是1。

（2）1的總數(shù)必須與頂點數(shù)相符。

（3）若某點的一個顏色模式為1，則與其連接的所有頂點的這個模式都不能為1。示例見表1。

表1 頂點顏色狀態(tài)表Table 1 Model table of vertex color

2.2 神經(jīng)元設(shè)計

對于m個頂點，需要4m個神經(jīng)元，設(shè)n＝4m，則描述CHNN的動態(tài)方程如下。

其中，T為CHNN網(wǎng)絡(luò)連接矩陣，λ為增益參數(shù)，τ是各神經(jīng)元的時間常數(shù)。

2.3 網(wǎng)絡(luò)設(shè)計

設(shè)G為最大平面圖的連接矩陣；g（a，b）＝0表示第a個頂點與第b個頂點不連接；g（a，b）＝1表示第a個頂點與第b個頂點連接。則T設(shè)計為

其中，Col為列限制系數(shù)常量，A為全局限制系數(shù)常量，D為平面圖結(jié)構(gòu)限制系數(shù)常量。a，b取1到m的值；a＝b意味同一頂點，δab＝1；a≠b，δab＝0。x，y取1到4的值；x＝y(tǒng)意味同一顏色，δxy＝1；x≠y，δxy＝0。

3 實驗驗證

3.1 實驗程序

程序主要由以下5個部分組成。

（1）隨機(jī)生成最大可平面圖。

（2）網(wǎng)絡(luò)中有關(guān)矩陣的生成。

（3）迭代計算。

（4）根據(jù)計算結(jié)果對頂點進(jìn)行染色。

（5）參數(shù)設(shè)定模塊。參數(shù)設(shè)定模塊主要迭代計算的偽代碼如下。

初始化：① 按公式（5）設(shè)置連接矩陣；② 以零設(shè)置輸入和狀態(tài)值。

cok：＝false；／／cok表示著色是否成功

dt：＝0.01；

while（idx＜nMax）do begin

／／nMax為迭代次數(shù)限制

／／狀態(tài)的計算；tt，II，dt分別對應(yīng)參數(shù)τ，I，Δt

for k：＝1to 4＊DDN do begin

／／DDN為實際頂點數(shù)

tmp：＝0；

for j：＝1to 4＊DDN do

tmp：＝tmp＋T［k，j］＊V［j］；

U［k］：＝U［k］＋

（tmp－U［k］／tt＋I(xiàn)I）＊dt；／／參照公式（4）end；

／／利用激活函數(shù)計算反饋；lmd為參數(shù)λ

for k：＝1to 4＊DDN do begin

V［k］：＝（1＋tanh（lmd＊U［k］））／2；

／／參照公式（2）

end；

／／頂點顏色的計算；CoT為頂點顏色狀態(tài)表

for i：＝1to DDN do

for j：＝1to 4do

CoT［j，i］：＝V［（j－1）＊DDN＋i］；

for k：＝1to DDN do begin

max：＝－1；maxi：＝0；

for i：＝1to 4do

if CoT［i，k］＞max then begin

max：＝F［i，k］；maxi：＝i；

end；

Se［k］：＝maxi；／／頂點所著顏色（次號）

end；

／／判斷是否著色成功

i：＝1；

while i＜＝DDN do begin

j：＝1；

while j＜＝DDN do begin

if（G［i］［j］＝1）and（Se［i］＝Se［j］）then

break；

j：＝j(luò)＋1；

end；

if j＜＝DDN then break；

i：＝i＋1；

end；

if i＞DDN then break；

idx：＝idx＋1；

end；

cok：＝（idx＜nMax）；／／cok為 True表示著色成功。

3.2 實驗參數(shù)和著色示例

在實驗中，隨機(jī)產(chǎn)生了100個頂點的最大可平面圖，使用表2的最后一行數(shù)據(jù)為運行參數(shù)，經(jīng)過大約20 599次迭代以后，成功染色，運行時間大約為180s。圖3中的空圓圈、實心圓圈、空方塊、實心方塊分別代表4種不同的顏色。在參數(shù)表中，參數(shù)Col，A和D用于網(wǎng)絡(luò)矩陣T的初始化計算；參數(shù)λ，τ，和I用于迭代計算［4］。U和V的初始值可以為零。本程序使用Delphi2010實現(xiàn)，如圖3所示為實驗著色的結(jié)果。

表2 運行參數(shù)表Table 2 Running parameter table

圖3 100個頂點的著色結(jié)果Fig.3 Coloring result of one hundred vertexes

4 結(jié)論

霍普菲爾德神經(jīng)網(wǎng)絡(luò)已成功地應(yīng)用于多種場合，主要集中于圖像處理、語音處理、信號處理、數(shù)據(jù)查詢、容錯計算、模式分類、模式識別等［5］?；羝辗茽柕抡J(rèn)為，在系統(tǒng)的運動過程中，其內(nèi)部儲存的能量隨著時間的增加而逐漸減少，當(dāng)運動到平衡狀態(tài)時系統(tǒng)的能量耗盡或變得最少，那么系統(tǒng)自然在此平衡狀態(tài)穩(wěn)定下來。利用能量函數(shù)概念，可以設(shè)計CHNN進(jìn)行優(yōu)化計算，利用其并行性可解決計算中的“指數(shù)爆炸”問題。典型例子是TSP問題、旅行商問題。本文探討更復(fù)雜的四著色問題，希望能給圖論研究帶來一點啟示。

［1］ 楊炳儒.圖論概要［M］.天津：天津科學(xué)技術(shù)大學(xué)出版社，1990.

［2］ HAYKIN S.神經(jīng)網(wǎng)絡(luò)原理［M］.北京：機(jī)械工業(yè)出版社，2004.

［3］ 魏海坤.神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計的理論與方法［M］.北京：國防工業(yè)出版社，2005.

［4］ TALAVAN P M，JAVIER.Parameter setting of the Hopfield network applied to TSP［J］.Neural Networks，2002，15（1）：363－373.

［5］ KURITA N，F(xiàn)UNAHASHI K－I.On the Hopfield neural networks and mean field theory［J］.Neural Networks，1996，9（9）：1531－1540.