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

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

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

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