はじめまして。
「データ構造とアルゴリズム」を独学で勉強中の学生です。
当方、周りより指導していただける環境が無く
どうにも行き詰まってしまったのでここに書き込みをさせていただきました。
お聞きしたい問題なのですが
「最短路問題について問題の定義と解法(アルゴリズム)を説明せよ。次に図1においてpから全ての頂点への最短路を求めよ。」
というものです。
* 図1はhttp://www.geocities.co.jp/Hollywood-Stage/3151/ …にupしてあります。
最短路問題を解く方法としてダイクストラのアルゴリズムやFloydのアルゴリズムがありますが、これらは書籍などを参考にして理解しているつもりです。
しかし実際、問題を解く手順といいますか、解答を書くことができないのでどなたかおわかりになる方がいらっしゃいましたらご指導をいただきたいと思い書き込みをさせていただきました。
学習不足で怠慢な学生の質問で大変申し訳ありませんが
ご指導のほどよろしくお願いいたします。

このQ&Aに関連する最新のQ&A

A 回答 (1件)

「アルゴリズムを説明せよ」って


言われたら、私なら、参考書に良く
出ている、「ステップ1 …を…する」
とかいう、あれを書きます。

ダイクストラのアルゴリズムの場合、
例えば、こんな風に書けるんじゃない
でしょうか?

[定義]
・ノードiからノードjの仮の最短距離を
 d_ijとし、その初期値は全て∞とする
・ノードiと直接つながっているノード(隣接ノード)
 番号の集合を
  N_i = {n_i1, n_i2, … }
 とする
・ノードiと、その隣接ノードjの間の距離をl_ijとする
・他のノードへの最短距離を求めるべき初期ノード
 (出発点)の番号をpとする
・最短経路を構成するアーク(ノードiとノードjを
 結ぶアークを(i,j)と表す)を要素とする集合をRとし、
 その初期値は空集合とする
・全てのノードの番号を要素に持つ集合をMとする

[アルゴリズム]
ステップ1.
 初期化:
 ・初期ノードpの仮の最短距離を0にする
   d_pp := 0
 ・変数aを初期ノードの番号pで初期化
   a := p
 ・集合Mからpを取り除く

 ステップ4へ

ステップ2.
 集合Mの要素であるノードのうち、初期ノードpからの
 仮の最短距離が最小のノードを求め、
 その番号をaに代入する
  a = argmin_(i∈M) d_pi

ステップ3.
 Mに含まれないaの全ての隣接ノードについて、
 各ノードの仮の最短距離とノードaまでの距離の和が
 最小のアークを選び、最短経路として登録する
  b = argmin_(i not∈M) (d_pb + l_ab)
  R := {{R}, (b, a)}

ステップ4.
 Mに含まれるaの全ての隣接ノードについて、
 各ノードの仮の最短距離が、ノードaまでの仮の
 最短距離とノード間距離の和より大きい場合、
 その値を更新する
  for all i (∈ N_a)
   if d_pi > d_pa + l_ai
    d_pi := d_pa + l_ai

ステップ5.
 Mが空集合であれば終了。Rの要素が最短経路を
 構成する全てのアークである。また、pから
 ノードiへの最短距離はd_piである。
 Mが空集合でなければステップ2へ。
  if M = φ
   end
  otherwise
   go to step 2

このように、自分で必要な変数を定義し、それを
使って曖昧性が少なくなるよう、集合論の記号や
数式を駆使して、各ステップのオペレーションを
表現します。

補足ですが、グラフ理論を勉強されている方には
失礼かと思いますが、上で「ノード」とは各頂点
(葉)を表し、「アーク」とは隣接する地点間を
結ぶ線分(枝)を表す抽象的な用語です。
    • good
    • 0
この回答へのお礼

お礼が遅くなってしまって申し訳ありませんでした。
ご回答ありがとうございました。
参考にさせていただきます。

お礼日時:2001/08/31 02:02

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aと関連する良く見られている質問

Qこの問題の途中式を教えてください 2×1/16+4×1/16^2+8×1/16^3 =1/4×16+

この問題の途中式を教えてください
2×1/16+4×1/16^2+8×1/16^3
=1/4×16+1/2×16×16
=64+8+1/512
=73/512

Aベストアンサー

一番分母の大きくなるところを計算します。
 8×1/16^3=8×1/(2×8×16^2)=1/(2×16^2)=1/512
分子と分母を8で割って約分しています。

分母を(2×16^2)=512に揃えることを考えて、足りない分をかけます。
 2×1/16=(2×2×16)/(16×2×16)=64/(2×16^2)=64/512 (2×16をかける)
 4×1/16^2=(4×2)/(16^2×2)=8/512

よって
 2×1/16+4×1/16^2+8×1/16^3
  =64/512+8/512+1/512
  =(64+8+1)/512
  =73/512

Qモル濃度についての問題です。 この問題で溶質を求めるときに なぜ30[g]/60[g/mol]になる

モル濃度についての問題です。
この問題で溶質を求めるときに
なぜ30[g]/60[g/mol]になるのかがわからないので教えてください。よろしくお願いします

Aベストアンサー

問題の肝心の部分が無いのですが…
式から推測するに、30gというのは溶かした化合物の質量(g)ですよね。
60g/molというのは式量もしくはモル質量というもので、1モルあたりの質量です。
60g/molということはプロパノール辺りが考えられますが…これだけではよく判りません。

化合物の質量(g)/モル質量(g/mol)の計算をすることで、化合物の物質量(分子の数)が何モル存在していのかが判ります。
30(g)/60(g/mol)=0.5(mol) 0.5mol存在していることになります。
モル濃度は溶液の単位体積当たりの溶質のモル数なので、0.5molを0.200Lで割って1L当たりのモル濃度を2.5mol/Lと求めています。

Q高2/夏/受験対策/問題集

こんにちは。
私はいま高2なのですが、部活も特にやっていないし、この夏休みに、ぐうたら防止のため"受験勉強"なるものを初めてみようと思っています\^Д^/
そこで英語と世界史の問題集等についてのおすすめを聞きたくて質問させていただいてます><!
問題集については検索しましたがレベル等によってアドバイスが変わってくると言われてる方がいたので質問させてください><

自分のレベルの情報としてはこんなんです><

世界史→定期テストの順位的には一応常に1割には入る感じ(←しょーもない情報でごめんなさい><)

英語→TOEIC900点以上所持
(長期留学経験/高校では国際教養科在学中)

目指す大学などはまだハッキリしていませんが、国公立はあんまり頭にありません。外大とか私大で英語が強いところがいいなーという漠然とした目標ならあるのですが…。

長々と失礼致しました!
回答お願い致します!
(英語に関しては、問題集以外にも単語帳?みたいなのも探し中です)

Aベストアンサー

学校のレベルが分からないので定期テストについては何ともいえませんが
夏休みが暇なら世界史の先取りを行ってみたらどうでしょうか?
全部買うと費用がかかりすぎますが『青木世界史Bの実況中継』をお勧めします。
まだ習っていない部分だけ買うとよいと思います。
結構楽しく勉強できると思いますよ

英語は私にはよくわかりませんが
とりあえずターゲット1900とかをやってみて受験に出る単語のレベルをたしかめたらよいのではないですか?

受験勉強がんばってください

Qこの問題を解いて、私は答えが1番だと思ったのですが不正解でした。 なお、この問題には解説がないため

この問題を解いて、私は答えが1番だと思ったのですが不正解でした。
なお、この問題には解説がないため
なんで違うのかがわかりません(>_<)
すいません。この問題の解き方の解説をお願いしたいです。よろしくお願いします(>_<)

Aベストアンサー

まず、問題文は累積度数なので、階級度数に直す必要があります。
直すと、25歳未満:45、25~35歳未満:75、35~45歳未満:65、45~55歳未満:35、55歳以上:15となります。
1.25~35歳未満の相対度数=75/235≒0.32となり、0.51ではありません。
2.35~45歳未満の累積相対度数=185/235≒0.79となり、0.28ではありません。
3.45歳以上の社員数=35+15=50人、45歳未満の社員数=185人です。 したがって、50/185≒0.27→約27%です。 したがって、正解は3です。
4.中央値は、235/2=117.5の人数を累積度数に含む階級にあります。 したがって、25~35歳未満の階級にあるので、37.5歳ではありません。

Q(3)の問題でx=2, 2/3になったんですが、範囲が1以上3以下になっているので、表で2/3が最初

(3)の問題でx=2, 2/3になったんですが、範囲が1以上3以下になっているので、表で2/3が最初にくるのはおかしいと思うんですが、xがどうしても2/3になるので最初が2/3になってしまいます。どうすればいいのでしょうか? まとまりのない文でごめんなさい(><)

Aベストアンサー

y=x^3-4x^2+4x+1
y’=3x^2-8x+4
=(3x-2)(x-2) → x=2/3,2 の時、yは極大極小をとる
それとは別に1≦x≦3の範囲があるということです。

x1…2…3
y’ -0+
y2※9/4 ※の所は右下向きの矢印


人気Q&Aランキング

おすすめ情報