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

正解 ウ

分割統治法は、問題を小さな問題に分けて独立に解き、その結果を組み合わせて元の問題を解く方法です。

分割統治法は、大きな問題を同じ形の小さな部分問題に分割します。部分問題を独立に解き、その解を統合して全体の解を得ます。部分問題が十分小さくなるまで、分割は再帰的に繰り返します。代表例はマージソートとクイックソートです。決め手は「小さな問題に分割」「独立に処理」「結果をつなぎ合わせて」という言葉です。

ア：粗い解を出して逐次改良する方法は、近似解を段階的に改善する反復改良の考え方です。部分問題を解いて統合する分割統治法とは異なります。

イ：分枝限定法は、組合せを列挙しながら見込みのない組合せを除いて、調べる数を減らす方法です。

エ：貪欲法は、各時点で最良に見える選択を繰り返して解を構成する方法です。全体の最適解が得られるとは限りません。

出典：令和3年度 春期 応用情報技術者試験 問7