计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2014年
1期
111-114
,共4页
TSP问题%DNA计算%闭环模型%DNA算法
TSP問題%DNA計算%閉環模型%DNA算法
TSP문제%DNA계산%폐배모형%DNA산법
TSP problem%DNA computing%closed circle model%DNA algorithm
旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决.DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势.尝试利用DNA计算中改进的闭环模型解决TSP问题.首先介绍了闭环DNA计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题.
旅行商問題TSP是NP完全問題,在工程實踐中有著廣汎的應用,利用常規算法很難在多項式時間內解決.DNA計算是一種新興的計算模式,與生俱來的彊大併行計算能力使得它在解決衆多NP問題上錶現齣瞭巨大的優勢.嘗試利用DNA計算中改進的閉環模型解決TSP問題.首先介紹瞭閉環DNA計算模型及其改進;隨後提齣瞭一種基于改進的閉環模型求解TSP問題的算法,併對算法的實驗過程進行瞭詳細的描述;最後運用該算法解決瞭一箇小規模的TSP問題算例,結果錶明,該算法能在較低的時間複雜度內有效地解決TSP問題.
여행상문제TSP시NP완전문제,재공정실천중유착엄범적응용,이용상규산법흔난재다항식시간내해결.DNA계산시일충신흥적계산모식,여생구래적강대병행계산능력사득타재해결음다NP문제상표현출료거대적우세.상시이용DNA계산중개진적폐배모형해결TSP문제.수선개소료폐배DNA계산모형급기개진;수후제출료일충기우개진적폐배모형구해TSP문제적산법,병대산법적실험과정진행료상세적묘술;최후운용해산법해결료일개소규모적TSP문제산례,결과표명,해산법능재교저적시간복잡도내유효지해결TSP문제.
