基本情報技術者過去問題 平成29年春期 午後問8 解説

問題文は他のサイトを別ウインドウで開いてご覧ください。

最初にやること

この問題、はじめてアルゴリズム問題にチャレンジする人は、おそらく解き方すらわからないと思います。
しかし、どんな問題であろうともやることは一緒で、まずは引数を用意します。

その引数ですが、どこにも書いてありませんよね。一部はありますが、すべては用意されていません。
実はこの問題では、図1を見ながら自分で作ることを暗に要求されているのです。

さらに本問では変数の種類がかなり多いので、記憶に頼るのではなく、各変数が何を意味しているかを押さえながら、表を作って行きたいと思います。

引数を用意する

引数を図1から作ります。

Distance[ ][ ]は表2に用意されています。これで大丈夫な人はこのままでいいですが、私の表の作り方とは感性がだいぶ違うので、すこし加工したいと思います。

Distance[ ][ ]　：地点間の距離
[0][0] [0][1] [0][2] [0][3] [0][4] [0][5] [0][6]
0 2 8 4 -1 -1 -1
[1][0] [1][1] [1][2] [1][3] [1][4] [1][5] [1][6]
2 0 -1 -1 3 -1 -1
[2][0] [2][1] [2][2] [2][3] [2][4] [2][5] [2][6]
8 -1 0 -1 2 3 -1
[3][0] [3][1] [3][2] [3][3] [3][4] [3][5] [3][6]
4 -1 -1 0 -1 8 -1
[4][0] [4][1] [4][2] [4][3] [4][4] [4][5] [4][6]
-1 3 2 -1 0 -1 9
[5][0] [5][1] [5][2] [5][3] [5][4] [5][5] [5][6]
-1 -1 3 8 -1 0 3
[6][0] [6][1] [6][2] [6][3] [6][4] [6][5] [6][6]
-1 -1 -1 -1 9 3 0

nPointは地点数ですので図1を見て数えます。

nPoint = 7　：地点数

同じく図1から地点番号を設定します。

sp = 0　：出発地点番号
dp = 6　：目的地点番号

初期値を設定する

行番号5～10で初期値を設定します。

sDist = ∞　：最短距離

sRoute[ ]　：最短経路
[0] [1] [2] [3] [4] [5] [6]
-1 -1 -1 -1 -1 -1 -1

pDist[ ]　：出発地からの最短距離
[0] [1] [2] [3] [4] [5] [6]
∞ ∞ ∞ ∞ ∞ ∞ ∞

pFixed[]　：確定状態（フラグ）
[0] [1] [2] [3] [4] [5] [6]
false false false false false false false

プログラム内で宣言している変数

その他にも行番号2～4で宣言している変数があります。

pRoute[ ]　：？？？
[0] [1] [2] [3] [4] [5] [6]
null null null null null null null

sPoint　：？？？
newDist　：？？？

トレース

行番号11から、
出発地から出発地（pDist[0]）までの距離を0に設定します。

pDist[ ]　：出発地からの仮の最短距離
[0] [1] [2] [3] [4] [5] [6]
0 ∞ ∞ ∞ ∞ ∞ ∞

ループ１回目

行番号14～19。
pFixed を検査して、いまだ数値が確定していない地点（値が false の地点）をひとつ選択します。
まだ最初なのですから i は 0 です。

行番号20～22。
すべての地点が確定していたらループを抜けます。
この判定にひっかかるのはループ８回目のときだけです。

行番号23～27。
説明文（5）の２に、「出発地からの最短距離が未確定の地点の中で、出発地からの距離が最も短い地点を探す」とあるので、空欄ａはイとなります。

pDist[ j ] が pDist[ i ] より小さければ i を j で上書きします。
j i pFixed[ j ] pDist[ j ] pDist[ i ]
1 0 false ∞ 0

この処理を j が nPoint より小さい間ループします。
j i pFixed[ j ] pDist[ j ] pDist[ i ]
1 0 false ∞ 0
2 0 false ∞ 0
3 0 false ∞ 0
4 0 false ∞ 0
5 0 false ∞ 0
6 0 false ∞ 0

結局 i は 一度も上書きされず 0 のままでした。

行番号28。
sPoint = 0　：このループ処理で判明した、出発点からいまだ数値が確定していない地点のうち距離が最短の地点

行番号29。
pFixed[0] を　true に書き換えます。
よって空欄ｂはオの sPoint です。

pFixed[ ]　：確定状態（フラグ）
[0] [1] [2] [3] [4] [5] [6]
true false false false false false false

行番号30～39。

31行目の >0 の意味ですが、
Distance[ ][ ] が -1 のときは　sPoint と隣接していない地点を表しています。
Distance[ ][ ] が 0 のときは　sPoint と同じ地点だということを表しています。
よって >0 のときは隣接地点である、となる訳です。

さらに and not(pFixed[j]) なのですから、pFixed[j] が false のとき（未確定のとき）に内側の処理をします。

j Distance
[ 0 ][ j ]		 pFixed
[ j ]		 newDist
0 0 true ×
1 2 false 0+2
2 8 false 0+8
3 4 false 0+4
4 -1 false ×
5 -1 false ×
6 -1 false ×

pDist[ ]　：出発地からの仮の最短距離
[0] [1] [2] [3] [4] [5] [6]
0 2 8 4 ∞ ∞ ∞

pRoute[ ]　：直前の経由地の地点番号
[0] [1] [2] [3] [4] [5] [6]
null 0 0 0 null null null

２回目

