最短経路問題におけるDNAコンピュータとダイクストラ法との比較シミュレーション

カテゴリ: 全国大会

論文No: 3-061

グループ名: 【全国大会】平成19年電気学会全国大会論文集

発行日: 2007/03/15

タイトル(英語): Comparative Simulation Between DNA Computer and Dijkstra Algorithm in Shortest Pass Problem

著者名: 藤島 弘二郎(明治大学),小野 治(明治大学)

著者名(英語): Kojiro Fujishima(Meiji University),Osamu Ono(Meiji University)

キーワード: DNAコンピュータ|ダイクストラ法|計算オーダ|Parallel Overlap Assembly

要約(日本語): DNAコンピュータにおいて現在さまざまな応用が考えられている。本研究では、その中の一つである有向グラフにおける最短経路問題において、信頼性のあるダイクストラ法とDNAコンピュータの手法の一つであるPOAと呼ばれる手法の計算量を求めることにより両手法を比較している。しかし、この比較において実装にはかなりの差があり、平等な比較が難しいものと考えられた。そこで、ここでは計算オーダという近似式を用いることによって計算量を近似している。これにより、POAがダイクストラ法と比較しても非常に高速なO(logn)で計算できるということを示した。

原稿種別: 日本語

PDFファイルサイズ: 1,920 Kバイト