令和3年度 春期 応用情報技術者試験 午前 問7

• ア: 粗い解を出して逐次改良する方法
  誤り。これは「逐次改良法（近似法）」であり、分割統治法ではありません。

• イ: 全ての組合せを調べて無駄を省く方法
  誤り。これは「枝刈りを伴う全探索法（バックトラック法や動的計画法）」の説明です。

• ウ: 問題を分割し、それぞれを独立に解く方法
  正しい。分割統治法は、問題を再帰的に小さく分割し、それぞれを独立に処理して最終的に統合する方法です。代表例は「クイックソート」や「マージソート」です。

• エ: 各時点で最良の解を選択する方法
  誤り。これは「貪欲法（グリーディ法）」の説明です。

答え

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