アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。

選択肢

• ア与えられた問題を直接解くことが難しいときに、幾つかに分割した一部分に注目し、とりあえず粗い解を出し、それを逐次改良して精度の良い解を得る方法である。
• イ起こり得る全てのデータを組み合わせ、それぞれの解を調べることによって、データの組合せのうち無駄なものを除き、実際に調べる組合せ数を減らす方法である。
• ウ全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。
• エまずは問題全体のことは考えずに、問題をある尺度に沿って分解し、各時点で最良の解を選択し、これを繰り返すことによって、全体の最適解を得る方法である。

正解と解説

正解：ウ 全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。

分割統治法は、解きにくい大きな問題を同じ構造の小さな部分問題に分割し、それぞれを独立に解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、二分探索などが代表例で、再帰的に分割していく点が特徴である。

選択肢ごとの解説

• ア粗い解を反復的に改良していくのは逐次近似法の考え方で、分割統治法の説明ではない。
• イ無駄な組合せを枝刈りして探索数を減らすのは分枝限定法などの探索手法の説明である。
• ウ正解。小問題へ分割し独立に解いて統合するという分割統治法の定義そのものである。
• エ各時点で最良に見えるものを選び続けるのは貪欲法（欲張り法）の説明である。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
• 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3