基于分治的背包問題DNA計算機算法

李潤榮

摘要：隨著我國科學技術的不斷發(fā)展，各式各樣的計算機網(wǎng)絡可謂層出不窮。與此同時，計算機網(wǎng)絡的廣泛應用，隨之在一定的程度上為人們的生活等多方面，也提供了許多的便利。另外，DNA計算機作為一種新興的生物形式計算機，則更是起到了不容小覷的作用。對此，其主要是應用于處理較為復雜的大型計算機問題。例如，背包問題等多種NP完全問題。而為了能夠更好地提高該計算機算法的可靠性與精準性，基于分治的DNA計算機算法便在一定的程度上，引起了相關工作人員對其的重視。基于此，本文將就此現(xiàn)象做出一定的分析與研究。進而，以期對分治法應用于背包問題的DNA計算機算法，而起到一定合理化的保障作用。

關鍵詞：分治、背包問題、DNA計算機算法

在未運用基于分治的DNA計算機算法解決背包問題時，其所采用的傳統(tǒng)計算機算法，普遍具備極為復雜化與繁瑣化的特點。因而，也就使得無法真正地起到解決問題的目的。是以，有關工作人員則就此而提出了一種新型的計算機算法，即基于分治的背包問題DNA計算機算法。與此同時，自運用這一計算機算法以來，有關于各類復雜的大型計算機問題的解決效率與準確性等等，則均得到了極大的發(fā)展和改善。

一、背包問題與DNA計算機的簡要概述

DNA計算機，是一種不同于往常傳統(tǒng)計算機的新型生物形式計算機。對此，其主要具有存儲容量大、運行快、耗能低、以及體積小等多種優(yōu)勢特點。另外，其主要是通過運用分子生物學的運算形式，而來解決相應復雜的計算機數(shù)學問題。對此，由于當前我國DNA計算機算法，仍然處于較為落后的發(fā)展階段。因而，這便使得其存在了一定的欠缺之處。例如，在其進行較大范圍的計算機操作的過程中，普遍極易出現(xiàn)實際操作困難、不靈活、以及復制錯誤率大等多方面的問題現(xiàn)象。與此同時，又由于相關計算機問題中的背包問題，具有較強的典范性與復雜性。因此，現(xiàn)階段有關于如何科學、合理、以及高效地運用DNA計算機算法來解決背包問題，則可謂是刻不容緩。對此，將分治算法而應用于這一問題之中，則在現(xiàn)階段較大程度上的取得了多數(shù)人的認可。

二、基于分治的背包問題DNA計算機算法的提出背景

處于分子生物技術快速發(fā)展的背景下，當前背包問題在信息密碼學、以及數(shù)論研究等大型難解問題領域中，所具有的應用價值與重要意義隨之也得到了一定的提升。是以，為了更為有效地解決背包問題，相關科學研究人員則為此提出了一種新型的DNA計算機算法，即分治DNA計算機算法。對此，其運行模式，即主要分為了并行數(shù)據(jù)搜索器、以及n位并行減法器這兩種子算模式。且除此之外，應用該算法的主要優(yōu)勢特點，即是其能夠有效地提高計算機算法應用的并行性與準確性。而與此同時，就我國目前的生物技術而言，運用基于分治的DNA計算機算法，一方面能夠更為全面、以及具體地減少編碼錯誤現(xiàn)象的產(chǎn)生。另一方面，則更是在一定的程度上，增添了更多不同的解決途徑。因此，雖然該計算機算法在其計算方式、以及存儲等方面，與傳統(tǒng)計算機算法存在著一定的差異。但毋庸置疑的是，這兩者所具有的本質(zhì)仍然是一致的。

三、基于分治的背包問題DNA計算機算法思想的分析

（一）背包問題DNA 計算機算法思想

在應用分析算法來解決背包問題之前，傳統(tǒng)計算機算法最為著名、以及最為精準的一種算法，即是二表法計算機算法。對此，運用該算法最主要的一個原因，即是其能夠有效地解決與覆蓋相應的計算機NP完全問題。因而，也就是由于其具備這一關鍵的優(yōu)勢。所以，有關工作人員則據(jù)此而提出了一種更為便利、以及高效的DNA分子操作形式的計算機算法。繼而，通過實際地應用這一算法，我們可以得知的是其在一定的程度上，極大地降低了DNA鏈數(shù)等因素的影響程度與與范圍。但需要注意的是，其必然也存在著一定的不足之處。例如，無法實時的進行相關搜索行為、以及無法解決DNA的排序等等。是以，相關工作人員通過不斷對其進行實驗與實踐，隨之也便逐漸地摸索出了將分治算法與DNA分子算法結(jié)合運用的新型計算模式。此外，就DNA分子操作特點的角度而言，該計算機算法，一方面能夠大幅度地減少計算的次數(shù)，另一方面也能夠有效地減少原需計算的DNA鏈數(shù)。因此，為了更為充分地擴大其具體的應用范圍，相關工作人員則有必要采取一定的措施。進而，確保在有效提高該計算機算法可行性的同時，還能夠使其真正地發(fā)揮出其具體地應用成效。

（二）基于分治的背包問題DNA計算機算法思想分析

簡單來說，分治也就是將一個較為復雜的大型問題，合理地分解為多個類似的小問題。然后，通過采取相應的應對措施，而使其能夠?qū)崿F(xiàn)最終的解決目的。而與此同時，現(xiàn)階段最為普遍、以及最為有效的背包問題解決方法，即為分治DNA計算機算法。對此，目前分治算法在解決背包問題時，即主要是依據(jù)1個搜索器、一個減法器、以及4個子算法而進行具體運算的。且除此之外，分治算法不同于其他傳統(tǒng)計算機算法的主要優(yōu)勢有：其一，能夠有效地解決實際計算過程中的精準問題；其二，能夠及時地發(fā)現(xiàn)其具體數(shù)據(jù)信息的錯誤之處；其三，能夠最大可能性地達到DNA計算機算法的需求標準。另外，從理論上來講，當前這一算法已將所需計算的背包問題中的DNA鏈數(shù)的維數(shù)，成功的從原來的60提高到了120。因而，在當前DNA計算機算法的不斷發(fā)展過程中，如何運用分治DNA計算機算法，來求解計算大型復雜問題中的純指數(shù)增長的DNA鏈數(shù)，便隨之成為了當前研究DNA計算機算法最為關鍵的一重要內(nèi)容。

結(jié)束語：綜上所述，將分治算法應用到DNA計算機中來解決背包問題，是目前較為合理、以及較為高效的一種新型計算機算法。是以，為了使該算法能夠更好地發(fā)揮其計算優(yōu)勢、以及更為有效地提高DNA計算機算法的準確性。因而，相關工作人員還應在現(xiàn)有的條件基礎上，對其積極不斷地進行分析、研究與實踐。進而，有效確保該DNA計算機算法能夠得到更好地發(fā)展、以及能夠應用到更為廣泛的領域。

參考文獻：

[1]王喻.分治的背包問題DNA計算機算法分析[J].信息系統(tǒng)工程，2017，（03）：150.

[2]王劍波.基于質(zhì)粒模型的DNA計算機算法求解背包問題[J].湖南人文科技學院學報，2010，（04）：77-79+96.

[3]郭里.若干圖論問題的DNA計算機算法研究[D].導師：李仁發(fā)；李肯立.湖南大學，2011.

[4]潘果，李肯立，劉完芳.基于分治的子集積問題DNA計算機算法[J].計算機工程與科學，2011，（08）：74-78.