Python-アルゴリズムクラス

アルゴリズムは明確なステップであり、0個以上の入力を処理することで明確に定義された出力が得られるはずです。これは、アルゴリズムの設計と作成において多くのアプローチにつながります。ほとんどのアルゴリズムは、次のカテゴリに分類できることが確認されています。

欲張りアルゴリズム

欲張りアルゴリズムは、ローカライズされた最適なソリューションを見つけようとします。これにより、最終的にはグローバルに最適化されたソリューションにつながる可能性があります。ただし、一般的に欲張りアルゴリズムは、グローバルに最適化されたソリューションを提供しません。

したがって、欲張りアルゴリズムは、将来のステップにどのように影響するかを考慮せずに、その時点で簡単な解決策を探します。これは、提供された入力の完全な詳細を調べずに人間が問題を解決する方法に似ています。

ほとんどのネットワークアルゴリズムは欲張りアプローチを使用します。ここにそれらのいくつかのリストがあります-

• 巡回セールスマン問題
• プリムの最小スパニングツリーアルゴリズム
• クラスカルの最小スパニングツリーアルゴリズム
• ダイクストラの最小スパニングツリーアルゴリズム

分割統治

このクラスのアルゴリズムでは、特定の問題をより小さなサブ問題に分割し、各サブ問題を個別に解決します。問題をさらに細かく分割できない場合は、各サブ問題の解をマージして、より大きな問題の解に到達します。

分割統治アルゴリズムの重要な例は次のとおりです。

• マージソート
• クイックソート
• クラスカルの最小スパニングツリーアルゴリズム
• 二分探索

動的計画法

動的計画法では、大きな問題を小さな問題に分割しますが、分割統治法とは異なり、各サブ問題を個別に解決する必要はありません。むしろ、より小さなサブ問題の結果が記憶され、類似または重複するサブ問題に使用されます。ほとんどの場合、これらのアルゴリズムは最適化に使用されます。手元のサブ問題を解決する前に、動的アルゴリズムは以前に解決されたサブ問題の結果を調べようとします。

動的アルゴリズムは、局所的な最適化ではなく、問題の全体的な最適化を目的としています。

動的計画法アルゴリズムの重要な例は次のとおりです。

• フィボナッチ数列
• ナップサック問題
• ハノイの塔