HOME»応用情報技術者令和3年春期»午前問7
応用情報技術者令和3年春期 午前問7
午前問7
アルゴリズム設計としての分割統治法に関する記述として,適切なものはどれか。
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ウ
解説
分割統治法は、大きな問題を同じ構造をもつ複数の小さな問題に分割し、その小さな問題の解を統合することで最終的に元の大きな問題を解決しようとする考え方です。整列アルゴリズムだとクイックソートやマージソートが分割統治法の考え方に基づくアルゴリズムです。

- 局所探索法の説明です。現在の解と近傍解を比較し、近傍解が良ければ新しい解として入れ替えることを繰り返します。
- 分枝限定法の説明です。全体問題を場合分けによって部分問題にする(分枝操作)と、解く必要のない部分問題を切り捨てる(限定操作)ことによって効率よく解を求める方法です。
- 正しい。分割統治法の説明です。
- 貪欲法(グリーディ法)の説明です。