基本情報技術者試験 - 平成29年春期(科目B) - 問8

問題

 次のプログラムの説明及びプログラムを読んで,設問1,2に答えよ。

 副プログラムShortestPathは,N個(N>1)の地点と,地点間を直接結ぶ経路及び距離が与えられたとき,出発地から目的地に至る最短経路とその距離を求めるプログラムである。最短経路とは,ある地点から別の地点へ最短距離で移動する際の経由地を結んだ経路である。副プログラムShortestPathでは,出発地の隣接地点から開始して,目的地に向かって最短距離を順次確定する。ある地点の隣接地点とは,その地点から他の地点を経由せずに直接移動できる地点のことである。
 図1は,地点数Nが7の経路の例で,経路をグラフで表現したものである。図1において,丸は地点を示し,各地点には0から始まる番号(以下,地点番号という)が順番に割り当てられている。線分は地点間を直接結ぶ経路を示し,線分の上に示す数字はその距離を表す。また,経路上は,双方向に移動できる。



〔プログラムの説明〕
(1) 副プログラムShortestPathの引数の仕様を,表1に示す。ここで,出発地から目的地までを結ぶ経路は,少なくとも一つ存在するものとする。また,配列の要素番号は,0から始まる。
表1 副プログラムShortestPathの引数の仕様
引数データ型入出力説明
Distance[][]整数型入力地点間の距離が格納されている2次元配列
nPoint整数型入力地点数
sp整数型入力出発地の地点番号
dp整数型入力目的地の地点番号
sRoute[]整数型出力出発地から目的地までの最短経路上の地点の地点番号を目的地から出発地までの順に設定する1次元配列
sDist整数型出力出発地から目的地までの最短距離

(2) Distance[i][j](i=0,…,nPoint-1;j=0,…,nPoint-1)には,地点iから地点jまでの距離が格納されている。ただし,地点iと地点jが同一の地点の場合は0,地点iが地点jの隣接地点ではない場合は-1が格納されている。図1の例における配列Distanceの内容は,表2のとおりである。
表2 図1の例における配列Distanceの内容
i\j0123456
00284-1-1-1
120-1-13-1-1
28-10-123-1
34-1-10-18-1
4-132-10-19
5-1-138-103
6-1-1-1-1930

(3) 行番号5~10では,変数,配列に初期値を格納する。
 ① 最短距離を返却する変数sDistに初期値として∞(最大値を表す定数)を格納し,出発地から目的地までの最短距離が設定されていないことを示す。
 ② 最短経路を返却する要素数がnPointである配列sRouteの全ての要素に初期値として-1を格納し,最短経路上の地点の地点番号が設定されていないことを示す。
 ③ 出発地から各地点までの最短距離を設定する配列をpDistとする。pDistは1次元配列であり,要素数はnPointである。配列pDistの全ての要素に初期値として∞を格納する。
 ④ 出発地から各地点までの最短距離が確定しているかどうかを識別するための配列をpFixedとする。pFixedは1次元配列であり,要素数はnPointである。配列pFixedの全ての要素に初期値としてfalseを格納し,最短距離が未確定であることを示す。最短距離が確定したときにtrueを設定する。例えば,出発地から地点iまでの最短距離が確定したとき,pFixed[i]はtrueとなり,その最短距離はpDist[i]に設定されている。pFixed[i]がfalseの場合は,地点iまでの最短距離は未確定であり,pDist[i]の値は最短距離として確定されていない。
(4) 行番号11では,出発地から出発地自体への最短距離pDist[sp]に0を設定する。
(5) 行番号12~39の最短経路探索処理では,出発地から各地点までの最短距離を算出しながら,最短経路を求める。
 ① 行番号13~22
  配列pFixedを調べ,出発地から全ての地点までの最短距離が確定していれば,最短経路探索処理を抜けて(6)に進む。
 ② 行番号23~29
  出発地からの最短距離が未確定の地点の中で,出発地からの距離が最も短い地点を探し,その地点をsPointとし,その地点の最短距離を確定する。
 ③ 行番号30~38
  各地点に対して(ア),(イ)を実行し,①に戻る。
 (ア)地点sPointの隣接地点であり,かつ,出発地からの最短距離が未確定であるかどうかを調べる。
 (イ) (ア)の条件を満たす地点jに関して,出発地から地点sPointを経由して地点jに到達する経路の距離を求め,その距離が既に算出してあるpDist[j]よりも短ければ,pDist[j]及びpRoute[j]を更新する。ここで,pDist[j]は,出発地から地点jまでの仮の最短距離となる。pRoute[j]には,そのときの,地点jの直前の経由地の地点番号を設定する。
(6) 行番号40~48では,出発地から目的地までの最短距離をsDistに,最短経路上の地点の地点番号を目的地から出発地までの順に配列sRouteに設定する。


設問1  プログラム中の [   ] に入れる正しい答えを,解答群の中から選べ。

aに関する解答群
アnot(pFixed[i])
イnot(pFixed[j])
ウpFixed[i]
エpFixed[j]

bに関する解答群
アdp
イnPoint
ウnPoint-1
エsp
オsPoint

cに関する解答群
アpRoute[dp]
イpRoute[i]
ウpRoute[j]
エpRoute[sp]
オsRoute[dp]
カsRoute[i]
キsRoute[j]
クsRoute[sp]

