本文關(guān)鍵詞：求解兩類圖論問題的P系統(tǒng)研究

  更多相關(guān)文章： 頂點(diǎn)覆蓋 度約束生成樹 圖論 P系統(tǒng) 膜計(jì)算

【摘要】：膜計(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)擁有極大并行性,用來解決一些復(fù)雜問題得心應(yīng)手,從而獲得遠(yuǎn)遠(yuǎn)超過傳統(tǒng)電子計(jì)算機(jī)的計(jì)算能力,也為很多難點(diǎn)問題帶來新的求解思路。已有研究證明,膜計(jì)算可以在多項(xiàng)式時(shí)間內(nèi)解決很多NP-完全問題。頂點(diǎn)覆蓋問題和度約束生成樹問題是圖論中兩類經(jīng)典的NP難問題,在電子計(jì)算機(jī)計(jì)算模型下,對于這兩類問題的求解要么只能求出其個(gè)別值,要么對于大規(guī)模的問題求解根本束手無策。膜計(jì)算作為一個(gè)新興的研究領(lǐng)域,雖然其對于求解NP難問題擁有很大的優(yōu)勢,但是仍然鮮有對這兩類問題的研究成果發(fā)表。不論從擴(kuò)展膜計(jì)算的應(yīng)用領(lǐng)域上,還是從實(shí)際應(yīng)用中,研究這兩類NP難問題都有著一定的理論意義和應(yīng)用價(jià)值。因此,本文通過對頂點(diǎn)覆蓋問題和度約束生成樹問題的分析,設(shè)計(jì)出求解這兩類問題全部解的P系統(tǒng),擴(kuò)展P系統(tǒng)在圖論領(lǐng)域的研究,也為P系統(tǒng)計(jì)算機(jī)的物理實(shí)現(xiàn)提供一定的理論基礎(chǔ)。本文所完成的研究工作簡述如下:(1)根據(jù)圖論中頂點(diǎn)覆蓋問題基礎(chǔ)知識及其特點(diǎn),設(shè)計(jì)出判定頂點(diǎn)覆蓋的具體流程,為求解該問題的具體實(shí)現(xiàn)奠定基礎(chǔ)。(2)根據(jù)圖論中度約束生成樹問題基礎(chǔ)知識及其特點(diǎn),設(shè)計(jì)出判定生成樹的具體流程,為求解該問題的具體實(shí)現(xiàn)奠定基礎(chǔ)。(3)通過膜計(jì)算模型的研究,設(shè)計(jì)了一個(gè)求解頂點(diǎn)覆蓋問題全部解的P系統(tǒng),并用實(shí)例及計(jì)算機(jī)仿真程序來驗(yàn)證該P(yáng)系統(tǒng)的可行性。(4)通過膜計(jì)算模型的研究,設(shè)計(jì)了一個(gè)求解度約束生成樹問題全部解的P系統(tǒng),并用實(shí)例及計(jì)算機(jī)仿真程序來驗(yàn)證該P(yáng)系統(tǒng)的可行性。綜上所述,本文通過選擇頂點(diǎn)覆蓋問題和度約束生成樹問題進(jìn)行P系統(tǒng)研究,完善了P系統(tǒng)中對于NP難問題的研究,為其他NP難問題的求解提供參考,也為今后解決其他領(lǐng)域問題的提供解決思路。
【關(guān)鍵詞】：頂點(diǎn)覆蓋 度約束生成樹 圖論 P系統(tǒng) 膜計(jì)算
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要3-4
• ABSTRACT4-8
• 1 緒論8-12
• 1.1 引言8-9
• 1.2 國內(nèi)外研究現(xiàn)狀綜述9-10
• 1.3 研究的目的及意義10-11
• 1.4 本文結(jié)構(gòu)及安排11-12
• 2 研究基礎(chǔ)12-20
• 2.1 膜計(jì)算基礎(chǔ)12-14
• 2.1.1 膜及其表示12-13
• 2.1.2 類細(xì)胞P系統(tǒng)定義13-14
• 2.2 圖論問題基礎(chǔ)14-15
• 2.3 頂點(diǎn)覆蓋問題15-17
• 2.3.1 問題定義15-16
• 2.3.2 判定方法16-17
• 2.4 度約束生成樹問題17-18
• 2.4.1 問題定義17
• 2.4.2 判定方法17-18
• 2.5 P系統(tǒng)仿真平臺18-19
• 2.6 本章小結(jié)19-20
• 3 頂點(diǎn)覆蓋問題全部解的求解P系統(tǒng) ΠAll-VCP20-32
• 3.1 ΠAll-VCP的定義20-21
• 3.2 All-VCP求解流程21-23
• 3.3 規(guī)則集合23-25
• 3.4 實(shí)例分析25-26
• 3.5 系統(tǒng)仿真26-31
• 3.6 本章小結(jié)31-32
• 4 度約束生成樹問題全部解求解P系統(tǒng) ΠAll-DCSTP32-43
• 4.1 ΠAll-DCSTP的定義32-33
• 4.2 All-DCSTP求解流程33-35
• 4.3 規(guī)則集合35-38
• 4.4 實(shí)例分析38-39
• 4.5 系統(tǒng)仿真39-42
• 4.6 本章小結(jié)42-43
• 5 總結(jié)與展望43-45
• 5.1 總結(jié)43
• 5.2 展望43-45
• 致謝45-46
• 參考文獻(xiàn)46-49
• 附錄49
• A. 作者在攻讀學(xué)位期間發(fā)表的論文目錄49
• B. 作者在攻讀學(xué)位期間參與的科研項(xiàng)目49

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前3條

1 曹布陽,林亞雄;最小費(fèi)用/容量比生成樹的一個(gè)算法[J];上海機(jī)械學(xué)院學(xué)報(bào);1985年03期

2 楊春德;Fuzzy網(wǎng)絡(luò)中生成樹的優(yōu)化問題[J];重慶郵電學(xué)院學(xué)報(bào);1996年02期

3 ;[J];;年期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 馮俊文;;最優(yōu)生成樹的表格求解方法[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（下卷）[C];2000年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 李幸福;最大內(nèi)部點(diǎn)生成樹問題的算法及復(fù)雜性[D];山東大學(xué);2015年

2 王巖;扭立方體和奇偶立方體上獨(dú)立生成樹的嵌入研究[D];蘇州大學(xué);2014年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 鐘玉文;求解兩類圖論問題的P系統(tǒng)研究[D];重慶大學(xué);2016年

2 徐憶晨;最小標(biāo)記生成樹問題的研究與拓展[D];復(fù)旦大學(xué);2009年

，

本文編號：1048570