令和3年度 春期 応用情報技術者試験 午前 問7
アルゴリズム設計としての分割統治法に関する記述として，適切なものはどれか。
解答・解説
正解: ウ. 全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。
分割統治法（Divide and Conquer）は、そのままでは解決が難しい大きな問題を、幾つかの小さな問題に分割し、それぞれの小さな問題を独立して解決（統治）した後、その結果をつなぎ合わせて全体の問題を解決するアルゴリズムの設計手法です。代表的な例として、マージソートやクイックソートなどのソートアルゴリズムで用いられています。
したがって、この考え方を正しく説明しているウが正解となります。
各選択肢の解説
- ア: とりあえず粗い解を出し、それを逐次改良して精度の良い解を得る手法は、ヒューリスティクス（発見的手法）や局所探索法に関する記述です。
- イ: 起こり得る全ての組み合わせを調べつつ、無駄なものを除いて（枝刈りして）実際に調べる数を減らす手法は、分枝限定法に関する記述です。
- ウ: 正解です。分割統治法に関する記述です。
- エ: 全体のことは考えず、各時点で最良の解（局所的な最適解）を選択することを繰り返し、全体の解を得る手法は、貪欲法（グリーディアルゴリズム）に関する記述です。