アカウント名:
パスワード:
>「家から駅までの最短経路」 例えば、でしょ(W 巡回セールスマン問題。NPコンプリートだったっけ?
「DNAコンピュータ」がNP完全問題を現実的時間内で解ける力を持ち得ると 期待される点については その通りと思いますが、 「家から駅までの最短経路」は「巡回セールスマン問題」とは違って、 完全解を得る効率的なアルゴリズムがすでに存在しますね、 ってことで念のため。:)
Dijkstra's Algorithm [acm.org]が定番。
NP完全問題の例のつもりで挙げたのを読売新聞が間違えた、とかいうことでなければ、 単にDNAコンピュータでプログラミングしやすい例を挙げただけなんじゃないでしょうか。
で、やっぱりどうやってプログラミングするんだろうってのが素朴な疑問なんですが。 そーぞーするに、白衣着て試験管振るようなコーディング風景であろうか。 DNAコンピュータなら、情報処理技術者も、 晴れて映画に出てくる「カガクシャ」の格好ができそうだなあ。:-D
Dijkstraを実際に用いている身近な例としては、OSPFがありますね。Topological Databaseの構築を受け、各ルータやネットワークへの最短経路木を求めて(SPF)経路表を作る [wide.ad.jp]ために使います。
SPFの計算量はO((リンク数) x log(ノード数)) [wide.ad.jp]だそうで。最も、めったやたらにリンク数を増やしているのでなければ、問題はむしろlink stateの交換 [wide.ad.jp]だったりするようですが。これもネットワークの構造が複雑になると大変だけど。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
「毎々お世話になっております。仕様書を頂きたく。」「拝承」 -- ある会社の日常
よく わからん (スコア:1)
「家から駅までの最短経路」
なんて問題をどうやってDNAにコード化するんだろう?
Re:よく わからん (スコア:1)
例えば、でしょ(W
巡回セールスマン問題。NPコンプリートだったっけ?
実用化レベルになったとすれば凄いこと。
家から駅までの最短経路 (スコア:0)
「DNAコンピュータ」がNP完全問題を現実的時間内で解ける力を持ち得ると 期待される点については その通りと思いますが、 「家から駅までの最短経路」は「巡回セールスマン問題」とは違って、 完全解を得る効率的なアルゴリズムがすでに存在しますね、 ってことで念のため。:)
Dijkstra's Algorithm [acm.org]が定番。
NP完全問題の例のつもりで挙げたのを読売新聞が間違えた、とかいうことでなければ、 単にDNAコンピュータでプログラミングしやすい例を挙げただけなんじゃないでしょうか。
で、やっぱりどうやってプログラミングするんだろうってのが素朴な疑問なんですが。 そーぞーするに、白衣着て試験管振るようなコーディング風景であろうか。 DNAコンピュータなら、情報処理技術者も、 晴れて映画に出てくる「カガクシャ」の格好ができそうだなあ。:-D
Dijkstraの応用例: OSPF (スコア:2, 参考になる)
Dijkstraを実際に用いている身近な例としては、OSPFがありますね。Topological Databaseの構築を受け、各ルータやネットワークへの最短経路木を求めて(SPF)経路表を作る [wide.ad.jp]ために使います。
SPFの計算量はO((リンク数) x log(ノード数)) [wide.ad.jp]だそうで。最も、めったやたらにリンク数を増やしているのでなければ、問題はむしろlink stateの交換 [wide.ad.jp]だったりするようですが。これもネットワークの構造が複雑になると大変だけど。
Re:家から駅までの最短経路 (スコア:0)