アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。
| ア | 与えられた問題を直接解くことが難しいときに、幾つかに分割した一部分に注目し、とりあえず荒い解を出し、それを逐次改良して精度の良い解を得る方法である。 |
| イ | 起こり得る全てのデータを組み合わせ、それぞれの解を調べることによってデータの組合せのうち無駄なものを除き、実際に調べる組合せ数を減らす方法である。 |
| ウ | 全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。 |
| エ | まず問題は全体のことは考えずに、問題をある尺度に沿って分割し、各時点で最良の解を選択し、これを繰り返すことによって、全体の最適解を得る方法である。 |
答え ウ
【解説】
| ア | 与えられた問題を直接解くことが難しいときに、幾つかに分割した一部分に注目し、とりあえず荒い解を出し、それを逐次改良して精度の良い解を得る方法は、局所探索法です。(×) |
| イ | 起こり得る全てのデータを組み合わせ、それぞれの解を調べることによってデータの組合せのうち無駄なものを除き、実際に調べる組合せ数を減らす方法は、分枝限定法です。(×) |
| ウ | 全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法は、分割統治法です。(〇) |
| エ | まず問題は全体のことは考えずに、問題をある尺度に沿って分割し、各時点で最良の解を選択し、これを繰り返すことによって、全体の最適解を得る方法は、貪欲法(グリーディー算法)です。(×) |
【キーワード】
・分割統治法
- 分割統治法
分割統治法とは、大きな問題を効率的に解く方法で、問題全体を同じ構造の小さな問題に再帰的に分割していって簡単に解けるサイズにした上で解いていきます。
もっと、「分割統治法」について調べてみよう。
戻る
一覧へ
次へ