【基本情報技術者試験平成24年秋期午後】問題と解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成24年秋期基本情報技術者午後問08

問08　　 必須問題

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

　鉄道の路線がある，駅数 N は２以上で，各駅には駅番号（ 1，2，…，N ）が付いている。どの任意の２駅間にも，それらを結ぶ経路が一つ以上存在する。また，隣接する２駅間を直接結ぶ経路は一つだけ存在し，その距離が与えられている。図１に５駅からなる鉄道の路線例を示す。

　　　　　図１　鉄道の路線例 (1)

〔プログラムの説明〕

　副プログラム CalcDist は，駅数 N 及び要素数 N×N の２次元配列 Dist を受け取り，プログラムに示すアルゴリズム（Warshall-Floyd 法）によって，配列 Dist の内容を更新しながら各駅間の最短距離を求めていく。実行が終わると，任意の２駅 i，j 間の最短距離が Dist[i][j] に求められている。どの２駅間についても，その最短距離は 999 より小さいものとする。配列 Dist の添字は１から始まる。

　副プログラム CalcDist に渡す配列 Dist には，次の値を格納する。

　なお，図１の路線情報を格納した配列 Dist の内容を，図２の初期値に示してある。

(1)　２駅 i，j が隣接しているとき，Dist[i][j] 及び Dist[j][i] には，その駅間距離を格納する。例えば，図１の駅①と②は隣接しているので， Dist[1][2] 及び Dist[2][1] には，18を格納する。

(2)　２駅 i，j が隣接していないとき，Dist[i][j] 及び Dist[j][i] には，未確定を表す距離 999 を格納する。例えば，図１の駅①と③は隣接していないので， Dist[1][3] 及び Dist[3][1] には，999 を格納する。

(3)　各駅iについて，Dist[i][1] には０を格納する。

　副プログラム CalcDist 中の Print(N，Dist) は，配列 Dist のその時点の内容を印字する副プログラムである。

〔プログラム〕

　図１の路線情報を配列 Dist に格納して，CalcDist を実行した。配列 Dist の内容の変化を print(N，Dist) で印字した結果は，図２のとおりであった。

　　　　　図２　配列 Dist の内容の変化を印字した結果

　駅数 N に関して，副プログラム CalcDist の計算量のオーダは，またメモリ使用量のオーダはである。そこで，駅数 N が大きい場合に，計算量やメモリ使用量を減らすための方法を考える。

　例えば，配列 Dist の対称性に着目し，プログラム中のの部分を，

とすれば，繰返し処理中の選択処理の実行回数を約半分に減らすことができる。

　次に，少ないメモリ使用量で，任意の２駅 i，j 間の最短距離を求める方法を考える。

　駅を，乗換駅（３方向以上に隣接する駅がある），終端駅（１方向だけに隣接する駅がある），中間駅（２方向だけに隣接する駅がある）の３種類に分ける。乗換駅と終端駅を合わせて基幹駅と呼ぶ。基幹駅の数を K として，駅番号 1 ～ K が基幹駅, 駅番号 K+1 ～ N が中間駅となるように駅番号を定める。ここで，K≧２であるとする。図３の路線例では，駅 ①～③が乗換駅，駅④が終端駅，駅⑤～⑩が中間駅である。

　　　　　図３　鉄道の路線例 (2)　　　　　　　図４　鉄道の路線例 (2) の基幹駅区間名

　各駅間の最短距離は，次の方法で求める。

(1)　中間駅を全て除いて，基幹駅だけからなる路線を考え，二つの基幹駅を結ぶ経路ごとに一意の区間名を付ける。図３の路線例にこの操作を加えたものが図４である。例えば，図３の経路①－⑤－⑥－③は，図４の区間Ｂに対応する。

(2)　要素数 K×K の２次元配列 Dist を用意し，事前に配列 Dist 各基幹駅間の最短距離を求めておく。

(3)　全ての駅について，表１に示す形式の駅情報表を用意する（表１には，図３の駅情報の一部が示してある）。

　中間駅の場合，Sec はその駅が属する区間の区間名，KL，KH はその駅が属する区間の両端の駅番号（ KL ≦ KH とする），ToKL，ToKH はその駅から駅 KL，KH までの距離である。基幹駅の場合，その駅は自分自身の駅を両端とする距離０の区間に属すると考えて，表１の例のように中間駅と同様の情報を用意する。

　これらの情報は，駅番号を添字として参照する。例えば，駅番号 5 の ToKL の値は ToKL[5] として参照する。

　　　　　表１　駅情報表の形式

(4)　２駅 i，j 間の最短距離を求める。一般に，両駅が属する区間が異なる場合，駅 i から駅 j へ行く経路は，

　　　　（駅 i ）→（駅 i が属する区間のいずれか一端の基幹駅）
　　　　　→（駅 j が属する区間のいずれか一端の基幹駅）→（駅 j ）

となる，したがって，次の式で求める４通りの値 D1，D2，D3，D4 のうちの最小値が，２駅 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 へ行く経路がある。これも考慮すると，任意の２駅 i，j 間の最短距離 Res は次の処理で求められる。ここで，関数 min（式₁，式₂，…）は，式₁，式₂，…の値の最小値を返す関数であり，関数 abs(式)は，式の値の絶対値を返す関数である。

　この方法なら，２次元配列 Dist の要素数を N×N から K×K に削減できる。ただし，表１に示す表が増えるので，例えば K＝5 のとき，配列及び表が占めるメモリ使用量を削減できるのは N ≧ の場合となる。ここで，表１に示す表は，１駅について配列 Dist の要素５個分のメモリを使用するものとする。