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

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

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

3、問題）和求解0-1背包問題的兩類P系統(tǒng)。本文所完成的主要研究工作包括：
　　①基于對(duì)膜計(jì)算的研究，提出了在多項(xiàng)式時(shí)間內(nèi)求解All-SAT問題的P系統(tǒng)ΠAll-SATP，并對(duì)其算法進(jìn)行了詳細(xì)描述，最后給出了其復(fù)雜度分析。
　?、谠赑系統(tǒng)ΠAll-SATP的基礎(chǔ)上，對(duì)膜結(jié)構(gòu)和規(guī)則進(jìn)行改進(jìn)，提出了在線性時(shí)間內(nèi)求解All-SAT問題的P系統(tǒng)ΠAll-SATL，ΠAll-SATL中膜嵌套的層數(shù)降到常量級(jí)別（3層），同時(shí)時(shí)間復(fù)雜度降低到

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