求解HCP問題和TSP問題的P系統(tǒng)研究.pdf

1、膜計(jì)算（又被稱為P系統(tǒng)）是自然計(jì)算中的一個(gè)新興的分支，它是由自然界的細(xì)胞所抽象得出的一種全新的計(jì)算模型。自Gheorghe.P?un教授于1998年在羅馬尼亞提出膜計(jì)算的概念后，便迅速發(fā)展，得到了全世界眾多學(xué)者的關(guān)注和研究，成為了有著巨大潛力的研究領(lǐng)域。相較于基于馮諾依曼模型的傳統(tǒng)計(jì)算機(jī)，膜計(jì)算的高度并行性的特點(diǎn)，使膜計(jì)算的計(jì)算能力大大超過(guò)了傳統(tǒng)計(jì)算機(jī)，因而在解決許多NP難問題上有了十分巨大的優(yōu)勢(shì)。
　　哈密爾頓回路問題和旅行者問

2、題是圖論中的兩個(gè)十分經(jīng)典的 NP難問題,雖然這兩個(gè)問題早已被提出，然而在目前的電子計(jì)算機(jī)的模型下，仍然不能在多項(xiàng)式時(shí)間內(nèi)求得這兩個(gè)問題的精確解。而膜計(jì)算作為新興的自然計(jì)算的分支，目前對(duì)這兩個(gè)NP難問題鮮有研究。因此，本文通過(guò)對(duì)求解哈密爾頓回路問題和旅行者問題的P系統(tǒng)研究，不僅擴(kuò)展了P系統(tǒng)在圖論領(lǐng)域的使用范圍，也對(duì)P系統(tǒng)的實(shí)際應(yīng)用有著一定的研究?jī)r(jià)值。本文分析和研究了哈密爾頓回路問題和旅行者問題，設(shè)計(jì)了求解這兩個(gè)圖論問題的P系統(tǒng)。本文所完成

3、的研究工作簡(jiǎn)述如下：
　　①根據(jù)圖論中哈密爾頓回路問題的特點(diǎn)，設(shè)計(jì)了求解哈密爾頓回路的具體算法，為求解該問題的P系統(tǒng)實(shí)現(xiàn)奠定了基礎(chǔ)。
　?、诟鶕?jù)圖論中旅行者問題的特點(diǎn)，設(shè)計(jì)了求解旅行者問題的具體算法，為求解該問題的P系統(tǒng)實(shí)現(xiàn)奠定了基礎(chǔ)。
　?、墼O(shè)計(jì)了三個(gè)P系統(tǒng)組件以求解哈密爾頓路徑問題、哈密爾頓回路問題和旅行者問題等圖論問題。
　?、芑谶@些P系統(tǒng)組件，設(shè)計(jì)了一個(gè)可以求解哈密爾頓回路問題全部解的P系統(tǒng)，并給出了具