5 つの古典的なコンピューター アルゴリズムとは何ですか?

5 つの古典的なコンピューター アルゴリズム: 1. 複雑な問題を 2 つ以上の同一または類似のサブ問題に分割する分割統治法、2. 動的プログラミング法、3. 貪欲アルゴリズム、4. バックトラッキング法、最適な検索方法の一種で、目標を達成するための最適な条件に従って前方に検索します; 5. 分岐限定方法。

このチュートリアルの動作環境: Windows 10 システム、Dell G3 コンピューター。

これから履歴書の提出とインターンシップの募集を始めます。まだ何をすればいいのか分からず、とてもパニックです。今日から毎日リートコードを2つ以上磨いていきます面接でのさまざまな質問の知識ポイントを要約し、まとめます。今後頻繁に復習してください。

リートコードをブラッシングしていると、DP について話している人をよく見かけました。その後、DP が何なのか調べるために Baidu にアクセスしたところ、DP が 5 つの古典的なアルゴリズムの 1 つであることに気付きました。今日は、これについてまとめます。 5 つの古典的なアルゴリズム。

5 つの古典的なアルゴリズムは、

1 に分割されます。 分割統治法: 複雑な問題を 2 つ以上の同一または類似の問題に分割します。サブ問題を分割し、さらにそのサブ問題をさらに小さなサブ問題に分割します...最終的にサブ問題が単純かつ直接的に解決できるようになり、元の問題の解決策はサブ問題の解決策を統合することになります。 。

2. 動的プログラミング手法: 各決定は現在の状態に依存し、即座に状態遷移を引き起こします。状態が変化しながら意思決定系列が生成されるため、問題を解決するための多段階の最適化意思決定プロセスを動的計画法と呼びます。

3. 貪欲なアルゴリズム: 問題を解決するときは、常に現時点で最善の選択をします。つまり、彼が作ったのは全体最適解を考慮せず、ある意味局所最適解に過ぎなかったのである。一般的な貪欲アルゴリズムには、Prim アルゴリズムと Kruskal アルゴリズム (どちらも最小スパニング ツリーを求める) が含まれます。

基本的な考え方: 問題をいくつかの小さな問題に分解し、各部分問題の局所最適解を徐々に取得し、最終的にそれを元の問題の解にマージします。

4. バックトラッキング手法: バックトラッキング アルゴリズムは、実際には列挙と同様の検索試行プロセスであり、主に検索試行中に問題の解決策を探索します。 、「バックトラック」して戻ります。 、別のパスを試してください。深さ優先;

バックトラッキング法は、最適化条件に従って目標を達成するために前方に探索する最適化探索法です。しかし、探求が一定の段階に達し、最初の選択が最適ではない、または目標を達成できないことがわかった場合、一歩下がって別の選択をすることになります。うまくいかなかったときに戻ってやり直してみるこのテクニックは、バックトラック方法と、バックトラック条件を満たすある状態の点を「バックトラックポイント」と呼びます。

5. 分岐限定法: バックトラッキング法と同様に、問題の解空間木 T 上で問題の解を探索するアルゴリズムです。ただし、一般に、分岐限定法とバックトラッキング法では、解決の目標が異なります。バックトラッキング法の解の目標は、制約条件を満たす T 内のすべての解を見つけることですが、分岐限定法の解の目標は、制約条件を満たす解を見つけること、または制約を満たす解を見つけることです。ある目的に対して関数の値が最大値または最小値に達するような条件を設定することで、ある意味最適解となります。

1. 分割統治法

分割統治法で解決できる問題には、一般に次のような特徴があります:

1) 問題の規模をある程度小さくすると、問題は簡単に解決できます。
2) 問題は、同じサイズのいくつかの小さな問題に分解できます。つまり、問題は最適化されています。部分構造のプロパティ。
3) この問題によって分解された部分問題の解決策は、この問題の解決策に組み合わせることができます;

4) この問題から分解された部分問題は互いに独立しています、つまり、サブ問題です。質問間に共通のサブサブ問題はありません。

3 番目の特性がない場合は、動的プログラミング (DP) または貪欲な方法の使用を検討できます。

4 番目の特性がない場合は、動的プログラミングの使用を検討できます。

分割統治法の基本ステップ:

ステップ 1 分解: 元の問題を、元の問題と同じ形式を持つ、いくつかの小さな独立したサブ問題に分解します。
ステップ 2 の解決策: サブ問題が小さく、解決が簡単な場合は直接解決します。そうでない場合は、各サブ問題を再帰的に解決します。

ステップ 3 マージ: 各サブ問題の解を結合します。元々の問題の解決策。

#2. 動的プログラミング手法

# 分割統治法の最大の違いは、解決される問題に適していることです。動的計画法によると、分解後に得られるサブ問題は互いに独立していないことがよくあります (つまり、次のサブステージの解決策は、さらなる解決のために前のサブステージの解決策に基づいています)。

