平成２９年度春期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問８についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2017h29_1/2017h29h_fe_pm_qs.pdf
問題の概要
問題としては最短経路を求めるアルゴリズムですね。
例えば、図1で地点⓪から地点②への経路を考えると、地点⓪から地点②の経路だと距離８ですが、地点⓪→地点①→地点④→地点②の経路だと距離７なので実はこちらの方が距離が短いのです。
こういった複数ある経路の中から最短経路を見つけ出すアルゴリズム問題になっています。
スポンサーリンク
設問１
設問１はプログラムの穴埋めです。
ただこのプログラム難しいです…。なんでこのプログラムで最短経路が見つかるかや、どういう仕組みのプログラムかの理解はすぐには難しいかもしれません。
ただこの問題を解く上で必要なのは、プログラムの全体像を把握することではなく穴埋め部分を埋めるです。
これは[プログラムの説明]を読めば解くことはできます。プログラムを行ごとに[プログラムの説明]で説明してくれています。
では問題を解いていきましょう。[ a ]と[ b ]に関しては下記の説明から回答が導け出せます。
(5) – ②
行番号23～29
「出発地からの最短距離が未確定の地点の中で、出発地からの距離が最も短い地点を探し、その地点を sPoint とし、その地点の最短距離を確定する。」
(3) – ③よりpDistとは「出発地から各地点までの最短距離を設定する配列」であることがわかります。
プログラム24行目の「pDist[j] > pDist[i]」では地点jと地点iのpDistを比較し、地点jの方が短ければプログラム25行目の「i ← j」が実行されます。つまり、最短距離の地点をiとして仮定しておき、それより距離が短い地点が見つかったらiをその地点番号で更新する。これを最後の地点番号まで繰り返すことで最短距離を探す処理と考えられます。ですので、これは⑸ – ②の「出発地からの距離が最も短い地点を探し」の処理と考えることができそうです。
さらに(5) – ②では「出発地からの最短距離が未確定の地点の中」から上記の「最も短い地点」を探そうとしています。ですので、プログラム25行目は「pDist[j] > pDist[i]」かつ「出発地からの最短距離が未確定な地点jである」の両方の判断がtrueのときのみ実行される必要があります。
(3) – ④より、地点jが出発地からの最短距離が未確定かどうかは「pFixed」に格納されており、地点jが未確定であるとき「pFixed[j]はfalseが格納されている」ので未確定であるときにtrueであるようにするようにするためには「not(pFixed[j])」を条件とする必要があります。したがって[ a ]の答えは「not(pFixed[j])」となります。
最短距離が未確定かつ地点iよりも短い地点が見つかるとその地点番号iをその地点番号で上書きしていっているので、プログラム23行目から27行目が実行されると、「出発地からの最短距離が未確定かつ出発地からの距離が最短の地点」の地点番号がiに格納されることになります。
さらにプログラムの28行目は(5) – ②の「その地点をsPointとし」の処理です。sPointにiが格納されていますので、sPointには「出発地からの最短距離が未確定かつ出発地からの距離が最短の地点の地点番号」が格納されることになります。
次の[ b ]の穴埋めのある29行目は残った「その地点の最短距離を確定する」処理になります。
プログラム23行目から28行目が実行されると出発地から最短距離の地点番号がsPointに格納されているので、この地点の最短距離を確定すればよいため、地点iまでの最短距離確定情報を格納しているpFixed[sPoint]をtrueにしてやればよいです。
ですので[ b ]の答えは「sPoint」となります。
つづいて[ c ]、[ d ]を見ていきましょう。
プログラムの40行目から48行目は[プログラムの説明]の(6)の処理になります。
まず出てくる変数がどういったものか見てみましょう。
表１よりspとdpはそれぞれ出発地と目的地の地点番号と分かります。
pDist[j]は[プログラムの説明]の(5) – ③より「出発地から地点jまでの最短距離」であることが分かります。
またpRoute[j]には「出発地から地点jの最短経路における地点jの直前の地点番号」が格納されていることが分かります。
図に書くとこんな感じですね。これは出発地を⓪とした時の地点②に対する最短経路、そこを通る地点のpRouteはそれぞれ図示したものになります。
では設問を解いていきましょう。ここでおさらいした変数の意味より、プログラムの40行目は[プログラムの説明]の(6)の前半部分の「出発地から目的地までの最短距離を sDistに格納」する処理と考えられます。
ですので、プログラム41行目から48行目は[プログラムの説明]の(6)の後半部分の「出発地から目的地までの最短経路上の地点の地点番号を目的地から出発地までの順に配列 sRoute に設定する」処理と考えられます。
pRoute[j]には「出発地から地点jの最短経路における地点jの直前の地点番号」が格納されています。
ですので「出発地からまでの最短経路上の地点の地点番号」はpRouteに格納されている値を辿っていくことで求めることができます。
目的地dpを2とした時はpRoute[2]には最短経路上の②の１つ前の地点番号である4が格納されています。
さらに、④の１つ前の地点番号は同様にpRoute[4]に格納されています。
同様にpRouteを目的地のspまで辿っていくことで「出発地から目的地までの最短経路上の地点の地点番号を目的地から出発地までの順に」取得可能です。あとはこれをsRouteに格納してやるプログラムを考えれば設問を解くことができます。
目的地から出発地までの順に地点番号をsRouteに格納するので、sRoute[0]にはdpが入ると考えられます。
上記のpRouteの特性より、sRoute[1]にはpRoute[dp]の値を入れれば良さそうです。ここでpRoute[dp]の値をiに一旦格納してやれば、次のsRoute[2]にはpRoute[i]の値が入ると考えられます。pRoute[i]がspになるまで繰り返せば、[プログラムの説明]の(6)の後半部分が実現できます。
この辺りがわかれば問題は解けると思います。
まずsRouteの値を格納されている箇所を探してみましょう。どこにもないのでおそらく穴埋めとなっている[ c ]で値が格納されていそうと予想できます。
選択肢はいくつかありますが、上記の説明でsRouteの添字は0から始まり値を格納するごとに1ずつ増やしていました。ですので、最初が0で、ループの中で1ずつ値が増やされているjがsRouteの添字と考えられます。したがって[ c ]の答えは「sRoute[j]」となります。
[ d ]はプログラム45行目でiに格納される変数になります。iは目的地のdpで初期化されており、プログラム44行目でsRoute[j]に格納される値ですので、最短経路上の地点番号が格納されていると考えられそうです。ですので、プログラム45行目では最短経路上の地点番号を1つ前の地点に更新する処理と考えられます。具体的には「i ← pRoute[i]」ですね。したがって、[ d ]は「pRoute[i」]です。設問２
この設問は実際に処理を実行したときに各変数がどのように変化していくかを答える問題です。ですので、設問１さえ解けていれば実際に頭の中で処理を追っていけば必ず解ける問題だと思います。
具体的にはループ３回目のα時点のsPoint、β時点のpRoute、pDistの値を答える問題です。
しかも１回目と２回目のループでのそれぞれの変数の値は問題に書いてくれています。ですのでループ３回目だけ考えて解くということも可能です。
ですが時間があるのであればループ１回目と２回目も実際に試してみて変数の値を見てみることをオススメします。問題に記載の値と合っていれば今までの考え方が合っていたかどうかが分かりますし、値が違っていれば設問１が間違っている可能性があるので見直しにも使えます。
詳しい説明は省きますが、
sPointは確定していない地点の中から出発地点⓪からの最短距離が入ります。①に関しては２回目のループで確定しているので、３回目のループではsPointは3になります。なので[ e ]の答えは「3」です。
pRouteは３回目のループでsPointである地点③から辿れる地点⑤の最短距離のみが更新されます。さらに地点③を経由したときの地点⑤の最短距離に更新されますので距離は１２となります。ですので、２回目のループ結果からpRoute[5]のみが更新され、そこに12が格納されているものが答えとなります。したがって[ f ]の答えは選択肢 カとなります。
pDistに関してもpRouteと同様の考えで、ループ３回目では地点⑤の情報のみが更新されますのでpDist[5]のみが更新され、そこには１つ前の地点番号である3が格納されているものが答えとなります。したがって[ g ]の答えは選択肢 アとなります。
解いてみた感想
これも難しい問題です。平成３０年度春期の問題も難しかったですが、こちらの方が難易度は上ですね。
最短経路の知識なしにこの問題が解けるのであればアルゴリズム問題はバッチリだと思います。自信を持って試験受けてきてください。
私は設問１を解いていてもプログラムが何をやっているのか正直イメージが湧きませんでした・・・。プログラムの説明が充実していたのでゴリ押しで解きましたが。
イメージ湧きだしたのは設問２で具体的な例でプログラムの動きを追っていた時ですね。やっぱり具体的な例で考えるのは重要だと思います。
もう一つこの問題を解いていて重要だと思ったのは、プログラムが何をやっているのかが分からなくても問題は解けることです。
プログラムの説明が理解できれば穴埋め問題なら解けそうだと思いました。アルゴリズム問題はプログラムの説明が実際のプログラムどこに対応しているかをしっかり理解することと、変数の意味や変化の仕方を理解することさえできれば問題解けると思います。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ
本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成２９年度 春期 基本情報技術者試験（FE）試験区分 午後 問８
アルゴリズム問題の対策（PR）
過去問を解いてみて感触はいかがだったでしょうか？
全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。
なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる！ 基本情報技術者 [午後・アルゴリズム編] です。
オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。
また、「アルゴリズムとは？」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。
アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。
慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" ＆ "実際のアルゴリズム問題に慣れる" のが良いと思います。
私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです（アルゴリズム問題だけでなく、全問題の解説も充実しています）。