dに関する解答群
アpRoute[dp]
イpRoute[i]
ウpRoute[j]
エpRoute[sp]
オsRoute[dp]
カsRoute[i]
キsRoute[j]
クsRoute[sp]

設問4  次の記述中の [   ] に入れる正しい答えを,解答群の中から選べ。

 図1において,出発地の地点番号spの値が0,目的地の地点番号dpの値が6の場合について,プログラムの動きを追跡する。行番号12~39の最短経路探索処理の繰返しで,行番号28のαにおいてsPointに代入された値は,繰返しの1回目は0,2回目は1,3回目は [ e ] となる。また,行番号30~38の処理が終了した直後のβにおける配列pDistと配列pRouteの値を,表3に示す。最短経路探索処理の繰返しが3回目のときのβにおける配列pDistの値は [ f ] となり,配列pRouteの値は [ g ] となる。ここで,配列pRouteの全ての要素には初期値として0が格納されているものとする。
表3 βにおける配列pDistと配列pRouteの値
最短経路探索処理の繰返し配列pDist配列pRoute
1回目0,2,8,4,∞,∞,∞0,0,0,0,0,0,0
2回目0,2,8,4,5,∞,∞0,0,0,0,1,0,0
3回目[ f ][ g ]
︙︙︙


eに関する解答群
ア2
イ3
ウ4
エ5
オ6

fに関する解答群
ア0,2,8,4,5,10,14
イ0,2,8,4,5,10,∞
ウ0,2,8,4,5,11,14
エ0,2,8,4,5,11,∞
オ0,2,8,4,5,12,14
カ0,2,8,4,5,12,∞

gに関する解答群
ア0,0,0,0,1,3,0
イ0,0,0,0,1,3,5
ウ0,0,0,0,2,2,0
エ0,0,0,0,2,2,5
オ0,0,4,0,1,2,0
カ0,0,4,0,2,2,5

正解と解説

正解設問1 (a)イ 設問2 (b)オ 設問3 (c)キ (d)イ 設問4 (e)イ (f)カ (g)ア 
分野テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズム

解説

■ 問題の概要

 出発地から目的地までの最短経路を求める「ダイクストラ法」のプログラムを完成させ,動きを追跡する問題です。

 ダイクストラ法の考え方は,次のとおりです。
  • 出発地からの距離が確定していない地点の中で,最も距離が短い地点を選び,その距離を確定させます。
  • 確定した地点の隣の地点について,確定した地点を経由した方が近ければ,距離を更新します。
  • 全ての地点の距離が確定するまで,これを繰り返します。

 プログラムで使う配列の意味は,次のとおりです。
  • pDist[i]:出発地から地点iまでの(その時点での)最短距離
  • pFixed[i]:地点iの最短距離が確定したかどうか
  • pRoute[i]:地点iの直前に経由する地点の番号

■ 設問1

 正解は,空欄aが「イ」,空欄bが「オ」,空欄cが「キ」,空欄dが「イ」です。

【空欄a】

 行番号13~19で,未確定の地点を一つ見つけてiとします。行番号23~27では,それより後ろの地点jについて,「未確定」で,かつ「iより距離が短い」ものがあれば,iをjに置き換えます。こうして,未確定の地点の中で距離が最も短い地点を探します。したがって,空欄aは「未確定」を表す「not(pFixed[j])」(「イ」)です。

【空欄b】

 行番号28で,最も距離が短い地点をsPointとしました。行番号29は,その地点の最短距離を確定させる処理なので,pFixed[sPoint]をtrueにします。空欄bは「オ」です。

【空欄c,d】

 行番号40~48では,最短経路を目的地から出発地の順にsRouteに格納します。pRoute[i]には「地点iの直前の地点」が入っているので,目的地からpRouteを順にたどれば,出発地まで戻れます。
  • 行番号44:現在の地点iを,sRouteのj番目に格納します。したがって,空欄cは「sRoute[j]」(「キ」)です。
  • 行番号45:iを直前の地点に移します。したがって,空欄dは「pRoute[i]」(「イ」)です。
  • 行番号48:最後に出発地spを格納します。

■ 設問2

 正解は,空欄eが「イ」,空欄fが「カ」,空欄gが「ア」です。出発地0,目的地6の場合を追跡します。表3より,2回目の繰返しが終わった時点では,pDistは「0,2,8,4,5,∞,∞」で,地点0と地点1が確定しています。

【空欄e】

 3回目の繰返しでは,未確定の地点(2,3,4,5,6)の中で距離が最も短い地点を選びます。距離はそれぞれ8,4,5,∞,∞なので,最も短いのは地点3(距離4)です。したがって,空欄eは「イ」の3です。

【空欄f,g】

 地点3を確定させた後,地点3の隣で未確定の地点の距離を更新します。地点3の隣は地点0と地点5ですが,地点0は確定済みなので,地点5だけを調べます。

 地点3を経由した地点5までの距離は,4+8=12です。これまでの距離∞より短いので,pDist[5]を12に,pRoute[5]を3に更新します。その結果,pDistは「0,2,8,4,5,12,∞」(「カ」),pRouteは「0,0,0,0,1,3,0」(「ア」)となります。

 なお,地点5までの本当の最短距離は,0→1→4→2→5の経路の2+3+2+3=10ですが,3回目の時点ではまだその経路の地点が確定していないため,この時点では12となります。このように,pDistは途中では「仮の」最短距離であり,確定した時点で初めて本当の最短距離になる点に注意してください。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる