一、アルゴリズムと問題
アルゴリズムは問題を解決するための一連の手順です。
問題を理解し、アルゴリズムを設計する一般的なプロセスは次のとおりです：
問題を解決する際にはまず力まかせ法を考えることができます。力まかせ法は一般的に解決できますが、効率は低いです。力まかせ法で問題を解決した後、他のアルゴリズムの考えを使用して最適化を行うことができます。力まかせ法を使用する際に解決が困難な場合は、問題を再考し、何らかのパターンを見つけることができるかどうかを再度考え、そのパターンを使用して解決します。
力まかせ法は通常、すべての可能性を順番に試す必要があります。また、問題には複数の遍歴戦略が存在することがあります。いくつかの戦略は問題の解を導き出すことができますが、他の戦略は最終的な解を導き出すことができません。したがって、力まかせ法を使用する際には、遍歴戦略の選択が非常に重要です。適切な遍歴戦略は、貪欲法や動的計画法と同様の効果を発揮することさえあります。この意味で、貪欲法、動的計画法、バックトラック、分岐限定も一種の力まかせ法と言えますが、賢明な力まかせ法です。
最適化のアプローチには以下の 3 つの方向があります：
1、力まかせ法→貪欲法、動的計画法→バックトラック、分岐限定
2、分割、減少、変化
3、時空間のトレードオフ
二、力まかせ法
力まかせ法は問題を解決するための直感的で簡単な方法であり、問題の記述と関連する概念に基づいています。力まかせ法は解決できる問題の範囲が最も広いですが、効率は通常低いです。
力まかせ法を使用するアルゴリズムは次のとおりです：
1、バブルソート、選択ソート
2、順序マッチング
3、総当たり法
三、分割法
分割法の設計手順：
1、問題インスタンスをより小さな同じ問題のインスタンスに分割し、できるだけ同じサイズにすることが望ましいです。
2、より小さなインスタンスを解決します。
3、より小さな問題の解を結合します。
分割法のアルゴリズム：
1、マージソート、クイックソート
2、バイナリサーチ
3、二分木のトラバーサル（前順、中順、後順）
4、大きな整数の乗算と行列の乗算の分割
5、最近のペアと凸包の問題の分割
四、減少法
減少法は問題の解と同じ問題のより小さなインスタンスの解の関係を利用する技術です。減少法には次の 3 つの主なタイプがあります：
1、定数の減少：同じサイズの定数を減らすことを繰り返し行います。一般的には 1 または 2 です。例えば、a の n 乗を求めることは f (n)=f (n-1)*a と理解できます。
2、定数倍の減少：各反復で同じ定数倍を減らします。例えば、問題のサイズを元の問題の 1/2 にすることができますが、それでも a の n 乗を求めることができます。ただし、再帰的な式を使用してください。
3、可変サイズの減少：各反復で問題のサイズを可変に減らします。例えば、最大公約数 gcd (m,n) = gcd (n,m mod n) や、クイックソートに基づく k 番目の最大数の検索などがあります。
減少法のアルゴリズム（定数の減少）：
挿入ソート、深さ優先探索、幅優先探索、トポロジカルソート、順列の生成、部分集合の生成
定数倍の減少アルゴリズム：
偽コイン問題、ヨセフス問題
可変サイズの減少：
クイックソートに基づく k 番目の最大数の検索、補間検索、二分探索木の挿入と検索
五、変治法
変治法は主に問題インスタンスの変換に焦点を当てており、次の 3 つの主なタイプがあります：
1、問題の簡略化：同じ問題のより簡単で便利なインスタンスに変換します。
2、表現の変更：同じ問題インスタンスの異なる表現方法
3、問題の変換：別の問題のインスタンスに変換します。
問題の簡略化：事前ソート、ガウスの消去法
表現の変更：探索木、ヒープソート
問題の変換：最小公倍数を求める問題を最大公約数を求める問題に変換する
lcm(m,n) = m*n/gcd(m,n)
六、時空間のトレードオフ
空間を時間に変換する、動的計画法やハッシュも空間を時間に変換する一種の方法です。
1、カウントソート
2、文字列マッチング（Horspool、Boyer-Moore、KMP）
3、ハッシュ
4、B 木インデックス
七、動的計画法
動的計画法は、重複する部分問題の解決に使用されるアルゴリズムです。具体的な解決手順は通常、次の 2 つのステップに分かれます：
1、再帰関係を決定する
2、問題の性質に応じて適切な計画戦略を採用し、ボトムアップの再帰またはトップダウンのメモ化検索を行う
メモ化検索では、状態テーブルを維持する必要がありますが、新しい値を計算するたびにテーブルを検索し、既に計算されている場合は直接使用します。
動的計画法のアルゴリズム：
1、二項係数の計算
C(n,k) = C(n-1,k-1)+C(n-2,k)
2、Warshall アルゴリズムによる推移閉包の計算
3、Floyd アルゴリズムによる完全最短経路の計算
4、最適二分木の構築
5、ナップサック問題
八、貪欲法
貪欲法の選択性質は、問題の全体の最適解が一連の局所的な最適な選択、つまり貪欲な選択によって達成できるということです。これは、貪欲法の実行可能性の最初の基本要素であり、また、貪欲法と動的計画法の主な違いでもあります。動的計画法では、各ステップでの選択は関連するサブ問題の解に依存することが多いです。したがって、関連するサブ問題の解を計算した後に選択を行う必要があります。一方、貪欲法では、現在の状態で最善の選択、つまり局所的な最適な選択を行います。その後、この選択によって生じる対応するサブ問題を解決します。貪欲法で行われる貪欲な選択は、過去の選択に依存することがありますが、将来の選択やサブ問題の解には依存しません。この違いのため、動的計画法は通常、ボトムアップの方法で各サブ問題を解き、貪欲法は通常、トップダウンの方法で逐次的な貪欲な選択を行い、問題をより小さなサブ問題に簡略化します。
貪欲法のアルゴリズム：
1、Prim、Kruskal アルゴリズムによる最小全域木の計算
2、Dijkstra アルゴリズム
3、ハフマン符号化
九、反復改善
いくつかの実行可能な解から始めて、それを繰り返し改善するためにいくつかの単純な手順を適用します：
1、実行可能な解を構築する
2、現在の解が最適でないかどうかをチェックし、最適でない場合は置き換えます。
反復改善アルゴリズム：
1、シンプレックス法と線形計画法
2、最大フロー
3、再帰的な下降
4、安定した結婚
5、EM
6、二部グラフのマッチング
十、バックトラック法と分岐限界法
実際には、状態空間ツリーとは意思決定ツリーのことであり、各意思決定ノードは一度の反復を表します。ツリーを枝刈り、成長させ、最終的な結果を導き出すために、ツリーを繰り返し操作します。
バックトラック法の応用：
1、N クイーン問題
2、ハミルトンサイクル
3、部分集合の生成
分岐限界法：
1、ナップサック問題
2、巡回セールスマン問題