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

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

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

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