適用条件:

動的計画法で解ける問題には、一般に次の 3 つの性質があります:

(1) 最適化原理: 最適な問題の場合 解決策の場合最適解に含まれる部分問題も最適であれば、その問題は最適な部分構造を持っている、つまり最適化原理を満たしていると言われます。
(2) 余効なし: つまり、ある段階の状態が決定されると、この状態での後続の決定は影響を受けません。言い換えれば、特定の状態の後のプロセスは前の状態には影響せず、現在の状態にのみ関連します。

(3) 重複するサブ問題があります。つまり、サブ問題は独立しておらず、サブ問題は意思決定の次の段階で複数回使用される可能性があります。 (この性質は動的計画法を適用するための必須条件ではありませんが、この性質がなければ動的計画法のアルゴリズムは他のアルゴリズムと比べて利点がありません。)

ケース:

n 個あります。ステップ では、人は一度に 1 つまたは 2 つのステップを上っていき、n つのステップを完了する方法は何通りあるかを尋ねます。
分析: 動的プログラミングの実装の鍵は、実際の問題を抽象化するために動的プログラミング テーブルを正確かつ合理的に使用できるかどうかにあります。この問題では、f(n) を n ステップ上に進む方法の数を表します。

次に、n が 1 の場合、f(n) = 1、n が 2 の場合、f(n) = 2、つまりステップが 1 つしかない場合、メソッドの数が決まります。が 1 の場合、ステップが 2 つの場合、メソッドの数は 2 になります。したがって、n 段階上に行きたい場合は、n-1 段階から 1 段階、または n-2 段階から 2 段階進む必要があるため、n 段階に到達する方法の数は、n-1 段階に到達する方法の数を加えたものでなければなりません。 n-2 ステップに到達する方法の数の合計。つまり、f(n) = f(n-1) f(n-2)、動的計画法テーブル dp[i],i>0,i

int fun(int n){  
    if (n==1||n==2)  
        return n;  
    /*判断n-1的状态有没有被计算过*/  
    if (!dp[n-1])  
        dp[n-1] = fun(n-1);  
    if(!dp[n-2])  
        dp[n-2]=fun(n-2);  
    return dp[n-1]+dp[n-2];  
}

3. 貪欲なアルゴリズム

貪欲なアルゴリズムとは、問題を解決する際に、常に現時点で最善の決定を下すことを意味します。 。つまり、全体最適解は考えず、ある意味局所最適解を作るだけです。グリーディ アルゴリズムは、すべての問題に対して全体的な最適解を取得するわけではありません。重要なのは、グリーディ ストラテジーの選択です。選択されたグリーディ ストラテジーには、影響があってはならない、つまり、特定の状態の前のプロセスが次の状態に影響を及ぼさないようにする必要があります。ただし、現在の状態にのみ影響します。
問題を解決するための一般的な手順は次のとおりです:
1. 問題を説明する数学的モデルを確立します;
2. 解決する問題をいくつかのサブ問題に分割します;
3. 各サブ問題を解決します-problem を実行し、サブ問題を取得します。 問題の局所最適解;

4. サブ問題の局所最適解を元の問題の解に結合します。

例: 両替の問題

この問題は私たちの日常生活でより一般的です。それぞれ1元、2元、5元、10元、20元、50元、100元の紙幣c0、c1、c2、c3、c4、c5、c6があるとする。さて、このお金を K 元の支払いに使用するには、少なくとも何枚の紙幣を使用する必要がありますか?貪欲なアルゴリズムの考え方を使用すると、各ステップで可能な限り額面の大きな紙幣のみを使用できることがわかります。私たちは日常生活の中でこれを自然に行っています。プログラム内では値が昇順に並べられています。

public class charge {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
    	int res = charge(84);
    	System.out.println(res);
    }
 
   private static int charge(int money) {
	   int count = 0;
       int value[] = {50,20,10,5,2,1};
       while(money>0){
       	int length = value.length;
       	for(int i=0;i<length;i++){
       		while(money>=value[i]){
       			money=money-value[i];
       			count++;
       			//System.out.println(money);
       		}
       	}
       }
       return count;
	}     
}

4. バックトラッキング法

# バックトラッキング法は、問題の解決策を体系的に探索する方法です。検索プロセスでは、問題の解決策を見つけようとします。見つからない場合は、一歩下がって上に戻ります (枝刈りプロセス)。バックトラッキングは、多くの複雑で大規模な問題に使用できます。
バックトラッキング法の基本的な考え方は、深さ優先探索戦略に従ってルートノードから探索を開始し、特定のノードに到達したときに、そこに問題の解決策が含まれているかどうかを判断する必要があります。存在する場合は、そのノードから検索を続行します。存在しない場合は、親ノードに戻って検索を続行します。問題に対するすべての解決策を見つけるためにバックトラッキング方法が使用される場合、ルートまで遡る必要があり、終了する前にルート ノードのすべての実行可能なサブツリーが検索されている必要があります。また、バックトラッキング手法を使用して解決策を見つける場合は、問題の解決策が見つかったら終了することができます。

