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

正解

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

正答率 79.2%（625人中 495人が正解）

問題の解説

分割統治法は、大きな問題を同じ形の小さな問題に分け、それぞれを解いて結果を統合し、元の問題の答えを得る設計手法である。クイックソートやマージソートが代表例で、小さな問題どうしが独立しているので、並列処理にも向く。

選択肢ごとの解説

• ア粗い解から出発して逐次改良し、精度を上げていくのは、反復改良（逐次近似）の考え方であり、問題を分割する分割統治法ではない。
• イ全ての組合せを調べつつ、無駄な部分を除いて調べる数を減らすのは、分枝限定法（枝刈り）の考え方である。
• ウ正しい。問題を小さく分け、独立に解いた結果を統合して元の問題を解決するのが、分割統治法である。
• エ各時点で最良に見える選択を繰り返して全体の解を得るのは、貪欲法（グリーディ法）の説明である。