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

選択肢

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

正解と解説

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

分割統治法は、問題を同種の小さな部分問題に分割し、それぞれを独立に（多くは再帰的に）解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、高速フーリエ変換などが代表例である。

選択肢ごとの解説

• ア粗い解を反復して精度を上げるのは逐次近似法の考え方。
• イ場合分けで無駄な候補を刈り取って探索量を減らすのは分枝限定法。
• ウ正解。小問題に分けて独立に解き、結果を統合する手法。
• エその時点で最良の選択を繰り返すのは貪欲法。

この問題に出た用語

• 整列アルゴリズムの計算量
• 分割統治法
• 分枝限定法

同じ分野の他の問題

• fact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。2025年度 春期 午前 問7
• 0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに，区間内でf(x)=0であるxの値…2025年度 春期 午前 問2
• 整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか。ここで、整列対象は重複のない1から9の数字がランダ…2024年度 春期 午前 問7
• 正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件…2024年度 春期 午前 問5
• あるデータ列を整列したら状態0から順に状態1、2、・・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。2023年度 秋期 午前 問6