令和3年度春期 応用情報技術者試験 午前 問7
アルゴリズム設計としての分割統治法に関する記述として，適切なものはどれか。
- ア 与えられた問題を直接解くことが難しいときに，幾つかに分割した一部分に注目し，とりあえず粗い解を出し，それを逐次改良して精度の良い解を得る方法である。
- イ 起こり得る全てのデータを組み合わせ，それぞれの解を調べることによって，データの組合せのうち無駄なものを除き，実際に調べる組合せ数を減らす方法である。
- ウ 全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。
- エ まずは問題全体のことは考えずに，問題をある尺度に沿って分解し，各時点で最良の解を選択し，これを繰り返すことによって，全体の最適解を得る方法である。
解答・解説を見る
正解：ウ
AI解説
分割統治法は、与えられた問題全体を独立に解くことができる幾つかの小さな部分問題に分割し、それぞれの部分問題を再帰的に解いた上で、その結果をつなぎ合わせて元の問題全体の解を得るアルゴリズム設計技法である。マージソートやクイックソートが代表例である。 ア: 粗い解を求めてから逐次改良して精度を高める方法は反復改善法(逐次改善法)の説明であり、分割統治法とは異なる。 イ: 起こり得る組合せを全て調べつつ無駄な組合せを除いて調べる数を減らす方法は、分岐限定法などバックトラック系の手法の説明である。 ウ: 正しい。問題を独立に解ける小さな問題に分割し、それぞれの結果をつなぎ合わせて元の問題を解決するのが分割統治法である。 エ: 問題全体を考えずに、ある尺度に沿って各時点で最良の選択を繰り返し全体の最適解を目指す方法は貪欲法(greedy algorithm)の説明である。 💡 「分割して統治する(Divide and Conquer)」という名前どおり、独立に解ける部分問題への分割と結果の統合がセットになっている点が貪欲法や逐次改善法との違いである。
出典：令和3年度 春期 応用情報技術者試験 午前 問7 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。