応用情報技術者試験 応用情報技術者試験 令和3年度春期 午前 問7: アルゴリズム設計としての分割統治法に関する記述として，適切なものはどれか。

問題本文

アルゴリズム設計としての分割統治法に関する記述として，適切なものはどれか。

選択肢

• ア.与えられた問題を直接解くことが難しいときに，幾つかに分割した一部分に注目し，とりあえず粗い解を出し，それを逐次改良して精度の良い解を得る方法である。
• イ.起こり得る全てのデータを組み合わせ，それぞれの解を調べることによって，データの組合せのうち無駄なものを除き，実際に調べる組合せ数を減らす方法である。
• ウ.全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。
• エ.まずは問題全体のことは考えずに，問題をある尺度に沿って分解し，各時点で最良の解を選択し，これを繰り返すことによって，全体の最適解を得る方法である。

正解

ウ. 全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。

解説

分割統治法（divide and conquer）は、解きにくい大きな問題をいくつかの小さな部分問題に分割し、各部分問題を（多くは再帰的に）独立に解いてから、それらの結果を統合して元の問題の解を得る設計手法である。クイックソートやマージソートが代表例で、この「分割→個別に処理→統合」という流れを述べたウが正しい。

選択肢ごとの解説

• ア.粗い解を出して逐次改良し精度を上げる手法（反復改良・近似解法の系統）の説明であり、分割統治法ではないため誤り。
• イ.全組合せのうち無駄なものを枝刈りして探索数を減らす手法（分枝限定法など）の説明であり、分割統治法ではないため誤り。
• ウ.全体を小さな問題に分割し、各々を独立に処理した結果をつなぎ合わせて元の問題を解くという、分割統治法そのものの説明であり正しい。
• エ.各時点で最良に見える選択を繰り返して全体最適を狙う手法（貪欲法）の説明であり、分割統治法ではないため誤り。