求解兩類典型NP問題的P系統(tǒng)研究.pdf

1、膜計算是自然計算領域的新分支，它是通過研究生物活細胞的功能和結(jié)構(gòu)，以及其他組織和器官或者其他細胞群等高級結(jié)構(gòu)而抽象出來的一種并行計算模型。以膜計算模型為基礎建立的計算系統(tǒng)稱為 P系統(tǒng)，它具有極大并行性，這也是其相比傳統(tǒng)計算系統(tǒng)的優(yōu)勢，能夠獲得更強的計算能力。膜計算模型已經(jīng)被證明與圖靈機具有等價的計算能力，它能夠用于解決NP難問題，且能夠在多項式時間甚至線性時間內(nèi)完成。
　　邏輯命題的可滿足性問題和背包問題是兩類經(jīng)典的NP問題，在電

2、子計算機計算模型下，對于這兩類問題只能求出個別解或者近似解，當問題規(guī)模較大時，普通的電子計算機根本束手無策。在膜計算領域中，雖然已經(jīng)有學者構(gòu)造了求解可滿足性問題（Satisfiability problem，簡稱SAT問題）的P系統(tǒng)，但其時間復雜度和空間復雜度仍可以改進。也有學者提出了利用P系統(tǒng)求解判定性背包問題，但并沒有得到背包問題的最優(yōu)解?；诖耍疚脑O計了求可滿足性問題全部解（All-Solutions SAT，簡稱All-SAT

3、問題）和求解0-1背包問題的兩類P系統(tǒng)。本文所完成的主要研究工作包括：
　?、倩趯δび嬎愕难芯浚岢隽嗽诙囗検綍r間內(nèi)求解All-SAT問題的P系統(tǒng)ΠAll-SATP，并對其算法進行了詳細描述，最后給出了其復雜度分析。
　?、谠赑系統(tǒng)ΠAll-SATP的基礎上，對膜結(jié)構(gòu)和規(guī)則進行改進，提出了在線性時間內(nèi)求解All-SAT問題的P系統(tǒng)ΠAll-SATL，ΠAll-SATL中膜嵌套的層數(shù)降到常量級別（3層），同時時間復雜度降低到

4、線性級別。最后結(jié)合實例詳細描述了該P系統(tǒng)的執(zhí)行過程，并編寫仿真程序?qū)系統(tǒng)ΠAll-SATL的正確性和可行性進行驗證。
　?、刍趯δび嬎愕难芯?，提出了求解0-1背包問題的P系統(tǒng)ΠKP，對其算法和規(guī)則進行了詳細描述，該P系統(tǒng)的平均時間復雜度為線性級別，膜嵌套的層數(shù)是常量級別（3層）。最后結(jié)合實例詳細描述了該P系統(tǒng)的執(zhí)行過程，并編寫仿真程序?qū)系統(tǒng)ΠKP的正確性和可行性進行驗證。
　　本文通過選擇全部解的合取范式的可滿足性問題