求解兩類圖論問(wèn)題的P系統(tǒng)研究.pdf

1、膜計(jì)算(也被稱為膜系統(tǒng)或P系統(tǒng))是羅馬尼亞Gheorghe.P?un教授于1998年從細(xì)胞中抽象出的新的計(jì)算模型，自被提出后，發(fā)展迅速，并成為自然計(jì)算中的一個(gè)分支。由于細(xì)胞內(nèi)的化學(xué)反應(yīng)可以并行執(zhí)行，且反應(yīng)所消耗的能量非常小，所以，P系統(tǒng)擁有極大并行性，用來(lái)解決一些復(fù)雜問(wèn)題得心應(yīng)手，從而獲得遠(yuǎn)遠(yuǎn)超過(guò)傳統(tǒng)電子計(jì)算機(jī)的計(jì)算能力，也為很多難點(diǎn)問(wèn)題帶來(lái)新的求解思路。已有研究證明，膜計(jì)算可以在多項(xiàng)式時(shí)間內(nèi)解決很多NP-完全問(wèn)題。
　　頂點(diǎn)覆蓋

2、問(wèn)題和度約束生成樹(shù)問(wèn)題是圖論中兩類經(jīng)典的NP難問(wèn)題，在電子計(jì)算機(jī)計(jì)算模型下，對(duì)于這兩類問(wèn)題的求解要么只能求出其個(gè)別值，要么對(duì)于大規(guī)模的問(wèn)題求解根本束手無(wú)策。膜計(jì)算作為一個(gè)新興的研究領(lǐng)域，雖然其對(duì)于求解NP難問(wèn)題擁有很大的優(yōu)勢(shì)，但是仍然鮮有對(duì)這兩類問(wèn)題的研究成果發(fā)表。不論從擴(kuò)展膜計(jì)算的應(yīng)用領(lǐng)域上，還是從實(shí)際應(yīng)用中，研究這兩類NP難問(wèn)題都有著一定的理論意義和應(yīng)用價(jià)值。因此，本文通過(guò)對(duì)頂點(diǎn)覆蓋問(wèn)題和度約束生成樹(shù)問(wèn)題的分析，設(shè)計(jì)出求解這兩類問(wèn)題

3、全部解的P系統(tǒng)，擴(kuò)展P系統(tǒng)在圖論領(lǐng)域的研究，也為P系統(tǒng)計(jì)算機(jī)的物理實(shí)現(xiàn)提供一定的理論基礎(chǔ)。本文所完成的研究工作簡(jiǎn)述如下：
　?、俑鶕?jù)圖論中頂點(diǎn)覆蓋問(wèn)題基礎(chǔ)知識(shí)及其特點(diǎn)，設(shè)計(jì)出判定頂點(diǎn)覆蓋的具體流程，為求解該問(wèn)題的具體實(shí)現(xiàn)奠定基礎(chǔ)。
　?、诟鶕?jù)圖論中度約束生成樹(shù)問(wèn)題基礎(chǔ)知識(shí)及其特點(diǎn)，設(shè)計(jì)出判定生成樹(shù)的具體流程，為求解該問(wèn)題的具體實(shí)現(xiàn)奠定基礎(chǔ)。
　　③通過(guò)膜計(jì)算模型的研究，設(shè)計(jì)了一個(gè)求解頂點(diǎn)覆蓋問(wèn)題全部解的P系統(tǒng)，并用實(shí)例