最もよく使用される 5 つのアルゴリズムは何ですか?

一般的に使用されるアルゴリズムは次のとおりです: 1. 分割統治法、2. 貪欲アルゴリズム、特定の最適解問題に対するよりシンプルで高速な設計技術、3. 動的プログラミング アルゴリズム、4. バックトラッキング法、一種の最適化検索メソッド; 5. 分岐限定メソッド。

#最も一般的に使用される 5 つのアルゴリズムは、分割統治法、貪欲アルゴリズム、動的計画法アルゴリズム、バックトラッキング法、分岐限定法です。

アルゴリズムとは何ですか?

アルゴリズムとは、問題解決ソリューションの正確かつ完全な記述を指します。問題を解決するための一連の明確な指示です。アルゴリズムは、解決のための戦略的メカニズムを記述する体系的な方法を表します。問題。

アルゴリズムは特定の問題を解決するために使用される一連のステップであると理解できます;アルゴリズムには次の 3 つの重要な特性が必要です:

1. 有限性。有限数のステップを実行した後、アルゴリズムは終了する必要があります。

2. 正確さ。アルゴリズムの各ステップは正確に定義する必要があります。

3. 実現可能性。特定のアルゴリズムは、特定の問題を特定の時間内に解決できなければなりません。

最も一般的に使用される 5 つのアルゴリズム

分割統治法

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

分割統治法で解ける問題は、一般に次のような特徴を持っています:

1) 問題の規模をある程度まで小さくすると、問題は容易に解けるようになります。範囲;

2). この問題は、いくつかの小さな同一の問題に分解できます。つまり、問題には最適な下部構造特性があります;

3). 部分問題の解決策は、以下を使用して分解されます。この問題は、「この問題の解決策」に組み合わせることができます;

4)、この問題によって分解された各サブ問題は互いに独立しています。つまり、サブ問題間に共通のサブサブ問題はありません。 -問題。

貪欲アルゴリズム

貪欲アルゴリズムは、特定の最適解問題に対する、よりシンプルかつ高速な設計テクノロジです。

グリーディメソッドの設計アルゴリズムは、段階的に進めていくのが特徴で、起こり得る全体的な状況を考慮せず、現状や最適化策に基づいて最適な選択を行うことが多いです。最適解は、すべての可能性を網羅するために多くの時間を費やす必要があります。トップダウンの反復手法を使用して、貪欲な選択を連続的に行います。貪欲な選択が行われるたびに、目的の問題はより小さなサブセットに単純化されます。問題、各ステップでの貪欲な選択を通じて、問題の最適解を得ることができます。各ステップで局所的な最適解が得られることは保証されていますが、結果として得られる全体的な解が必ずしも最適であるとは限らないため、貪欲なアルゴリズムはバックトレースしません。

動的プログラミング アルゴリズム

動的プログラミングは、重複する部分問題を含む最適化問題を解決するために数学とコンピューター サイエンスで使用される手法です。基本的な考え方は、元の問題を同様の部分問題に分解し、問題を解決する過程で、部分問題の解決を通じて元の問題の解決策が得られるというものです。動的プログラミングの考え方は多くのアルゴリズムの基礎であり、コンピューターサイエンスとエンジニアリングの分野で広く使用されています。

動的プログラミング手法は、通常、最適化問題を解決するために使用されます。このタイプの問題には、多くの実行可能な解が存在します。各解には値があります。最適な値を持つ解を見つけることは、問題の最適解と呼ばれます。代わりに、最適解のうち、すべてが最適値に達する解が複数存在する可能性があります。

動的プログラミング アルゴリズムを設計する手順:

1)、最適解の構造的特徴を特徴付ける

2)、最適解の値を再帰的に定義します

3)、通常はボトムアップ法を使用して最適解の値を計算します

4)、計算された情報を使用して最適解を構築します

動的プログラミングと除算分割統治法 元の問題の解法と同様に、部分問題の解を組み合わせて元の問題の解を求める方法です。 and-conquer 法はそれぞれ独立して存在しますが、部分問題が重複する場合には動的計画法が適用されます。

バックトラッキング法

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

基本的な考え方は、問題に対するすべての解を含む解空間ツリーにおいて、深さ優先探索戦略に従って、解空間ツリーがルート ノードから開始して深く探索されるということです。ノードを探索するときは、まずノードに問題の解決策が含まれているかどうかを判断する必要があります。含まれている場合は、このノードから探索を続けます。ノードに問題の解決策が含まれていない場合は、そのノードにレイヤーごとに進みます。祖先、ノードのバックトラッキング。

分岐限定法

分岐限定法は非常に広く使用されているアルゴリズムであり、このアルゴリズムの使用法は非常に巧みであり、さまざまな種類の問題解決策が実現されています。異なる方法は同じではありません。

分枝限定法の基本的な考え方は、制約付きの最適化問題に対するすべての実行可能な解 (限られた数) の空間を検索することです。アルゴリズムが具体的に実行されると、実現可能な解空間全体が、より小さなサブセット (ブランチと呼ばれます) に連続的に分割され、各サブセット内の解の値の下限または上限 (区切りと呼ばれます) が計算されます。各分岐の後、制限が既知の実現可能な解の値を超えるサブセットにはそれ以上の分岐は行われません。このようにして、解の多くのサブセット (つまり、検索ツリー上の多くのノード) を無視することができ、検索範囲を絞り込むことができます。範囲。このプロセスは、値がサブセットの境界を超えない実現可能な解が見つかるまで続きます。したがって、このアルゴリズムは一般に最適解を得ることができます。

以上が最もよく使用される 5 つのアルゴリズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。