令和3年度春期 ネットワークスペシャリスト 午前Ⅰ 問3

判断に使う前提の出所を確かめる

アルゴリズムの設計を考える際は、与えられた条件と自分が補った前提を区別して整理しましょう。知っている例をそのまま当てはめず、今回の条件の下で考えているかを確かめることが、検討の土台になります。

この問題で問われていること

今回意識したいのは、判断の根拠に使う前提が明示されているかという点です。見慣れた用語から追加の条件を想像していないかを振り返り、条件が書かれていない部分は、決めつけずに考えてみましょう。

視点

前提には、与えられた条件と、経験や知識から自分で補った条件があります。検討の際は、この二つを混同していないかを確認し、判断に持ち込んだ前提の出所を意識しましょう。

確認ポイント

• 判断に使っている前提は、与えられた条件に含まれていますか。
• 知っている例の条件を、今回も成り立つと決めつけていませんか。
• 自分で補った条件を、明示された条件と区別できていますか。

正解

ウ

解説

正解はウです。分割統治法は、問題全体を小さな問題に分割し、それぞれを解いた結果を組み合わせて元の問題を解決する方法です。分割という語だけでなく、その後の処理と結果の組合せまで確認します。

理由

ウは、全体を小さな問題に分割すること、それぞれを独立に処理すること、その結果をつなぎ合わせて元の問題を解決することを述べています。この一連の流れが分割統治法の特徴に一致します。

比較

アの中心は粗い解の逐次改良、イの中心は無駄なデータの組合せを除いて探索対象を減らすことです。エの各時点で最良の選択を繰り返す考え方は貪欲法に対応します。ただし、貪欲法で全体の最適解を得られるかどうかは、問題の性質によります。

選択肢ア

これは不正解だよ。「粗い解を出し、それを逐次改良する」という部分は、解を段階的に改善する考え方を示しています。分割統治法の要点は、小さな問題をそれぞれ解き、その結果を組み合わせて元の問題を解くことです。

選択肢イ

これは不正解だよ。この記述の中心は、データの組合せを調べ、無駄な候補を除くことで探索する組合せ数を減らすことです。分割統治法は、小さな問題ごとの処理結果を組み合わせて全体の解を求めるため、候補の削減を述べたこの説明とは異なります。

選択肢ウ（正解）

これは正解だよ。全体を小さな問題に分割し、それぞれを独立に処理してから結果をつなぎ合わせるという記述は、分割統治法の基本的な流れを表しています。例えばマージソートでは、配列を分割して各部分を整列し、それらを併合して全体を整列します。

選択肢エ

これは不正解だよ。「各時点で最良の解を選択し、これを繰り返す」という部分は、貪欲法の考え方を示しています。分割統治法は、分割した問題の処理結果を組み合わせて全体を解く方法です。また、各時点の最良の選択が全体の最適解につながるとは限りません。

学習のポイント

分割統治法の「分割・個別の処理・結果の組合せ」という流れを、逐次改良や貪欲法と区別して理解しましょう。