一般的に使用されるアルゴリズム設計戦略は何ですか?

一般的なアルゴリズム設計戦略:

1. 分割統治

分割統治の設計思想直接解決するのが難しい大きな問題をk個の小さなサブ問題に分割し、それらのサブ問題は互いに独立しており、元の問題と同じであり、それぞれを分解して分割克服する方法です。 。

分割統治法は、再帰と組み合わせてよく使用されます。分割統治法を繰り返し適用することで、部分問題を元の問題タイプと一致させ、規模を継続的に縮小できます。最後に、部分問題は解決策を見つけやすいところまで縮小され、当然のことながら再帰的アルゴリズムが導き出されます。

2. 動的プログラミング

動的プログラミング手法は、分割統治法に似ており、その基本的な考え方は、元の問題をいくつかの部分問題に分解することです。問題。分割統治法とは異なり、分解された部分問題は互いに独立していないことがよくあります。この場合、分割統治法を使用すると一部の下位問題を複数回解決することになりますが、これは明らかに不必要です。動的計画法では、解決プロセス中に解決されたすべてのサブ問題の答えが保存されるため、サブ問題の繰り返しの解決が回避されます。

動的プログラミングは、最適化問題を解決するためによく使用されます。最適化問題に動的計画法を適用できるかどうかは、その問題に次の 2 つの特性があるかどうかによって決まります。

最適な部分構造のプロパティ:

問題の最適解にその部分問題が含まれる場合。の解法では、問題には最適な下部構造特性があると言われます。

サブ問題の重複する性質:

サブ問題の重複する性質とは、元の問題から分解されたサブ問題が互いに独立しておらず、重複していることを意味します。

3. 貪欲な

問題に最適な部分構造特性がある場合、動的プログラミングによって解決できます。しかし、場合によっては、動的プログラミングよりも単純で直接的かつ効率的なアルゴリズム、つまり貪欲法が存在します。貪欲法は常に現時点での最善の選択を行うため、全体最適の選択は考慮せず、ある意味局所的な最適選択に過ぎません。

4. バックトラッキング

バックトラッキング方法は、問題の解空間ツリーで深さ優先検索を実行することですが、各ノードで DFS を実行する前に、問題の解決策を含めることは可能かどうかを最初に判断する必要があります。明らかに含まれていない場合は、このノードをルートとするサブツリーの検索をスキップし、その祖先ノードをレイヤーごとに遡って調べます。含めることができる場合は、サブツリーに入り、DFS を実行します。

5. ブランチ アンド バウンド

ブランチ アンド バウンド メソッドの検索戦略は、まず現在のノードですべての子ノード (ブランチ) を生成し、制約条件を満たす子ノードごとに関数値 (バウンド) が計算され、制約条件を満たすすべての子ノードが解空間ツリーのライブ ノード優先キューに追加されます。次に、現在のライブ ノードの優先順位キュー (ノードの優先順位は制限関数の値によって決定されます) から最高の優先順位を持つノードを新しい現在のノードとして選択します。このプロセスは、葉ノードに到達するまで繰り返されます。到達したリーフ ノードが最適解です。                                                                                                       

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