私たちの日常生活には、さまざまな問題がつきものです。 同様に、プログラミングの分野にも多くの問題があります。
アルゴリズムとプログラミングに関連する特定の問題を解決する方法はたくさんあります。 ブルート フォースと動的計画法はどちらも、問題を解決して解決策を見つけるための一種の手法です。
主要な取り組み
- ブルート フォース アルゴリズムは可能な限りすべての解を徹底的に検索しますが、動的計画法は問題をより小さな重複する部分問題に分割し、解を再利用できるように格納します。
- 動的計画法は、ブルート フォース アプローチと比較して、効率が向上し、計算の複雑さが軽減されます。
- ブルートフォース法は実装が簡単ですが、動的計画法では、最適な部分構造と重複する部分問題を特定するために、問題をより深く理解する必要があります。
力ずく対動的計画法
ブルート フォースとダイナミック プログラミングの違いは効率です。どちらの手法にも効率があります。ブルート フォース方式では、指定されたデータ セットを何度も反復するため効率は悪くなりますが、ダイナミック プログラミング方式では、データ セットを 1 回だけ反復するため効率は高くなります。ただし、どちらの方法も状況によって有用です。
ブルート フォース アプローチは、満足のいく解決策が見つかるまで、特定の問題に関連するすべての可能な解決策を見つけます。 ソリューションが存在する場合、これは常に最も簡単な方法であり、ソリューションを実装して保証します。
ブルート フォース テクニックのこの性質により、その動作が遅くなります。 ブルート フォース アプローチは、解決策を得るための最も簡単なアプローチです。
動的計画法は、より少ない時間と労力で問題を解決するための最適化されたバージョンです。 再帰では、同じ入力セットを何度も解き続けるのに対し、動的計画法では、与えられた問題の未解決のケースのみを解決するため、再帰の最適化です。
比較表
比較のパラメータ | 強引な | 動的計画法 |
---|---|---|
方法論 | 与えられた問題に対して考えられるすべての解決策を見つけます。 | 最適解を XNUMX つだけ見つけます。 |
時間の複雑さ | O(mn)、ここで、m は検出される文字の数、n は入力のサイズです。 | O(n)、ここで n は一意のサブ問題の数です |
例 | 選択ソート | フロイド・ウォーシェル |
反復 | 繰り返し回数が多い | 繰り返し回数が少ない |
効率化 | 効率が悪い | もっと効率的 |
ブルートフォースとは?
コンピュータサイエンスの分野では、ブルートフォースは解決策を見つけるための一般的な手法です。ブルートフォース法は、与えられた問題に対する解決策を保証しますが、実行に時間がかかり、非効率的です。
すべてのケースを体系的に列挙し、条件を満たしているかどうかを確認することから始めます。
配列の要素をソートする例を挙げると、力ずくのアプローチによって、目的の解が得られるまで配列を何度もトラバースします。 これは時間の無駄につながります。
これが時間がかかると言われる理由です。
ブルート フォース手法は、データ セットが限られている場合に使用されます。これは、膨大な量のデータに対して多くの計算を何度も適用すると、多くの複雑さが生じるためです。 適切な解決策がわからない新しい問題が発生するたびに、ブルート フォース手法がベースライン手法として使用されます。
実世界の問題を解決するためのブルート フォースの主な欠点は、チェックするケースの数が増えることです。 たとえば、ある数値の約数を見つけたい場合、その約数が 16 だとすると、力ずくで 10^15 回の計算を実行して解を見つけます。
動的計画法とは
動的計画法は、数学およびコンピューター サイエンスの問題を解決するために最適化された方法です。 1950年代にリチャード・ベルマンによって開発されました。
現在、その最適化能力により、さまざまな分野で応用されています。
複雑な問題を再帰的に単純なサブ問題に分割することで解決します。 次に、各副問題が再帰的に解決されます。
要点は、サブケース「a」が複雑な問題で 4 回発生する場合、動的計画法では 4 回だけ解決するのに対し、再帰では XNUMX 回解決するということです。
これが動的計画法が好まれる理由です。 数学の場合、動的計画法とは、決定を部分問題に分解することによって単純化することを指します。
コンピューター サイエンスの場合、動的計画法を適用する際に XNUMX つの重要な用語があります。XNUMX つ目は最適部分構造、もう XNUMX つは重複部分問題です。
最適な部分構造とは、すべての部分問題の最適化された解を組み合わせることによって、最適化問題の解が得られることを意味します。 サブ問題の重複は、サブ問題のスペースが小さくなければならないことを意味します。
また、すべてのコインには両面があるため、短所もあります。 ご存知のように、サブ問題を解決しながら中間結果を保存するため、大量のメモリが使用されます。
ブルートフォースと動的プログラミングの主な違い
- ブルート フォース アプローチは、データ セットを何度も反復処理することで問題を解決します。 一方、動的計画法は XNUMX 回だけ反復し、最適なソリューションを提供します。
- Brute Force によって提供されるソリューションは、すべての可能なソリューションを提供するため、最適であるとは限りません。 一方、動的計画法によって提供されるソリューションは常に最適です。
- ブルート フォース法は、一度にすべてのデータ セットを考慮することによって解決しますが、動的計画法は、与えられた問題をいくつかの部分問題に分割することによって問題を解決します。
- ブルート フォース アプローチでは、最適な部分構造と重複部分問題の概念は使用されません。 動的計画法では、これらの概念が使用されます。
- 力ずくの方法は、最適でも効率的でもありません。 同じ計算を数回解くのに対し、Dynamin プログラミングは XNUMX つの計算を XNUMX 回だけ解き、メモ化を使用するため、最適かつ効率的です。