バックトラッキング手法で一般的に使用される枝刈り関数: (1) 制約関数: ノードでの制約を満たさないサブツリーを減算します。 （２）境界関数：最適解が得られない部分木を減算する。

一般的な手順:

1. 指定された問題について、問題の解空間を決定します
2. 検索に適した方法を使用して解空間を整理します
3. を使用します。深さ優先検索 解決空間

4. 検索プロセス中にプルーニング機能を使用して、無効な検索を回避します。

5. 分岐限定法

#バックトラッキング法と同様に、問題の解決策を探索するアルゴリズムです。問題の解空間木 T 上で。ただし、一般に、分岐限定法とバックトラッキング法では、解決の目標が異なります。バックトラッキング法の解の目標は、制約条件を満たす T 内のすべての解を見つけることですが、分岐限定法の解の目標は、制約条件を満たす解を見つけること、または制約を満たす解を見つけることです。ある目的に対して関数の値が最大値または最小値に達するような条件を設定することで、ある意味最適解となります。

(1) ブランチ検索アルゴリズム

いわゆる「ブランチ」は、幅優先戦略を使用して、E ノードのすべてのブランチを順番に検索します。つまり、隣接するすべてのブランチを検索します。制約条件のノードと残りのノードがライブノードリストに追加されます。次に、次の E ノードとしてテーブルからノードを選択し、検索を続行します。

次の E ノードを選択する方法に応じて、いくつかの異なる分岐検索方法があります。

1) FIFO 検索

2) LIFO 検索

3) 優先キュー検索

(2) 分岐限定検索アルゴリズム

#分岐結合メソッドの一般的なプロセス

解の目的が異なるため、解空間木 T 上の分岐限定法と後戻り法の探索方法も異なります。バックトラッキング法は深さ優先方式で解空間木 T を探索するのに対し、分枝限定法は幅優先または最小コスト優先方式で解空間木 T を探索します。

分岐結合メソッドの検索戦略は次のとおりです。拡張ノードで、最初にそのすべての子ノード (分岐) を生成し、次に現在のライブ ノード テーブルから次の拡張ペアを選択します。次の拡張ノードを効果的に選択し、検索プロセスを高速化するために、各ライブ ノードで関数値 (境界) が計算され、これらの計算された関数値に基づいて、現在のライブ ノード テーブルから最適な値が選択されます。有利なノードは、解空間ツリー上の最適解を持つ分岐に向かって探索を進めるための拡張ノードとして機能し、できるだけ早く最適解を見つける。

分枝限定法では、多くの場合、幅優先または最小コスト (最大利益) 優先の方法で問題の解空間ツリーが検索されます。問題の解空間ツリーは、問題の解空間を表す順序付きツリーであり、一般的なものには、サブセット ツリーや順列ツリーなどがあります。問題の解空間ツリーを探索する場合、分枝限定法とバックトラッキング法では、現在の展開ノードに対して異なる展開方法が使用されます。分岐限定方式では、各ライブ ノードが拡張ノードになるチャンスは 1 回だけです。ライブ ノードが拡張ノードになると、そのすべての子ノードが一度に生成されます。これらの子ノードのうち、実行不可能な解決策または非最適な解決策につながるものは破棄され、残りの子ノードがライブ ノード リストに追加されます。その後、ライブノードテーブルからノードが取り出され、現在の拡張ノードとなり、上記のノード拡張プロセスが繰り返される。このプロセスは、目的の解決策が見つかるか、ライブノット テーブルが空になるまで続けられます。

バックトラッキング手法と分岐限定手法のいくつかの違い

一部の問題は、バックトラッキング手法または分岐限定手法のどちらでも実際にうまく解決できます。しかし、そうでない人もいます。おそらく、より具体的な分析が必要になるでしょう - 分岐限定をいつ使用するのか、いつバックトラッキングを使用するのか?

バックトラッキング手法と分岐限定手法のいくつかの違い:

この手法が解空間ツリーを検索する方法 ノードを格納するために一般的に使用されるデータ構造 ノード ストレージ機能の一般的に使用されるアプリケーション

バックトラッキング 深さ優先検索方法: 制約を満たすすべてのソリューションを見つけるために、スタックのライブ ノードのすべての実行可能な子ノードがスタックからポップされる前に走査されます。

ブランチアンド-バウンド方式 幅優先または最小消費優先の検索キュー、優先キュー 各ノードは、制約を満たすソリューションまたは特定の意味での最適なソリューションを見つけるためにライブ ノードになる機会が 1 回だけあります。知識がある場合は、

FAQ

列をご覧ください。

以上が5 つの古典的なコンピューター アルゴリズムとは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。