応用情報技術者 2021年 春期 午前2 問07
問題文
アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。
選択肢
ア：与えられた問題を直接解くことが難しいときに、幾つかに分割した一部分に注目し、とりあえず粗い解を出し、それを逐次改良して精度の良い解を得る方法である。
イ：起こり得る全てのデータを組み合わせ、それぞれの解を調べることによって、データの組合せのうち無駄なものを除き、実際に調べる組合せ数を減らす方法である。
ウ：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。（正解）
エ：まずは問題全体のことは考えずに、問題をある尺度に沿って分解し、各時点で最良の解を選択し、これを繰り返すことによって、全体の最適解を得る方法である。
アルゴリズム設計としての分割統治法に関する問題【午前2 解説】
要点まとめ
- 結論：分割統治法は問題を小さな独立部分に分割し、それぞれを解いて結果を統合する手法です。
- 根拠：大きな問題を扱いやすい小問題に分け、再帰的に解決することで効率的なアルゴリズム設計が可能です。
- 差がつくポイント：分割統治法は「分割→解決→統合」の3段階を踏むことが特徴で、逐次改良や全探索とは異なります。
正解の理由
選択肢ウは「全体を幾つかの小さな問題に分割し、それぞれ独立に処理し結果をつなぎ合わせる」とあり、分割統治法の本質を正確に表現しています。
この方法は、例えばマージソートやクイックソートなどの代表的なアルゴリズムで用いられ、問題を分割し部分問題を解決してから統合することで効率的に解を得ます。
この方法は、例えばマージソートやクイックソートなどの代表的なアルゴリズムで用いられ、問題を分割し部分問題を解決してから統合することで効率的に解を得ます。
よくある誤解
分割統治法は「粗い解を逐次改良する方法」や「全探索の無駄を省く方法」と混同されやすいですが、これらは異なるアルゴリズム設計手法です。
解法ステップ
- 問題を複数の小さな独立した部分問題に分割する。
- 各部分問題を再帰的に解決する。
- 部分問題の解を統合して元の問題の解を得る。
選択肢別の誤答解説
- ア：粗い解を逐次改良する方法は「局所探索法」や「ヒューリスティック」に近く、分割統治法とは異なります。
- イ：全ての組み合わせを調べて無駄を省く方法は「枝刈り」や「バックトラック法」に該当し、分割統治法の説明ではありません。
- ウ：正解。問題を分割し独立に解決、結果を統合する分割統治法の特徴を正しく述べています。
- エ：各時点で最良の解を選ぶ方法は「貪欲法」であり、分割統治法とは異なる戦略です。
補足コラム
分割統治法は多くの効率的なアルゴリズムの基礎です。例えば、マージソートは配列を半分に分割し、それぞれをソートしてからマージすることでの計算量を実現します。分割統治法は問題の構造を理解し、再帰的に解決する力が求められます。
FAQ
Q: 分割統治法と動的計画法の違いは何ですか？
A: 分割統治法は独立した部分問題に分割し解決しますが、動的計画法は重複する部分問題をメモ化して効率化します。
A: 分割統治法は独立した部分問題に分割し解決しますが、動的計画法は重複する部分問題をメモ化して効率化します。
Q: 分割統治法はどんな問題に向いていますか？
A: 問題を独立した小問題に分割でき、結果を統合可能な問題に適しています。例としてソートや探索問題があります。
A: 問題を独立した小問題に分割でき、結果を統合可能な問題に適しています。例としてソートや探索問題があります。
関連キーワード: 分割統治法、アルゴリズム設計、マージソート、クイックソート、貪欲法、動的計画法
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！