任意地圖四著色問題的DNA算法.pdf

1、該文對地圖的著色問題進(jìn)行了研究,地圖的著色問題是一個(gè)NP難題,它源自著名的四色問題.著色問題主要研究如何將圖的點(diǎn)或者邊用給定數(shù)目的顏色涂染,使得相鄰兩點(diǎn)或者兩邊著色不同.該文通過考察三剖分邊著色的性質(zhì),提出了脈組的思想,并證明了覆蓋平滑三剖分所有區(qū)的脈組的存在性.根據(jù)以上的分析,我們給出了兩個(gè)算法:一個(gè)是平滑三剖分邊的三著色的DNA算法,并且在此基礎(chǔ)上,我們還給出了一個(gè)平滑三剖分頂點(diǎn)四著色的算法.任何一個(gè)地圖的著色問題都可以轉(zhuǎn)化成三剖分

2、從而平滑三剖分的頂點(diǎn)著色問題,因此對于任何一個(gè)地圖,我們都可以對它進(jìn)行著色.最后我們給出了一個(gè)計(jì)算機(jī)程序?qū)λ惴ㄟM(jìn)行了模擬.該文的兩個(gè)算法都具有很好的復(fù)雜度,分別是多項(xiàng)式時(shí)間復(fù)雜度和線性增長的空間復(fù)雜度.理想的,分別用十幾步生化操作就可以找出一個(gè)平滑三剖分圖的三著色和四著色,而所需的DNA分子鏈并不是很多,因此可以解決很大級別的圖著色問題,從而驗(yàn)證了DNA計(jì)算在并行計(jì)算上的優(yōu)越性.該文的編碼方式十分簡單、直觀,編碼具有規(guī)律性,易于實(shí)現(xiàn).在