基本情報技術者過去問題 平成24年秋期 午後問8

問8 

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

 鉄道の路線がある。駅数 N は2以上で,各駅には駅番号(1,2,…,N)が付いている。どの任意の2駅間にも,それらを結ぶ経路が一つ以上存在する。また,隣接する2駅間を直接結ぶ経路は一つだけ存在し,その距離が与えられている。図1に5駅からなる鉄道の路線例を示す。
〔プログラムの説明〕
 副プログラム CalcDist は,駅数N及び要素数N×Nの2次元配列 Dist を受け取り,プログラムに示すアルゴリズム(Warshall-Floyd 法)によって,配列 Dist の内容を更新しながら各駅間の最短距離を求めていく。実行が終わると,任意の2駅 i,j 間の最短距離が Dist[i][j] に求められている。どの2駅間についても,その最短距離は 999 より小さいものとする。配列 Dist の添字は1から始まる。
 副プログラム CalcDist に渡す配列 Dist には,次の値を格納する。
 なお,図1の路線情報を格納した配列 Dist の内容を,図2の初期値に示してある。
  • 2駅 i,j が隣接しているとき,Dist[i][j] 及び Dist[j][i] には,その駅間距離を格納する。例えば,図1の駅@とAは隣接しているので,Dist[1][2] 及び Dist[2][1] には,18を格納する。
  • 2駅 i,j が隣接していないとき,Dist[i][j] 及び Dist[j][i] には,未確定を表す距離 999 を格納する。例えば,図1の駅@とBは隣接していないので,Dist[1][3] 及び Dist[3][1] には,999 を格納する。
  • 各駅iについて,Dist[i][i] には0を格納する。
 副プログラム CalcDist 中の Print(N,Dist) は,配列 Dist のその時点の内容を印字する副プログラムである。
 図1の路線情報を配列 Dist に格納して,CalcDist を実行した。配列 Dist の内容の 変化を print(N,Dist) で印字した結果は,図2のとおりであった。
 駅数Nに関して,副プログラム CalcDist の計算量のオーダはc,またメモリ使用量のオーダはdである。そこで,駅数Nが大きい場合に,計算量やメモリ使用量を減らすための方法を考える。

 例えば,配列 Dist の対称性に着目し,プログラム中の の部分を,
 とすれば,繰返し処理中の選択処理の実行回数を約半分に減らすことができる。
 次に,少ないメモリ使用量で,任意の2駅 i,j 間の最短距離を求める方法を考える。
 駅を,乗換駅(3方向以上に隣接する駅がある),終端駅(1方向だけに隣接する駅がある),中間駅(2方向だけに隣接する駅がある)の3種類に分ける。乗換駅と終端駅を合わせて基幹駅と呼ぶ。基幹駅の数を K として,駅番号 1〜K が基幹駅,駅番号 K+1〜N が中間駅となるように駅番号を定める。ここで,K≧2であるとする。図3の路線例では,駅@〜Bが乗換駅,駅Cが終端駅,駅D〜Iが中間駅である。
各駅間の最短距離は,次の方法で求める。
  • 中間駅を全て除いて,基幹駅だけからなる路線を考え,二つの基幹駅を結ぶ経路ごとに一意の区間名を付ける。図3の路線例にこの操作を加えたものが図4である。例えば,図3の経路@−D−E−Bは,図4の区間Bに対応する。
  • 要素数 K×K の2次元配列 Dist を用意し,事前に配列 Dist に各基幹駅間の最短距離を求めておく。
  • 全ての駅について,表1に示す形式の駅情報表を用意する(表1には,図3の駅情報の一部が示してある)。
     中間駅の場合,Sec はその駅が属する区間の区間名,KL,KHはその駅が属する区間の両端の駅番号(KL ≦ KHとする),ToKL,ToKHはその駅から駅 KL,KH までの距離である。基幹駅の場合,その駅は自分自身の駅を両端とする距離0の区間に属すると考えて,表1の例のように中間駅と同様の情報を用意する。
     これらの情報は,駅番号を添字として参照する。例えば,駅番号5のToKLの値はToKL[5] として参照する。
  • 2駅 i,j 間の最短距離を求める。一般に,両駅が属する区間が異なる場合,駅iから駅jへ行く経路は,
        (駅i)→(駅iが属する区間のいずれか一端の基幹駅)
        →(駅jが属する区間のいずれか一端の基幹駅)→(駅j)
    となる,したがって,次の式で求める4通りの値D1,D2,D3,D4のうちの最小値が,2駅 i,j 間の最短距離となる。
    • D1←ToKL[i]+Dist[KL[i]][KL[j]]+ToKL[j]
    • D2←ToKL[i]+Dist[KL[i]][KH[j]]+ToKH[j]
    • D3←ToKH[i]+Dist[KH[i]][KL[j]]+ToKL[j]
    • D4←ToKH[i]+Dist[KH[i]][KH[j]]+ToKH[j]
     両駅が属する区間が同じ場合は,区間の端の基幹駅を経由せずに直接駅iから駅jへ行く経路がある。これも考慮すると,任意の2駅 i,j 間の最短距離 Res は次の処理で求められる。ここで,関数 min(式1,式2,…)は,式1,式2,…の値の最小値を返す関数であり,関数 abs(式) は,式の値の絶対値を返す関数である。
 この方法なら,2次元配列 Dist の要素数を N×N から K×K に削減できる。ただし,表1に示す表が増えるので,例えばK=5のとき,配列及び表が占めるメモリ使用量を削減できるのはN≧gの場合となる。ここで,表1に示す表は,1駅について配列 Dist の要素5個分のメモリを使用するものとする。

設問

本文中及び図2中の に入れる正しい答えを,解答群の中から選べ。
a,b に関する解答群
  • 33
  • 34
  • 35
  • 999
c,d に関する解答群
  • O(N)
  • O(NlogN)
  • O(N2)
  • O(N3)
e に関する解答群
  • 1, to ≦ From, 1
  • 1, to ≦ From + 1, 1
  • From, To ≦ N − 1, 1
  • From + 1, To ≦ N, 1
f に関する解答群
  • (KL[i]=KL[j])and(KH[i]=KH[j])
  • (KL[i] ≠KL[j])or(KH[i] ≠KH[j])
  • Sec[i]=Sec[j]
  • Sec[i] ≠Sec[j]
g に関する解答群
  • 6
  • 8
  • 9
  • 14

解答選択欄

  • a:
  • b:
  • c:
  • d:
  • e:
  • f:
  • g:

解答

  • a=
  • b=
  • c=
  • d=
  • e=
  • f=
  • g=

解説

この設問の解説はまだありません。
【24年秋期 午後問題】
 問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 問13
© 2010-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop