Question

か

なぜQはMに5たして20ではなく、25になるのか教えてください。

は新宿駅から上野駅までの移動をモデル化するにあたり、 実際の駅名は
アルファベットに置き換え, 図2のようなモデルを作成した。 スタートの新宿駅
はA, ゴールの上野駅はQであり, 各線に書かれた数値は二駅間の平均所要時間
2
(分) を表している。
4
(B) 7 (00) ALG
8 2
4
A
E
7
6
C
2
4
8
18
6
21
17
(H)
3
2
J
4
5
3
10
K
9
2
**
2
(M)
5
図2 Sさんが作成した東京中心部の路線図のモデル
Sさんが普段通学で使う経路は、A→I→K→N→O→P→Qであり.
モデル図から求まる平均所要時間は16分であり, Sさんが実際の通学時にか
かっている時間も16分程度であり、モデルと現実の誤差が小さいことが分かった。
(1)

問2
ADVEN
次の文章を読み、表1の空欄サ
4
AJTF5 F10 SE
Sさんは、最短経路を調べる問題を総当たりで解くのではなく,効率的に解
アルゴリズムを調べた。 1つ目の方法は、 すべての線を総当たり的に調べな
がら、頂点(駅)までの所要時間を最小の値に更新していくベルマン・フォード
法である。
初期値は,Aは0. A以外の頂点は無限大(∞) とする。
(0
∞
6
E
える
A
F
4
B
7
6
7
8
2
HA
4
8
7
8 2
8
6
21
8(G)
8
H
T
17
8
3 5
12
4
8
ナに当てはまる数字をマークせよ。
3
10
9
8
(K)
6
LS
5
2
2
図3 初期値を設定した状態
O
(Z)
2
8
2
Mo
5
5
AUNTS
05.0
-33 (00-00% . 03/SHAR
5

次にAを起点とした線を調べながら、各頂点の値が小さくなる場合は更新
していく。
KAE
H
++ p co
4
14 (B) 70
15-3
4
JJRD4
6
(限) ⑥ )
A
(4)
(0
4
(B)
4
6
(A)
ス 6
20
6
7
4
8
7
8
6
(D
①
8
12
OF
4
8
8G21 3
21
8
⑥E
WAJG JESU
G
8
(H)
6
17
10
F
Doo
ON L
図4 Aを起点とした5本の線の更新が終わった状態
2
1.
4
ASSO
次に,Bを起点とした線を,Bまでの所要時間(4分)を加算しながら調べ,
各頂点の値が小さくなる場合は更新していく。ここではFとHが更新される。
また,Cを起点として線を調べると,Fは14分 Hは15分,Dは9分となり、
これまでに求まった値よりも大きくなるため、どの頂点も更新されない。 さら
に,D,E,F,G,H,I,J を起点とした線を順に調べ、表1にまとめた。
5
G
21
8
3(C
8,
3
2
(H)
3
17
12
10
4
5
DO
2
8/
(K)
9
5
3
2
6
19 -
10
2
80
KO
9
Q
2
1
5
6
2
N) ∞
2
350ATOR
2
5
2
O
2
Z
2
Mo.
5
5 NA
Loo
TESTIMO
図5 A, B, C を起点とした計10本の線の更新が終わった状態