行番号14～22。
i は 1 になります。

行番号23～27。
j i pFixed[ j ] pDist[ j ] pDist[ i ]
2 1 false 8 2
3 1 false 4 2
4 1 false ∞ 2
5 1 false ∞ 2
6 1 false ∞ 2

やはり i は 一度も上書きされません。
これは、ようするに以下のことをやっているのです。
出発点から地点1までの距離は2。
（これを i として以下と比べます。）
出発点から地点2までの距離は8。
出発点から地点3までの距離は4。
地点4は隣接していない。
地点5は隣接していない。
地点6は隣接していない。
一番距離が短いのは地点1ですよね。
これをループ処理により導きだしているのです。

行番号28。
sPoint は 1 になります。

行番号29。
pFixed[ ]　：確定状態（フラグ）
[0] [1] [2] [3] [4] [5] [6]
true true false false false false false

行番号30～39。
j Distance
[ 1 ][ j ]		 pFixed
[ j ]		 newDist
0 2 true ×
1 0 true ×
2 -1 false ×
3 -1 false ×
4 3 false 2+3
5 -1 false ×
6 -1 false ×

pDist[ ]　：出発地からの仮の最短距離
[0] [1] [2] [3] [4] [5] [6]
0 2 8 4 5 ∞ ∞

pRoute[ ]　：直前の経由地の地点番号
[0] [1] [2] [3] [4] [5] [6]
null 0 0 0 1 null null

３回目

行番号14～22。
i は 2 になります。

行番号23～27。
j i pFixed[ j ] pDist[ j ] pDist[ i ]
3 2 false 4 8
4 3 false 5 4
5 3 false ∞ 4
6 3 false ∞ 4

出発点から地点2までの距離は8。
（これを i として以下と比べます。）
出発点から地点3までの距離は4。
地点4は隣接していない。
地点5は隣接していない。
地点6は隣接していない。
一番近い地点は3ですのでループの途中で i が 3 に変化しています。

行番号28。
sPoint は 3 になります。

行番号29。
pFixed[ ]　：確定状態（フラグ）
[0] [1] [2] [3] [4] [5] [6]
true true false true false false false

行番号30～39。
j Distance
[ 3 ][ j ]		 pFixed
[ j ]		 newDist
0 4 true ×
1 -1 true ×
2 -1 false ×
3 0 true ×
4 -1 false ×
5 8 false 4+8
6 -1 false ×

pDist[ ]　：出発地からの仮の最短距離
[0] [1] [2] [3] [4] [5] [6]
0 2 8 4 5 12 ∞

pRoute[ ]　：直前の経由地の地点番号
[0] [1] [2] [3] [4] [5] [6]
null 0 0 0 1 3 null

よって空欄ｆはカ、空欄ｇはアとなるのですが、、、

空欄ｇの選択肢には若干の戸惑いがあります。
pRoute[] の null値を 0 で初期化する命令文がどこかにあったでしょうか？
ちょっと私にはよくわかりません。

４回目以降

割愛させていただきます。本試でもトレースする時間はないはずです。
ただし、トレースしなくとも結果的に値がどうなるかがわからないと、残りの設問には感覚で回答することになります。
それが出題者の意図するところなので、仕方がないです。

後処理

行番号40。
判明した最短距離を sDist にいれます。
sDist = 13

行番号41。
j = 0

行番号42。
i = 6

行番号43。
i（目的地点） が sp（出発地点） になるまでループします。

なお、 pRoute は最終的に以下の値になっています。

pRoute[ ]
[0] [1] [2] [3] [4] [5] [6]
null 0 4 0 1 2 5

行番号44。
このループで sRoute[ ] を作成するのですが、 sRoute[ ] は「目的地点から出発地点の順に設定する」と引数の仕様に書いてありますので、まずは sRoute[0] に 目的地点を意味する i をいれます。

sRoute[ ]　：最短経路
[0] [1] [2] [3] [4] [5] [6]
6 -1 -1 -1 -1 -1 -1

よって空欄ｃはキになります。

行番号45。
次の地点に移動するため i を pRoute[ i ] に変更します。

j pRoute[ i ] i
0 5 6 5

よって空欄ｄはイになります。

行番号46。
j はループ処理するための軸に使っている意味のない変数です。
プラス1します。

j pRoute[ i ] i
0 5 6 5
1

以上の処理を出発地点まで繰り返すと以下のようになります。

sRoute[ ]　：最短経路
[0] [1] [2] [3] [4] [5] [6]
6 5 2 4 1 -1 -1

j pRoute[ i ] i
0 5 6 5
1 2 5 2
2 4 2 4
3 1 4 1
4 0 1 0
5

行番号48。
最後です。
sRoute[ j ] に sp をいれます。

sRoute[ ]　：最短経路
[0] [1] [2] [3] [4] [5] [6]
6 5 2 4 1 0 -1

感想

さてこの問題、３５分で解くことができるでしょうか？
私はこの原稿を作るのに１２時間以上かかりました。
問題に関係ないところまで完全トレースを試みましたが、申し訳ありませんが途中で断念いたしました。

断言できますが、この問題は絶対に時間内に解くことはできません。
完答できるのは、同種のアルゴリズムを以前に見聞きしたことがある人だけだと思います。

通常の問題でしたら、66％正解を目指したいところですが、この問題は半分答えられれば御の字といったところでしょう。
全部できなくても全く気にする必要はありません。
あなたができない問題は、周りの人たちもみんなできていないのです。

ホームに戻るボタン↓