- ベストアンサー
最短路問題解法の最新動向
pori_boyの回答
こんにちは 数年前になりますが，DIMACSというところで最短路問題を 対象としたコンペティションが行われていました． http://www.dis.uniroma1.it/~challenge9/ この中で，次の問題に対する様々な研究が行われました． 問題：巨大なグラフ（点の数が数万から数百万程度）が与えられる． このグラフの2点が指定されたとき，その間の最短距離を即座に答えよ． ただし，与えられたグラフに対するさまざまな前処理を認める． 多くの研究結果が発表されてきており，中にはScienceで発表された ものもありますので，興味があれば読んでみるとよいと思います．
関連するQ&A
- 最短路問題について
はじめまして。 「データ構造とアルゴリズム」を独学で勉強中の学生です。 当方、周りより指導していただける環境が無く どうにも行き詰まってしまったのでここに書き込みをさせていただきました。 お聞きしたい問題なのですが 「最短路問題について問題の定義と解法(アルゴリズム)を説明せよ。次に図１においてpから全ての頂点への最短路を求めよ。」 というものです。 * 図１はhttp://www.geocities.co.jp/Hollywood-Stage/3151/g/g.gifにupしてあります。 最短路問題を解く方法としてダイクストラのアルゴリズムやFloydのアルゴリズムがありますが、これらは書籍などを参考にして理解しているつもりです。 しかし実際、問題を解く手順といいますか、解答を書くことができないのでどなたかおわかりになる方がいらっしゃいましたらご指導をいただきたいと思い書き込みをさせていただきました。 学習不足で怠慢な学生の質問で大変申し訳ありませんが ご指導のほどよろしくお願いいたします。
- ベストアンサー
- その他（学問・教育）
- 最先端の研究について
1)蛍光を用いたバイオイメージング法を用いた具体的な研究応用例を調べていますが、何か参考になるページはありますでしょうか？ よろしくお願いします。 また 2)リポソームの薬物運搬体としての働きやその他の研究への応用例を調べたいのですが、参考になるページがありましたら教えてください。 よろしくお願いします。 3)生命科学の研究分野で最近注目されている先端的分析手法についてどのようなものがあるか調べていますが、何か参考になるページがありましたら教えてください。
- 締切済み
- 科学
- 身長を伸ばす手術ISKD法は日本では受けられない？
イリザロフ法に比べ感染症の可能性や痛みが少ないらしく注目しているのですが、日本で現在行っている病院はありませんか？ 無いとして、この手法はどうなれば、また、いつになれば日本で可能になるのでしょうか？医師が勉強したら？法的な問題？何が障害となっていて日本では行われないのでしょうか。 お金は用意できるのですが、イリザロフ法は痛みが酷く成人男性が泣いて1センチの延長でやめてしまったなどとも聞くので、 そんなことになっては感染症のリスクだけ負い、まさに骨折り損というか…、躊躇せざるをえません。
- 締切済み
- その他（病気・怪我・身体の不調）
- 二次方程式の解放についてご意見をください！
下のイメージ欄にあげた二次方程式の解法についての質問です。 以下のURLに、私の解答をgif画像でおいておきましたので、 添削をいただくような形でご意見をいただけたらと思います。 http://kite-badge.hp.infoseek.co.jp/Question.html （画像が大きすぎて見にくいのと、字がツブれかけている点、申し訳ありません） ＜問題の場面について＞ 高校数学IIの「図形と方程式」分野のなかでの途中計算でして、 あとはxとｙを求めればよい…。という場面です。 問題に付いていた解答集を読みますと、以下の二次方程式が示された後、 「(1)，(2)より（x，y）＝・・・」と書かれているのみです。しかしながら私の解答が 最短であるとするならば、省略するにはややこしい二次方程式だと感じます。 省略される程度の、もっとスマートな解法があるのかな？と懐疑している状態です。 詳しい方でなくても、ほんの感想や、「私ならこうアプローチするかな」といったようなことでも かまわないので、多くのご意見をいただきたいと思っています。 よろしくお願いいたします・・・。 （↓見た目では「簡単そうだ」と踏んだのですが、思ったほどうまくいかなくて・・・。）
- ベストアンサー
- 数学・算数
- グラフ構造のアルゴリズムの問題です。
グラフ構造のアルゴリズムの問題です。 頂点間の最短距離を求める問題ですが、どうすれば良いかわかりません......。ダイクストラ法などを使うのでしょうか？ 何のアルゴリズムを利用するのかという点と、解法の手順を解説していただけると幸いです。 以下、問題文です。 v1,v2,v3,..., v9,v10 の 10 個の頂点からなる重みつき無向グラフ G の全頂点間の最短距離を計算したい。こ こで dk(i,j) を頂点 vi から頂点 vj への「経由してよい頂点を v1,...,vk に限定した」最短距離とする。例えば, d3(i,j)は「経由してよい頂点が v1,v2,v3 に限定された」vi から vj への最短距離となる。 ただし,v1,...,vk までの頂点のみを経由するような vi から vj への経路がない場合は dk(i,j)を∞とする。 いま,「経由してよい頂点を v1～v6 に限定した」全頂点間の最短距離がそれぞれ d6(1,2)=3 d6(1,3)=12 d6(1,4)=∞ d6(1,5)=4 d6(1,6)=6 d6(1,7)=∞ d6(1,8)=4 d6(1,9)=8 d6(1,10)=9 d6(2,3)=5 d6(2,4)=∞ d6(2,5)=2 d6(2,6)=3 d6(2,7)=∞ d6(2,8)=1 d6(2,9)=6 d6(2,10)=3 d6(3,4)=∞ d6(3,5)=5 d6(3,6)=2 d6(3,7)=∞ d6(3,8)=6 d6(3,9)=9 d6(3,10)=5 d6(4,5)=∞ d6(4,6)=∞ d6(4,7)=2 d6(4,8)=∞ d6(4,9)=∞ d6(4,10)=4 d6(5,6)=5 d6(5,7)=∞ d6(5,8)=3 d6(5,9)=4 d6(5,10)=8 d6(6,7)=∞ d6(6,8)=4 d6(6,9)=9 d6(6,10)=3 d6(7,8)=3 d6(7,9)=∞ d6(7,10)=1 d6(8,9)=4 d6(8,10)=7 d6(9,10)=12 であった。この情報をもとに以下のそれぞれの値を求めよ。 (1)d7(1,10) (2)d7(4,8) (3)d7(4,10) (4)d8(1,10) (5)d8(4,5) お手数お欠けしますが、どうかよろしくお願い致します。
- ベストアンサー
- 数学・算数
- ＵＳＥＮって・・・
こんにちは。 メディアにからんだネットビジネスの動向に興味があります。 特に、ＵＳＥＮのＧｙａＯにかなり注目しています。 しかし、今のＧｙａＯにはかなり不満というか問題点が多数あるように感じます。 友人などに聞くと「（コンテンツが）大好き」だとか 「（ビジネスとして）今後が楽しみ」といった声が多いですが、 私個人としては、あれほど魅力的なインフラを有効に活用できていないように感じるのです。 コンテンツに関しても、 経営者を招いての対談番組「リアルビジネス」など、 宇野社長の自己満足にしかみえません。 まだまだこれからの分野だとは思うのですが、 いったい宇野社長はＧｙａＯで何をしたいのでしょう？ あれがあらたなマスメディアになると思っているんでしょうか？
- ベストアンサー
- インターネットビジネス
- 固有値問題のような問題
いま、取り組んでいる問題が下記の形に帰着できたのですが、 それから先に進まず困っております。 ■問題 A ： 2N x 2N の実対称行列 a(i) ： 2 次元の列ベクトル。 i = 1,...,N。 ただし、各 a_i の大きさは１。（ a_i ・ a_i = 1 ） a： 2N 次元の列ベクトル。{ a_i | i=1,...N } の 2N 個の要素を縦に並べたもの。 λ(i) ： 実数。i = 1,...,N。 添付画像の式が成り立つときに、a(i) を求めたいです。 ■今のアプローチ 今のところ思いつくアプローチは以下のようなものですが、 問題の特性を活かした、もう少し、良い方法は無いかと思っています。 a． a(i) = ( cosθ_i , sinθ_i ) とおいて、 a_i ・ a_i = 1 の制約式を無くして、 N 変数の連立方程式を数値的に探索する。 b．逐次２次計画法による繰り返し計算 c．行列 A を対角化してみましたが、その後、解に繋がりません。 ■補足 可能な限り解析的に求めたいと思っていますが、 無理であれば、もちろん、数値的解法もご提案ください。 もちろん、こんな分野を探してみては？ という情報でも構いません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 【安保問題】安保法案が衆議院で閣議決定されて、日本
【安保問題】安保法案が衆議院で閣議決定されて、日本の首都の東京の国会議事堂と大阪のJR大阪駅で大規模反対デモが行われています。 安保法案のどこが問題なんでしょうか？ 安保法案によって日本が戦争が出来るようになった。外国と戦争する前に国内デモという内紛が起こって国内情勢を悪化させて政治が必要だと国民に思わせるのが平和時の時事政治問題が無さすぎて政治の意味の無さを国民が感じ始めたときに国内情勢をわざと政治家が政治でかき回して、やはり政治で治安を安定させないといけないと思わせる。古典的な政治手法です。 あとアメリカから指示されて安倍首相は動いてますよね。 国のトップが安倍首相が考えて安保法案を成立させようと躍起になっているわけでなく、親であるアメリカ様の指示なので従うしかない。 違いますか？ アメリカは日本の内政を乱す社会不安を生み経済成長を鈍化させるのが目的。 違いますか？
- ベストアンサー
- ニュース・時事問題
補足
ご教授をありがとうございます。 URLも拝見させていただきましたが、この数十年の間は画期的な最短路 の解法が発見されていないようが気がしてなりません。 どうやら 1. 数学的にではなく、如何にコンピュータ処理をするかという方向が メインのひとつのようですね。 2. 現実問題への取り組みはまだまだですね。 ３.議論の媒体があればよろしいと思います。 あたらめて、有り難うございます。