令和3年度 春期 ITストラテジスト試験 システムアーキテクト試験 ネットワークスペシャリスト試験 ITサービスマネージャ試験 情報処理安全確保支援士試験 午前Ⅰ 問題【共通】 問3
アルゴリズム設計としての分割統治法に関する記述として，適切なものはどれか。
解答・解説
正解: ウ. 全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。
分割統治法（Divide and Conquer）は、そのままでは解くことが難しい大きな問題を、独立して解くことができる複数の小さな問題（部分問題）に分割し、それぞれの部分問題を処理した結果をつなぎ合わせて（統合して）、最終的に元の問題の解を得るアルゴリズム設計手法です。
代表的なアルゴリズムとして、マージソートやクイックソートなどがあります。
したがって、この特徴を正しく記述している ウ が正解です。
各選択肢の解説
- ア: 「とりあえず粗い解を出し，それを逐次改良して」とあるため、逐次改良法や近似解法などに関する記述です。
- イ: 「全てのデータを組み合わせ」「無駄なものを除き」とあるため、分枝限定法などの探索アルゴリズムに関する記述です。
- ウ: 正解です。分割統治法に関する記述です。
- エ: 「各時点で最良の解を選択し」とあるため、局所的な最適解を積み重ねていく貪欲法に関する記述です。