帶約束路由問題的DNA計(jì)算研究與應(yīng)用.pdf

1、帶約束路由算法問題一直是通信領(lǐng)域的熱點(diǎn)問題。然而,多數(shù)特殊約束路由問題為NP-完全問題,除非NP=P,否則無法給出多項(xiàng)式時(shí)間算法。對(duì)于這些問題,已經(jīng)出現(xiàn)各種偽多項(xiàng)式算法,但這些算法必須在一定的限制條件內(nèi)才能保證算法時(shí)間效率。1994年Adleman博士首次提出了DNA計(jì)算的概念,并設(shè)計(jì)了DNA算法成功解決了7個(gè)頂點(diǎn)的哈密爾頓路徑問題,顯示了DNA計(jì)算解決復(fù)雜問題的巨大潛力。由于路由問題的特點(diǎn),可以利用DNA計(jì)算高度的并行性將問題的時(shí)間復(fù)

2、雜度轉(zhuǎn)化為DNA分子鏈的空間復(fù)雜度,從而在多項(xiàng)式時(shí)間內(nèi)得出問題的精確解。本文提出一套通用的路由問題的DNA編碼方案,并對(duì)兩種特殊的帶約束路由問題進(jìn)行DNA計(jì)算算法設(shè)計(jì)。
　　 指定結(jié)點(diǎn)路由問題可一般性地定義為帶指定結(jié)點(diǎn)約束的最短路徑問題,是一個(gè)NP難問題。本文提出一種將電子計(jì)算機(jī)算法與DNA計(jì)算算法相結(jié)合的方法求解指定結(jié)點(diǎn)路由問題。算法由轉(zhuǎn)化算法,源宿結(jié)點(diǎn)搜索切割算法,轉(zhuǎn)化圖結(jié)果搜索算法和結(jié)果讀取算法共四個(gè)子算法組成。分析結(jié)果表

3、明:執(zhí)行算法的電子計(jì)算機(jī)部分可顯著減少參與生化反應(yīng)的DNA鏈的數(shù)量,在試管內(nèi)DNA鏈數(shù)恒定的情況下,增加了可解決問題的結(jié)點(diǎn)和鏈路的規(guī)模。算法的DNA計(jì)算部分對(duì)最短路徑進(jìn)行并行搜索,可以在多項(xiàng)式時(shí)間內(nèi)得出問題的解。
　　 鏈路分離路徑對(duì)可用于保障網(wǎng)絡(luò)傳輸穩(wěn)定性,增加傳輸帶寬和實(shí)現(xiàn)負(fù)載均衡。本文對(duì)計(jì)算鏈路分離路徑對(duì)的電子計(jì)算機(jī)算法LIDOMPA算法進(jìn)行算法優(yōu)化改進(jìn),提出基于DNA計(jì)算的高效并行算法。該算法主要由最短路徑搜索算法,路徑