令和3年度 春期 応用情報技術者試験 午前 問7
テクノロジ／アルゴリズムアルゴリズム設計としての分割統治法に関する記述として，適切なものはどれか。
出典：令和3年度 春期 応用情報技術者試験 午前 問7
- ア与えられた問題を直接解くことが難しいときに，幾つかに分割した一部分に注目し，とりあえず粗い解を出し，それを逐次改良して精度の良い解を得る方法である。
- イ起こり得る全てのデータを組み合わせ，それぞれの解を調べることによって，データの組合せのうち無駄なものを除き，実際に調べる組合せ数を減らす方法である。
- ウ全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。
- エまずは問題全体のことは考えずに，問題をある尺度に沿って分解し，各時点で最良の解を選択し，これを繰り返すことによって，全体の最適解を得る方法である。
正解：ウ
解説
分割統治法（divide and conquer）は，問題全体を幾つかの小さな部分問題に分割し，それぞれを独立に解いた結果を統合（つなぎ合わせ）して元の問題の解を得る設計手法です。マージソートやクイックソートが代表例です。
選択肢ごとの解説
- ア誤り。粗い解を出して逐次改良していくのは，逐次改良法（反復改善法）などの説明です。
- イ誤り。全ての組合せから無駄なものを除いて調べる数を減らすのは，分枝限定法などの枝刈り手法の説明です。
- ウ正しい。問題を小さな問題に分割し，独立に処理した結果をつなぎ合わせて元の問題を解決するのが分割統治法です。
- エ誤り。各時点で最良の解を選択することを繰り返すのは，貪欲法（グリーディ法）の説明です。