帶約束路由問題的DNA計算研究與應用.pdf

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

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

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