基于分治的背包問題DNA計算機(jī)算法

李潤榮

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

關(guān)鍵詞：分治、背包問題、DNA計算機(jī)算法

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

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

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

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

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

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

（一）背包問題DNA 計算機(jī)算法思想

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

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

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

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

參考文獻(xiàn)：

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

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

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

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