可滿足性問題的改進型類組織P系統(tǒng)的求解研究
發(fā)布時間：2018-11-09 11:51
【摘要】：作為首個被證明了的NP完全問題,布爾邏輯表達式的可滿足性問題(SAT問題)為計算機復雜性理論奠定了夯實的基礎,在硬件電路可行性的測試、計算機科學(包括定理機器證明、機器視覺、數(shù)據(jù)庫)等眾多領域都有廣泛應用。雖然大多數(shù)SAT問題都在表示為合取范式的基礎上求解的,但鑒于實際中的布爾表達式有兩種形式：合取范式(CNF)和析取范式(DNF),DNF更是其標準形式,但是卻鮮有關于DNF可滿足性的求解。因此本文將可滿足性問題進行了細分擴展,將可滿足性問題擴展成兩部分來求解。一部分是傳統(tǒng)的基于CNF的SAT問題的求解,另一部分是基于DNF的SAT問題的求解。這種劃分方式就能夠比較全面的涵括可滿足性問題的所有情況,大大拓寬了現(xiàn)實中的應用范圍。 本文利用膜計算的極大并行性,結(jié)合基本類組織P系統(tǒng),模仿自然界中帶電生物體組織的生命活動,提出了一種基于細胞分裂的識別型可進化類組織P系統(tǒng),來求解可滿足性問題。該系統(tǒng)能夠在短時間內(nèi)通過細胞分裂得到呈指數(shù)型增長的計算細胞,使每個計算細胞處理一種真值分配情況。運用交流規(guī)則、分裂規(guī)則、進化規(guī)則和輸出規(guī)則在多項式時間內(nèi)對布爾表達式進行并行處理,這不僅符合生物化學理論和實踐,從而能夠向環(huán)境中輸出對象yes或no,以此表明布爾表達式是否滿足。通過空間換時間這種方法來在很大程度上增強計算效率。 最后,在軟件和硬件上分別做了仿真與驗證。在軟件方面,使用塞爾維亞大學自然科學研究組專門開發(fā)出來的編程語言pLingua編寫本算法,并結(jié)合配套的專用于P系統(tǒng)仿真的pLinguaPlugin完成算法的仿真。在硬件方面,采用了具有并行特性的FPGA,通過VHDL語言對硬件的描述建立了相應的膜系統(tǒng)。并且,最終均證明本算法為正確可行的。 一直以來,很多學者都致力于SAT問題的求解,將其細分求解并用膜計算解決的并不多見,且膜計算一直面臨著軟硬件難實現(xiàn)的問題。本文將SAT問題進行細分處理解決,在很大程度上拓寬了現(xiàn)實中的應用范圍；利用膜計算高效的計算能力和效率,克服了以往大多數(shù)算法由于串行計算而導致計算效率不高的缺點；最后還分別通過軟硬件使得該算法得以實現(xiàn),尤其是通過硬件電路FPGA實現(xiàn)P系統(tǒng),克服了傳統(tǒng)的生化反應實現(xiàn),推動了膜計算硬件實現(xiàn)的步伐。綜上可知,探索膜計算求解SAT問題有著重要現(xiàn)實價值與應用意義。
[Abstract]:As the first proved NP complete problem, Boolean logic expression satisfiability problem (SAT problem) lays a solid foundation for computer complexity theory, and tests the feasibility of hardware circuit. Computer science (including theorem machine proof, machine vision, database) and many other fields have been widely used. Although most SAT problems are solved on the basis of representation as conjunctive normal form, in view of the fact that there are two forms of Boolean expressions in practice: (CNF) and (DNF), DNF are their standard forms. However, there are few solutions about DNF satisfiability. In this paper, the satisfiability problem is subdivided into two parts to solve the problem. One is the traditional SAT problem based on CNF, the other is the SAT problem based on DNF. This method can cover all the cases of satisfiability problem, and widen the range of application in reality. Based on the maximal parallelism of membrane computing and the basic tissue P system, a novel evolutionary tissue P system based on cell division is proposed in this paper, which mimics the life activities of charged organisms in nature. To solve the satisfiability problem. The system can obtain exponential growth computing cells through cell division in a short period of time, which enables each computing cell to deal with a distribution of true values. Using exchange rule, split rule, evolution rule and output rule to process Boolean expression in polynomial time in parallel, this not only accords with biochemistry theory and practice, thus can output object yes or no, to the environment. This indicates whether the Boolean expression is satisfied. To a great extent, the computational efficiency is enhanced by the method of changing space for time. Finally, the software and hardware are simulated and verified. In the aspect of software, the algorithm is programmed with the programming language pLingua, which is specially developed by the Natural Science Research Group of the University of Serbia, and the simulation of the algorithm is completed with the matching pLinguaPlugin which is dedicated to the simulation of P system. In the aspect of hardware, FPGA, with parallel characteristics is used to describe the hardware in VHDL language, and the corresponding membrane system is established. Finally, the algorithm is proved to be correct and feasible. Many scholars have been devoted to solving the SAT problem, but it is rare to solve it by subdivision and membrane computing, and membrane computing has always been faced with the problem of hardware and software difficult to implement. In this paper, the SAT problem is solved by subdivision, which to a great extent widens the scope of application in reality. The high efficiency and efficiency of membrane computing overcomes the shortcoming that most of the previous algorithms are not efficient because of serial computation. Finally, the algorithm is implemented by software and hardware, especially the P system is realized by hardware circuit FPGA, which overcomes the traditional biochemical reaction and promotes the realization of membrane computing hardware. In summary, it has important practical value and application significance to explore the solution of SAT problem by membrane calculation.
【學位授予單位】：安徽理工大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP311.1;O141
本文編號：2320335
[Abstract]:As the first proved NP complete problem, Boolean logic expression satisfiability problem (SAT problem) lays a solid foundation for computer complexity theory, and tests the feasibility of hardware circuit. Computer science (including theorem machine proof, machine vision, database) and many other fields have been widely used. Although most SAT problems are solved on the basis of representation as conjunctive normal form, in view of the fact that there are two forms of Boolean expressions in practice: (CNF) and (DNF), DNF are their standard forms. However, there are few solutions about DNF satisfiability. In this paper, the satisfiability problem is subdivided into two parts to solve the problem. One is the traditional SAT problem based on CNF, the other is the SAT problem based on DNF. This method can cover all the cases of satisfiability problem, and widen the range of application in reality. Based on the maximal parallelism of membrane computing and the basic tissue P system, a novel evolutionary tissue P system based on cell division is proposed in this paper, which mimics the life activities of charged organisms in nature. To solve the satisfiability problem. The system can obtain exponential growth computing cells through cell division in a short period of time, which enables each computing cell to deal with a distribution of true values. Using exchange rule, split rule, evolution rule and output rule to process Boolean expression in polynomial time in parallel, this not only accords with biochemistry theory and practice, thus can output object yes or no, to the environment. This indicates whether the Boolean expression is satisfied. To a great extent, the computational efficiency is enhanced by the method of changing space for time. Finally, the software and hardware are simulated and verified. In the aspect of software, the algorithm is programmed with the programming language pLingua, which is specially developed by the Natural Science Research Group of the University of Serbia, and the simulation of the algorithm is completed with the matching pLinguaPlugin which is dedicated to the simulation of P system. In the aspect of hardware, FPGA, with parallel characteristics is used to describe the hardware in VHDL language, and the corresponding membrane system is established. Finally, the algorithm is proved to be correct and feasible. Many scholars have been devoted to solving the SAT problem, but it is rare to solve it by subdivision and membrane computing, and membrane computing has always been faced with the problem of hardware and software difficult to implement. In this paper, the SAT problem is solved by subdivision, which to a great extent widens the scope of application in reality. The high efficiency and efficiency of membrane computing overcomes the shortcoming that most of the previous algorithms are not efficient because of serial computation. Finally, the algorithm is implemented by software and hardware, especially the P system is realized by hardware circuit FPGA, which overcomes the traditional biochemical reaction and promotes the realization of membrane computing hardware. In summary, it has important practical value and application significance to explore the solution of SAT problem by membrane calculation.
【學位授予單位】：安徽理工大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP311.1;O141
【參考文獻】
相關期刊論文 前10條
1 劉輝;;基于EP1C3T144C8的FPGA的開發(fā)板設計[J];電子技術;2009年01期
2 孟磊;周蘭江;;基于CNF權(quán)重學習求解3-SAT問題的進化算法[J];貴州大學學報(自然科學版);2009年05期
3 劉蘊韜;;FPGA應用實例——實現(xiàn)I2C總線主機控制器[J];電子世界;2014年06期
4 邢潔清;郭平;朱慶生;王春騰;;基于膜系統(tǒng)的邏輯運算研究[J];電腦知識與技術;2009年13期
5 勞勝領;董會錦;;單片機擴展FPGA應用技術研究[J];電子技術與軟件工程;2014年16期
6 李小龍;孟李林;邵瑞瑞;張小磊;;基于FPGA的PCI Express應用平臺設計[J];電子科技;2014年12期
7 譚用秋,楊克昌,方建超;求解可滿足性問題的改進的模擬退火算法[J];計算機工程與應用;2002年11期
8 王芙;周育人;葉立;;調(diào)查傳播算法和蟻群算法相結(jié)合求解可滿足性問題[J];計算機科學;2012年04期
9 張德富,黃文奇,汪厚祥;求解SAT問題的擬人退火算法[J];計算機學報;2002年02期
10 張葛祥;潘林強;;自然計算的新分支——膜計算[J];計算機學報;2010年02期
相關博士學位論文 前3條
1 陳海珠;膜計算應用研究[D];重慶大學;2011年
2 牛云云;求解計算困難問題的膜計算模型與算法研究[D];華中科技大學;2012年
3 楊世品;P系統(tǒng)優(yōu)化算法及應用研究[D];浙江大學;2013年
，本文編號：2320335
本文鏈接：http://sikaile.net/kejilunwen/yysx/2320335.html
最近更新
教材專著
