Design-and-analysis-of-algorithms-quick-guide

提供:Dev Guides
移動先:案内検索

DAA-はじめに

アルゴリズムは、計算、データ処理、および自動推論タスクを実行する問題を解決する一連の操作ステップです。 アルゴリズムは、有限の時間と空間内で表現できる効率的な方法です。

アルゴリズムは、特定の問題の解決策を非常にシンプルかつ効率的な方法で表すための最良の方法です。 特定の問題に対するアルゴリズムがある場合、任意のプログラミング言語でアルゴリズムを実装できます。つまり、*アルゴリズムはどのプログラミング言語*からも独立しています。

アルゴリズム設計

アルゴリズム設計の重要な側面には、最小の時間とスペースを使用して効率的な方法で問題を解決するための効率的なアルゴリズムの作成が含まれます。

問題を解決するには、さまざまなアプローチに従うことができます。 そのうちのいくつかは、時間の消費に関して効率的である場合がありますが、他のアプローチはメモリ効率が良い場合があります。 ただし、時間消費とメモリ使用量の両方を同時に最適化することはできないことに注意してください。 アルゴリズムをより短い時間で実行する必要がある場合、より多くのメモリに投資する必要があり、アルゴリズムをより少ないメモリで実行する必要がある場合、より多くの時間を必要とします。

問題開発手順

計算上の問題を解決するには、次の手順が必要です。

  • 問題の定義
  • モデルの開発
  • アルゴリズムの仕様
  • アルゴリズムの設計
  • アルゴリズムの正当性を確認する
  • アルゴリズムの分析
  • アルゴリズムの実装
  • プログラムのテスト
  • ドキュメンテーション

アルゴリズムの特徴

アルゴリズムの主な特徴は次のとおりです-

  • アルゴリズムには一意の名前が必要です
  • アルゴリズムには、入力と出力のセットが明示的に定義されている必要があります
  • アルゴリズムは明確な操作で整然としています
  • アルゴリズムは有限時間で停止します。 アルゴリズムは無限に実行しないでください。つまり、ある時点でアルゴリズムを終了する必要があります。

疑似コード

擬似コードは、プレーンテキストに関連するあいまいさを伴わずに、特定のプログラミング言語の構文を知る必要なしに、アルゴリズムの高レベルの説明を提供します。

実行時間は、Pseudocodeを使用してアルゴリズムを基本的な操作のセットとして表現することにより、より一般的な方法で推定できます。

アルゴリズムと擬似コードの違い

アルゴリズムは、特定のタスクを実行するためにチューリング完全なコンピューターマシンによって実行されるプロセスを記述する特定の特性を備えた正式な定義です。 一般的に、「アルゴリズム」という言葉は、コンピューターサイエンスの高度なタスクを表すために使用できます。

一方、擬似コードは、多くの詳細な情報を残した、アルゴリズムの非公式で(多くの場合、初歩的な)人間が読める記述です。 擬似コードの記述にはスタイルの制限はなく、その唯一の目的は、アルゴリズムの高レベルのステップを自然言語で非常に現実的な方法で記述することです。

たとえば、挿入ソートのアルゴリズムは次のとおりです。

Algorithm: Insertion-Sort
Input: A list L of integers of length n
Output: A sorted list L1 containing those integers present in L
Step 1: Keep a sorted list L1 which starts off empty
Step 2: Perform Step 3 for each element in the original list L
Step 3: Insert it into the correct position in the sorted list L1.
Step 4: Return the sorted list
Step 5: Stop

アルゴリズムInsertion-Sortで前述した高レベルの抽象プロセスをより現実的な方法で記述する方法を説明する擬似コードを次に示します。

for i <- 1 to length(A)
   x <- A[i]
   j <- i
   while j > 0 and A[j-1] > x
      A[j] <- A[j-1]
      j <- j - 1
   A[j] <- x

このチュートリアルでは、アルゴリズムはC、C ++、Java、Python、およびその他のプログラミング言語に多くの点で似ている擬似コードの形式で提示されます。

DAA-アルゴリズムの分析

アルゴリズムの理論的分析では、漸近的な意味での複雑さを推定する、つまり、任意の大きな入力の複雑さ関数を推定することが一般的です。 「アルゴリズムの分析」*という用語は、ドナルドクヌースによって作られました。

アルゴリズム分析は、計算の複雑さの理論の重要な部分であり、特定の計算の問題を解決するためにアルゴリズムに必要なリソースの理論的な推定を提供します。 ほとんどのアルゴリズムは、任意の長さの入力で動作するように設計されています。 アルゴリズムの分析とは、アルゴリズムの実行に必要な時間とスペースのリソースの量を決定することです。

通常、アルゴリズムの効率または実行時間は、入力の長さを*時間の複雑さ*として知られるステップの数、または*空間の複雑さ*として知られるメモリの量に関連付ける関数として表されます。

分析の必要性

この章では、アルゴリズムの分析の必要性と、特定の問題に対してより良いアルゴリズムを選択する方法について説明します。1つの計算問題は異なるアルゴリズムで解決できるためです。

特定の問題のアルゴリズムを検討することにより、パターン認識の開発を開始できるため、このアルゴリズムを使用して同様のタイプの問題を解決できます。

これらのアルゴリズムの目的は同じですが、多くの場合、アルゴリズムは互いにかなり異なります。 たとえば、異なるアルゴリズムを使用して一連の数値をソートできることがわかっています。 1つのアルゴリズムによって実行される比較の数は、同じ入力に対して他のアルゴリズムと異なる場合があります。 したがって、これらのアルゴリズムの時間の複雑さは異なる場合があります。 同時に、各アルゴリズムに必要なメモリ空間を計算する必要があります。

アルゴリズムの分析は、アルゴリズムの問​​題解決能力を、必要な時間とサイズ(実装中のストレージのメモリサイズ)の観点から分析するプロセスです。 ただし、アルゴリズムの分析の主な関心事は、必要な時間またはパフォーマンスです。 一般的に、次のタイプの分析を実行します-

  • ワーストケース-サイズ a のインスタンスで実行されるステップの最大数。
  • ベストケース-サイズ a のインスタンスで実行される最小ステップ数。
  • 平均ケース-サイズ a のインスタンスで実行される平均ステップ数。
  • Amortized -時間の経過とともに平均化されたサイズ a の入力に適用される一連の操作。

問題を解決するには、メモリは限られているが十分なスペースが利用可能であるか、またはその逆のシステムでプログラムが実行される可能性があるため、時間とスペースの複雑さを考慮する必要があります。 このコンテキストで、*バブルソート*と*マージソート*を比較すると。 バブルソートには追加のメモリは必要ありませんが、マージソートには追加のスペースが必要です。 バブルソートの時間の複雑さはマージソートに比べて高くなりますが、メモリが非常に限られている環境でプログラムを実行する必要がある場合は、バブルソートを適用する必要があります。

DAA-分析の方法論

アルゴリズムのリソース消費を測定するには、この章で説明するように、さまざまな戦略が使用されます。

漸近解析

関数 f(n) の漸近的な動作は、 n が大きくなるにつれて f(n) が大きくなることを指します。

通常、大きな入力でプログラムがどれだけ遅くなるかを推定することに関心があるため、 n の小さな値を無視します。

目安としては、漸近的成長率が遅いほどアルゴリズムが優れているということです。 それは常に真実ではありませんが。

たとえば、線形アルゴリズム$ f(n)= d * n + k $は、常に2次アルゴリズム$ f(n)= c.n ^ 2 + q $よりも漸近的に優れています。

回帰方程式を解く

再帰とは、小さな入力での値の観点から関数を記述する方程式または不等式です。 繰り返しは、一般的に分割統治のパラダイムで使用されます。

*_T(n)_* がサイズ *n* の問題の実行時間であると考えてみましょう。

問題サイズが十分に小さい場合、たとえば n <cc は定数)の場合、単純な解決策は一定の時間がかかり、これは*θ(1)*と記述されます。 問題の分割により、サイズが$ \ frac \ {n} \ {b} $のサブ問題が多数発生する場合。

この問題を解決するために必要な時間は a.T(n/b) です。 除算に必要な時間が D(n) であり、副問題の結果を結合するのに必要な時間が C(n) であると考える場合、再帰関係は次のように表すことができます-

T(n)= \ begin \ {cases} \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\ :\:\:\:\:\ theta(1)&if \:n \ leqslant c \\ a T(\ frac \ {n} \ {b})+ D(n)+ C(n)&それ以外\ end \ {cases}

再発関係は、次の方法を使用して解決することができます-

  • 置換方法-この方法では、境界を推測し、数学的帰納法を使用して、仮定が正しいことを証明します。
  • 再帰ツリー方法-この方法では、各ノードがコストを表す再帰ツリーが形成されます。
  • マスターの定理-これは、再帰関係の複雑さを見つけるためのもう1つの重要な手法です。

償却分析

償却分析は、通常、一連の同様の操作が実行される特定のアルゴリズムに使用されます。

  • 償却分析では、一連の操作のコストを個別に制限するのではなく、シーケンス全体の実際のコストに制限があります。
  • 償却分析は、平均ケース分析とは異なります。確率は償却分析には含まれません。 償却分析は、最悪の場合の各操作の平均パフォーマンスを保証します。

設計と分析は密接に関連しているため、単なる分析用のツールではなく、設計について考える方法でもあります。

集計方法

集約メソッドは、問題の全体像を提供します。 この方法では、 n 操作に合計で最悪の場合 T(n) 時間がかかる場合。 その場合、各操作の償却コストは T(n)/n です。 異なる操作には異なる時間がかかる場合がありますが、この方法ではコストの変動は無視されます。

会計方法

この方法では、実際のコストに応じて、異なる操作に異なる料金が割り当てられます。 作業の償却コストが実際のコストを超える場合、差額は貸方としてオブジェクトに割り当てられます。 このクレジットは、実際のコストよりも償却コストが低い後のオペレーションの支払いに役立ちます。

*i ^ th ^* 操作の実際のコストと償却コストが$ c _ \ {i} $および$ \ hat \ {c _ \ {l}} $である場合、

\ displaystyle \ sum \ limits _ \ {i = 1} ^ n \ hat \ {c _ \ {l}} \ geqslant \ displaystyle \ sum \ limits _ \ {i = 1} ^ n c _ \ {i}

ポテンシャル法

この方法は、プリペイド作業をクレジットとして考慮するのではなく、プリペイド作業をポテンシャルエネルギーとして表します。 このエネルギーは、将来の運用に支払うために解放できます。

初期データ構造 D〜0〜 で始まる n 操作を実行する場合。 c〜i〜 を実際のコストとして、 _ D〜i〜'i ^ th ^ 操作のデータ構造として考えてみましょう。 潜在的な関数Theは、実数Ф( ' D〜i〜' )、 ' D〜i〜_ の関連する可能性にマップします。 償却コスト$ \ hat \ {c _ \ {l}} $は次のように定義できます

\ hat \ {c _ \ {l}} = c _ \ {i} + \ Phi(D _ \ {i})-\ Phi(D _ \ {i-1})

したがって、総償却コストは

\ displaystyle \ sum \ limits _ \ {i = 1} ^ n \ hat \ {c _ \ {l}} = \ displaystyle \ sum \ limits _ \ {i = 1} ^ n(c _ \ {i} + \ Phi (D _ \ {i})-\ Phi(D _ \ {i-1}))= \ displaystyle \ sum \ limits _ \ {i = 1} ^ n c _ \ {i} + \ Phi(D _ \ {n}) -\ Phi(D _ \ {0})

ダイナミックテーブル

テーブルに割り当てられたスペースが十分でない場合、テーブルをより大きなサイズのテーブルにコピーする必要があります。 同様に、多数のメンバーがテーブルから消去される場合、より小さなサイズでテーブルを再割り当てすることをお勧めします。

償却分析を使用すると、挿入と削除の償却コストが一定であり、動的テーブルの未使用領域が総領域の一定の割合を超えないことがわかります。

このチュートリアルの次の章では、漸近記法について簡単に説明します。

漸近記法とアプリオリ分析

アルゴリズムの設計では、アルゴリズムの複雑さの分析が重要な側面です。 主に、アルゴリズムの複雑さは、そのパフォーマンス、動作の速さまたは遅さを懸念しています。

アルゴリズムの複雑さは、データの処理に必要なメモリの量と処理時間に関して、アルゴリズムの効率を表します。

アルゴリズムの複雑さは、*時間*および*スペース*の2つの観点で分析されます。

時間の複雑さ

これは、入力のサイズの観点からアルゴリズムを実行するのに必要な時間を記述する関数です。 「時間」とは、実行されるメモリアクセスの数、整数間の比較の数、内部ループの実行回数、またはアルゴリズムにかかるリアルタイムの量に関連するその他の自然単位を意味します。

スペースの複雑さ

これは、アルゴリズムへの入力のサイズの観点から、アルゴリズムが消費するメモリ量を記述する関数です。 入力自体を保存するために必要なメモリをカウントするのではなく、必要な「余分な」メモリについてよく話します。 繰り返しますが、これを測定するために自然な(ただし固定長の)ユニットを使用します。

スペースの複雑さは、使用されるスペースが最小または明白であるために無視される場合がありますが、時間と同じくらい重要になることがあります。

漸近記法

アルゴリズムの実行時間は、命令セット、プロセッサ速度、ディスクI/O速度などに依存します。 したがって、アルゴリズムの効率を漸近的に推定します。

アルゴリズムの時間関数は* T(n)で表されます。 *n は入力サイズです。

アルゴリズムの複雑さを表すために、さまざまなタイプの漸近表記法が使用されます。 次の漸近表記法を使用して、アルゴリズムの実行時間の複雑さを計算します。

  • O -Big Oh
  • Ω-ビッグオメガ
  • θ-ビッグシータ
  • o -Little Oh
  • ω-小さなオメガ

O:漸近的上限

「O」(Big Oh)は最も一般的に使用される表記法です。 * nとして正の整数 n の値が存在する場合、関数 f(n)O(g(n)) である g(n) の順序で表現できます。 〜0〜および次のような正の定数 *c

すべての場合で$ n> n _ \ {0} $の場合は$ f(n)\ leqslant c.g(n)$

したがって、 _ g(n)'_f(n)' よりも速く成長するため、関数 g(n) は関数 f(n) の上限です。

与えられた関数$ f(n)= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう

$ g(n)= n ^ 3 $を考慮すると、

$ n> 2 $のすべての値に対して$ f(n)\ leqslant 5.g(n)$

したがって、 _ f(n)_ の複雑さは$ O(g(n))$として表すことができます。 $ O(n ^ 3)$

Ω:漸近的下限

定数 c が存在する場合、$ f(n)= \ Omega(g(n))$と言います。 n の十分に大きい値すべてに対して、$ f(n)\ geqslant c.g(n)$です。 ここで、 n は正の整数です。 これは、関数 g が関数 f の下限であることを意味します。 nの特定の値の後、fg を下回ることはありません。

与えられた関数$ f(n)= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう。

$ n> 0 $のすべての値に対して、$ g(n)= n ^ 3 $、$ f(n)\ geqslant 4.g(n)$を検討します。

したがって、 _ f(n)_ の複雑さは、$ \ Omega(g(n))$として表すことができます。 $ \ Omega(n ^ 3)$

θ:漸近タイトバウンド

$ c _ \ {1} .g(n)\ leqslant fという定数* c〜1〜および c〜2〜が存在する場合、$ f(n)= \ theta(g(n))$と言います。 (n) *n の十分に大きい値すべてに対して、\ leqslant c _ \ {2} .g(n)$。 ここで、 n は正の整数です。

これは、関数 g が関数 f の厳密な境界であることを意味します。

与えられた関数$ f(n)= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう

*n* のすべての大きな値に対して、$ g(n)= n ^ 3 $、$ 4.g(n)\ leqslant f(n)\ leqslant 5.g(n)$を検討します。

したがって、 _ f(n)_ の複雑さは$ \ theta(g(n))$として表すことができます。 $ \ theta(n ^ 3)$。

O-表記法

*O-notation* によって提供される漸近的な上限は、漸近的に厳密である場合とそうでない場合があります。 境界$ 2.n ^ 2 = O(n ^ 2)$は漸近的にタイトですが、境界$ 2.n = O(n ^ 2)$は漸近的ではありません。
*o-notation* を使用して、漸近的に厳密ではない上限を示します。

正の定数$ c> 0 $に対して o(g(n)) (nのgの小さなoh)を集合 f(n)= o(g(n)) として正式に定義し、 $ 0 \ leqslant f(n)\ leqslant cg(n)$のような値$ n _ \ {0}> 0 $が存在します。

直観的に、 o-notation では、 n が無限に近づくにつれて、関数 f(n)g(n) に比べて重要ではなくなります。あれは、

\ lim _ \ {n \ rightarrow \ infty} \ left(\ frac \ {f(n)} \ {g(n)} \ right)= 0

同じ関数$ f(n)= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう

$ g(n)= n ^ \ {4} $を考慮すると、

\ lim _ \ {n \ rightarrow \ infty} \ left(\ frac \ {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} \ {n ^ 4} \ right)= 0

したがって、 _ f(n)_ の複雑さは$ o(g(n))$として表すことができます。 $ o(n ^ 4)$。

ω–表記法

ω-記法*を使用して、漸近的にタイトでない下限を示します。 ただし、正式には、 *ω(g(n)) (nのgの小さなオメガ)を任意の正の定数* C>のセット _f(n)=ω(g(n)) として定義します。 0_ *および値$ n _ \ {0}> 0 $が存在し、$ 0 \ leqslant cg(n)<f(n)$です。

たとえば、$ \ frac \ {n ^ 2} \ {2} = \ omega(n)$ですが、$ \ frac \ {n ^ 2} \ {2} \ neq \ omega(n ^ 2)$です。 関係$ f(n)= \ omega(g(n))$は、次の制限が存在することを意味します

\ lim _ \ {n \ rightarrow \ infty} \ left(\ frac \ {f(n)} \ {g(n)} \ right)= \ infty

つまり、 _ n が無限に近づくと、 _ f(n)'_g(n)' に対して相対的に大きくなります。

同じ関数$ f(n)= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう

$ g(n)= n ^ 2 $を考慮すると、

$$ \ lim _ \ {n \ rightarrow \ infty} \ left(\ frac \ {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} \ {n ^ 2} \ right)= \ infty $ $

したがって、 _ f(n)_ の複雑さは$ o(g(n))$として表すことができます。 $ \ omega(n ^ 2)$。

アプリオリとアポスティーリ分析

Apriori分析とは、特定のシステムで実行する前に分析が実行されることを意味します。 この分析は、理論モデルを使用して関数が定義される段階です。 したがって、異なるメモリ、プロセッサ、コンパイラを備えた特定のシステムでアルゴリズムを実行するのではなく、アルゴリズムを見るだけで、アルゴリズムの時間と空間の複雑さを判断します。

アルゴリズムのアポストリアリ分析とは、システムで実行した後にのみアルゴリズムの分析を実行することを意味します。 これは、システムとシステムごとの変更に直接依存します。

業界では、ソフトウェアは一般に匿名ユーザー向けに作成され、業界に存在するシステムとは異なるシステムで実行されるため、アポスティアリ分析を実行できません。

Aprioriでは、漸近表記法を使用して、コンピューター間で変化する時間と空間の複雑さを判断します。ただし、漸近的には同じです。

DAA-スペースの複雑さ

この章では、アルゴリズムが必要とするスペースの量に関する計算問題の複雑さについて説明します。

スペースの複雑さは、時間の複雑さの多くの特徴を共有し、計算の難しさに従って問題を分類するさらなる方法として機能します。

スペースの複雑さとは何ですか?

スペースの複雑さは、アルゴリズムへの入力の量に関して、アルゴリズムが使用するメモリ(スペース)の量を記述する関数です。

入力自体を保存するのに必要なメモリをカウントするのではなく、必要な*余分なメモリ*について話します。 繰り返しますが、これを測定するために自然な(ただし固定長の)ユニットを使用します。

バイトを使用することもできますが、使用する整数の数、固定サイズの構造体の数などを使用する方が簡単です。

最終的に、私たちが思いつく関数は、ユニットを表現するのに必要な実際のバイト数とは無関係になります。

スペースの複雑さは、使用されるスペースが最小限および/または明らかであるため無視される場合がありますが、時間の複雑さと同じくらい重要な問題になる場合があります

定義

*M* をすべての入力で停止する決定論的な* Turing machine(TM)*とします。 *M* のスペースの複雑さは関数$ f \ colon N \ rightarrow N $です。ここで、 *_ f(n)_* はテープのセルの最大数で、 *M* は長さ *M* の入力をスキャンします。 *M* のスペースの複雑さが *_f(n)_* である場合、 *M* はスペース *_f(n)_* で実行されると言えます。

漸近表記を使用して、チューリングマシンの空間の複雑さを推定します。

$ f \ colon N \ rightarrow R ^ + $を関数とします。 スペースの複雑さのクラスは次のように定義することができます-

*_SPACE = \ {L | LはO(f(n))空間決定論的TM} _* によって決定される言語です
*_SPACE = \ {L | Lは、O(f(n))空間によって決定される言語です。非決定的TM} _*
*PSPACE* は、決定論的チューリングマシン上の多項式空間で決定可能な言語のクラスです。

つまり、 _ PSPACE = U〜k〜SPACE(n ^ k ^)_

サビッチの定理

スペースの複雑さに関連する最も初期の定理の1つは、サビッチの定理です。 この定理によれば、決定論的マシンは、少量のスペースを使用して非決定論的マシンをシミュレートできます。

時間の複雑さのために、そのようなシミュレーションは時間の指数関数的な増加を必要とするようです。 スペースの複雑さについて、この定理は、 _ f(n)' スペースを使用する非決定論的チューリングマシンは、 ' f ^ 2 ^(n)_ スペースを使用する決定論的TMに変換できることを示しています。

したがって、サヴィッチの定理は、任意の関数について、$ f \ colon N \ rightarrow R ^ + $であると述べています。ここで、$ f(n)\ geqslant n $

*_NSPACE(f(n))⊆SPACE(f(n))_*

複雑性クラス間の関係

次の図は、さまざまな複雑度クラス間の関係を示しています。

関係

これまで、このチュートリアルではPクラスとNPクラスについては説明していません。 これらについては後で説明します。

DAA-分割統治

多くのアルゴリズムは、サブ問題を再帰的に処理する特定の問題を解決するために、本質的に再帰的です。

  • 分割統治アプローチ*では、問題は小さな問題に分割され、次に小さな問題が個別に解決され、最後に小さな問題の解決策が大きな問題の解決策に結合されます。

一般的に、分割統治アルゴリズムには3つの部分があります-

  • *問題を、同じ問題の小さなインスタンスであるいくつかのサブ問題に分割します。
  • *サブ問題を再帰的に解決して、サブ問題を克服します。 それらが十分に小さい場合、サブケースを基本ケースとして解決します。
  • *サブ問題の解決策*を組み合わせて、元の問題の解決策にします。

分割統治アプローチの長所と短所

サブ問題は独立しているため、分割統治アプローチは並列性をサポートします。 したがって、この手法を使用して設計されたアルゴリズムは、マルチプロセッサシステムまたは異なるマシンで同時に実行できます。

このアプローチでは、ほとんどのアルゴリズムが再帰を使用して設計されているため、メモリ管理が非常に高くなります。 関数の状態を保存する必要がある再帰的な関数スタックが使用されます。

分割統治アプローチの適用

以下に、分割統治アプローチを使用して解決されるいくつかの問題を示します。

  • 数列の最大値と最小値を見つける
  • Strassenの行列乗算
  • ソートをマージ
  • 二分検索

DAA-最大最小問題

分割統治法によって解決できる単純な問題を考えてみましょう。

問題文

アルゴリズム分析の最大最小問題は、配列の最大値と最小値を見つけることです。

溶液

サイズ n の特定の配列 _numbers [] _ の最大数と最小数を見つけるには、次のアルゴリズムを使用できます。 最初に*単純なメソッド*を表し、次に*分割して征服するアプローチ*を提示します。

ナイーブ法

ナイーブ法は、問題を解決するための基本的な方法です。 この方法では、最大数と最小数を別々に見つけることができます。 最大数と最小数を見つけるには、次の簡単なアルゴリズムを使用できます。

Algorithm: Max-Min-Element (numbers[])
max := numbers[1]
min := numbers[1]

for i = 2 to n do
   if numbers[i] > max then
      max := numbers[i]
   if numbers[i] < min then
      min := numbers[i]
return (max, min)

分析

Naiveメソッドの比較数は 2n-2 です。

比較と分割のアプローチを使用して、比較の回数を減らすことができます。 以下はそのテクニックです。

分割統治アプローチ

このアプローチでは、アレイは2つの半分に分割されます。 次に、再帰アプローチを使用して、各半分の最大数と最小数を見つけます。 その後、各半分の2つの最大値の最大値と、各半分の2つの最小値の最小値を返します。

この問題では、配列内の要素数は$ y-x + 1 $です。ここで、 yx 以上です。

$ \ mathbf \ {\ mathit \ {Max-Min(x、y)}} $は、配列$ \ mathbf \ {\ mathit \ {numbers [x …​ y]}} $の最大値と最小値を返します。 。

Algorithm: Max - Min(x, y)
if y – x ≤ 1 then
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y]))
else
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋)
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y)
return (max(max1, max2), min(min1, min2))

分析

*_T(n)_* を$ \ mathbf \ {\ mathit \ {Max-Min(x、y)}} $によって行われた比較の数とします。ここで、要素の数は$ n = y-x + 1 $です。
*_T(n)_* が数値を表す場合、再帰関係は次のように表すことができます

T(n)= \ begin \ {cases} T \ left(\ lfloor \ frac \ {n} \ {2} \ rfloor \ right)+ T \ left(\ lceil \ frac \ {n} \ {2 } \ rceil \ right)+2&for \:n> 2 \\ 1&for \:n = 2 \\ 0&for \:n = 1 \ end \ {cases}

*_n_* は *2* の累乗の形式であると仮定します。 したがって、 *n = 2 ^ k ^* で、 *k* は再帰木の高さです。

So,

T(n)= 2.T(\ frac \ {n} \ {2})+ 2 = 2. \ left(\ begin \ {array} \ {c} 2.T(\ frac \ {n} \ {4})+ 2 \ end \ {array} \ right)+ 2 ..... = \ frac \ {3n} \ {2}-2

単純な方法と比較して、分割統治アプローチでは、比較の数が少なくなります。 ただし、漸近表記を使用すると、両方のアプローチが* O(n)*で表されます。

DAA-ソートのマージ

この章では、マージソートについて説明し、その複雑さを分析します。

問題文

数のリストをソートする問題は、すぐに分割統治戦略に役立ちます。リストを2つの半分に分割し、各半分を再帰的にソートしてから、ソートされた2つのサブリストをマージします。

溶液

このアルゴリズムでは、数値は配列 numbers [] _ に格納されます。 ここで、 ' p_' および q はサブ配列の開始インデックスと終了インデックスを表します。

Algorithm: Merge-Sort (numbers[], p, r)
if p < r then
q = ⌊(p + r)/2⌋
Merge-Sort (numbers[], p, q)
    Merge-Sort (numbers[], q + 1, r)
    Merge (numbers[], p, q, r)
Function: Merge (numbers[], p, q, r)
n1 = q – p + 1
n2 = r – q
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays
for i = 1 to n1
   leftnums[i] = numbers[p + i - 1]
for j = 1 to n2
   rightnums[j] = numbers[q+ j]
leftnums[n1 + 1] = ∞
rightnums[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
   if leftnums[i] ≤ rightnums[j]
      numbers[k] = leftnums[i]
      i = i + 1
   else
      numbers[k] = rightnums[j]
      j = j + 1

分析

Merge-Sortの実行時間を T(n) として考えてみましょう。 したがって、

$ T(n)= \ begin \ {cases} c&if \:n \ leqslant 1 \\ 2 \:x \:T(\ frac \ {n} \ {2})+ d \:x \:n &それ以外の場合\ end \ {cases} $ここで、_c_および_d_は定数です

したがって、この再帰関係を使用して、

T(n)= 2 ^ i T(\ frac \ {n} \ {2 ^ i})+ i.d.n

As、$ i = log \:n、\:T(n)= 2 ^ \ {log \:n} T(\ frac \ {n} \ {2 ^ \ {log \:n}})+ log \ :ndn $

$ = \:c.n + d.n.log \:n $

したがって、$ T(n)= O(n \:log \:n)$

次の例では、Merge-Sortアルゴリズムを段階的に示しています。 最初に、サブ配列に要素が1つだけ含まれるまで、すべての反復配列が2つのサブ配列に分割されます。 これらのサブアレイをさらに分割できない場合、マージ操作が実行されます。

DAA-バイナリ検索

この章では、分割統治法に基づく別のアルゴリズムについて説明します。

問題文

ソートされた配列に対してバイナリ検索を実行できます。 このアプローチでは、要素が要素のリストに属している場合、要素 x のインデックスが決定されます。 配列がソートされていない場合、線形検索を使用して位置が決定されます。

溶液

このアルゴリズムでは、要素 x' が配列 numbers [] _ に格納されている一連の数値に属しているかどうかを確認します。 ここで、 ' l_ および r は、検索操作を実行するサブアレイの左右のインデックスを表します。

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then
   return l
else
   m := ⌊(l + r)/2⌋
   if x ≤ numbers[m]  then
      return Binary-Search(numbers[], x, l, m)
   else
      return Binary-Search(numbers[], x, m+1, r)

分析

線形検索は O(n) 時間で実行されます。 一方、バイナリ検索では O(log n) 時間で結果が生成されます

  • T(n)を、 *n 要素の配列の最悪の場合の比較数とします。

したがって、

T(n)= \ begin \ {cases} 0&if \:n = 1 \\ T(\ frac \ {n} \ {2})+ 1&その他\ end \ {cases}

この再帰関係$ T(n)= log \:n $を使用します。

したがって、バイナリ検索では$ O(log \:n)$時間を使用します。

この例では、要素63を検索します。

バイナリ検索

DAA-Strassenの行列乗算

この章では、まず行列乗算の一般的な方法について説明し、後でStrassenの行列乗算アルゴリズムについて説明します。

問題文

2つの行列 XY を考えてみましょう。 XY を乗算して、結果のマトリックス Z を計算します。

ナイーブ法

最初に、単純な方法とその複雑さについて説明します。 ここでは、 _ Z = X×Y_ を計算しています。 ナイーブ法を使用すると、これらの行列の順序が p×qq×r の場合、2つの行列( XY )を乗算できます。 アルゴリズムは次のとおりです。

Algorithm: Matrix-Multiplication (X, Y, Z)
for i = 1 to p do
   for j = 1 to r do
      Z[i,j] := 0
      for k = 1 to q do
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

複雑

ここでは、整数演算に O(1) 時間かかると想定しています。 このアルゴリズムには3つの for ループがあり、一方はもう一方にネストされています。 したがって、アルゴリズムの実行には O(n ^ 3 ^) 時間かかります。

Strassenの行列乗算アルゴリズム

このコンテキストでは、Strassenの行列乗算アルゴリズムを使用して、時間消費を少し改善できます。

Strassenの行列乗算は、正方行列n は* 2のべき乗*)でのみ実行できます。 両方の行列の次数は n×n です。

以下に示すように、 XY 、および Z を4つの(n/2)×(n/2)行列に分割します−

$ Z = \ begin \ {bmatrix} I&J \\ K&L \ end \ {bmatrix} $ $ X = \ begin \ {bmatrix} A&B \\ C&D \ end \ {bmatrix} $および$ Y = \ begin \ {bmatrix} E&F \\ G&H \ end \ {bmatrix} $

Strassenのアルゴリズムを使用して、以下を計算します-

M _ \ {1} \:\ colon =(A + C)\ times(E + F)

M _ \ {2} \:\ colon =(B + D)\ times(G + H)

M _ \ {3} \:\ colon =(A-D)\ times(E + H)

M _ \ {4} \:\ colon = A \ times(F-H)

M _ \ {5} \:\ colon =(C + D)\ times(E)

M _ \ {6} \:\ colon =(A + B)\ times(H)

M _ \ {7} \:\ colon = D \ times(G-E)

その後、

I \:\ colon = M _ \ {2} + M _ \ {3}-M _ \ {6}-M _ \ {7}

J \:\ colon = M _ \ {4} + M _ \ {6}

K \:\ colon = M _ \ {5} + M _ \ {7}

L \:\ colon = M _ \ {1}-M _ \ {3}-M _ \ {4}-M _ \ {5}

分析

$ T(n)= \ begin \ {cases} c&if \:n = 1 \\ 7 \:x \:T(\ frac \ {n} \ {2})+ d \:x \:n ^ 2およびそれ以外の場合\ end \ {cases} $ここで、_c_および_d_は定数です

この再帰関係を使用して、$ T(n)= O(n ^ \ {log7})$を取得します

したがって、Strassenの行列乗算アルゴリズムの複雑さは$ O(n ^ \ {log7})$です。

DAA-貪欲な方法

すべてのアルゴリズム的アプローチの中で、最も単純で簡単なアプローチは貪欲法です。 このアプローチでは、将来の現在の決定の影響を心配することなく、現在の利用可能な情報に基づいて決定が行われます。

貪欲なアルゴリズムは、解決策を部分的に構築し、次の部分をそのような方法で選択することで、即座に利益をもたらします。 このアプローチは、以前の選択を再考することはありません。 このアプローチは、主に最適化の問題を解決するために使用されます。 貪欲な方法は実装が簡単で、ほとんどの場合非常に効率的です。 したがって、Greedyアルゴリズムはヒューリスティックに基づいたアルゴリズムパラダイムであり、グローバルな最適解を見つけることを期待して、各ステップでローカルの最適な選択に従うと言えます。

多くの問題では、妥当な時間で近似(最適に近い)解決策を提供しますが、最適な解決策を生成しません。

貪欲なアルゴリズムのコンポーネント

貪欲なアルゴリズムには、次の5つのコンポーネントがあります-

  • 候補セット-このセットからソリューションが作成されます。
  • 選択機能-ソリューションに追加する最適な候補を選択するために使用します。
  • 実現可能性関数-候補を使用してソリューションに貢献できるかどうかを判断するために使用されます。
  • 目的関数-解または部分解に値を割り当てるために使用されます。
  • ソリューション関数-完全なソリューションに到達したかどうかを示すために使用されます。

適用分野

貪欲なアプローチは、次のような多くの問題を解決するために使用されます

  • ダイクストラのアルゴリズムを使用して、2つの頂点間の最短経路を見つけます。
  • Primの/Kruskalのアルゴリズムなどを使用して、グラフで最小スパニングツリーを見つける

貪欲なアプローチが失敗する場所

多くの問題で、Greedyアルゴリズムは最適なソリューションを見つけられず、さらに最悪のソリューションを生成する可能性があります。 巡回セールスマンやナップザックなどの問題は、このアプローチでは解決できません。

DAA-フラクショナルナップザック

Greedyアルゴリズムは、ナップザック問題と呼ばれるよく知られた問題で非常によく理解できました。 同じ問題は他のアルゴリズム手法を使用することで解決できますが、貪欲な手法はフラクショナルナップザック問題を適時に合理的に解決します。 ナップザック問題について詳しく説明しましょう。

ナップザックの問題

それぞれが重みと値を持つアイテムのセットを指定して、コレクションに含めるアイテムのサブセットを決定し、合計重量が所定の制限以下で、合計値が可能な限り大きくなるようにします。

ナップザックの問題は、組み合わせ最適化の問題です。 それは、現実世界の問題の多くのより複雑な数学モデルの下位問題として現れます。 難しい問題に対する一般的なアプローチの1つは、最も制限の厳しい制約を特定し、他の制約を無視し、ナップザック問題を解決し、無視された制約を満たすように何らかの方法でソリューションを調整することです。

アプリケーション

何らかの制約とともにリソースを割り当てる多くの場合、問題はナップザック問題と同様の方法で導き出すことができます。 以下に例を示します。

  • 原材料をカットする最も無駄のない方法を見つける
  • ポートフォリオ最適化
  • 在庫切れの問題

問題シナリオ

泥棒は店を強奪し、ナップザックに W の最大重量を運ぶことができます。 ストアにはn個のアイテムがあり、 _ i ^ th ^ ' アイテムの重量は _w〜i〜' で、その利益は p〜i〜 です。 泥棒はどのようなアイテムを取るべきですか?

これに関連して、アイテムは、泥棒が最大の利益を得るアイテムを運ぶような方法で選択されるべきです。 したがって、泥棒の目的は利益を最大化することです。

アイテムの性質に基づいて、ナップザックの問題は次のように分類されます。

  • フラクショナルナップザック
  • ナップザック

フラクショナルナップザック

この場合、アイテムは小さな断片に分割される可能性があるため、泥棒はアイテムの一部を選択できます。

問題の声明によると、

  • ストアには n 個のアイテムがあります
  • i ^ th ^ アイテムの重量$ w _ \ {i}> 0 $
  • i ^ th ^ 項目の利益$ p _ \ {i}> 0 $および
  • ナップザックの容量は W です

ナップザック問題のこのバージョンでは、アイテムを小さな断片に分割できます。 したがって、泥棒は i ^ th ^ アイテムの x〜i〜 の一部のみを取得できます。

0 \ leqslant x _ \ {i} \ leqslant 1

*i ^ th ^* アイテムは、ナップザックの総重量に重量$ x _ \ {i} .w _ \ {i} $を提供し、総利益に$ x _ \ {i} .p _ \ {i} $を提供します。

したがって、このアルゴリズムの目的は

maximize \:\ displaystyle \ sum \ limits _ \ {n = 1} ^ n(x _ \ {i} .p _ \ {} i)

制約の対象

\ displaystyle \ sum \ limits _ \ {n = 1} ^ n(x _ \ {i} .w _ \ {} i)\ leqslant W

最適なソリューションがナップザックを正確に満たす必要があることは明らかです。そうしないと、残りのアイテムの一部を追加して全体の利益を増やすことができます。

したがって、最適な解は次のようにして得られます。

\ displaystyle \ sum \ limits _ \ {n = 1} ^ n(x _ \ {i} .w _ \ {} i)= W

このコンテキストでは、まず$ \ frac \ {p _ \ {i}} \ {w _ \ {i}} $の値に従ってこれらのアイテムを並べ替えて、$ \ frac \ {p _ \ {i} + 1} \ {w _ \ {i} +1} $≤$ \ frac \ {p _ \ {i}} \ {w _ \ {i}} $ ここで、 _ x_ はアイテムの一部を格納する配列です。

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)
for i = 1 to n
   do x[i] = 0
weight = 0
for i = 1 to n
   if weight + w[i] ≤ W then
      x[i] = 1
      weight = weight + w[i]
   else
      x[i] = (W - weight)/w[i]
      weight = W
      break
return x

分析

指定されたアイテムが既に$ \ mathbf \ {\ frac \ {p _ \ {i}} \ {w _ \ {i}}} $の降順でソートされている場合、while_loopは O(n)で時間がかかります ;したがって、ソートを含む合計時間は O(n logn) になります。

ナップザックの容量 W = 60 と提供されたアイテムのリストが次の表に示されていることを考えてみましょう-

Item A B C D
Profit 280 100 120 120
Weight 40 10 20 24
Ratio $(\frac\{p_{i}}\{w_{i}})$ 7 10 6 5

提供されたアイテムは$ \ mathbf \ {\ frac \ {p _ \ {i}} \ {w _ \ {i}}} $に基づいてソートされないため。 ソート後、アイテムは次の表のようになります。

Item B A C D
Profit 100 280 120 120
Weight 10 40 20 24
Ratio $(\frac\{p_{i}}\{w_{i}})$ 10 7 6 5

溶液

$ \ frac \ {p _ \ {i}} \ {w _ \ {i}} $に従ってすべてのアイテムを並べ替えた後。 B の重量がナップザックの容量より小さいため、最初にすべての B が選択されます。 次に、ナップザックの使用可能な容量が A の重量よりも大きいため、アイテム A が選択されます。 現在、 _ C_ が次の項目として選択されています。 ただし、ナップザックの残りの容量が C の重量よりも小さいため、アイテム全体を選択することはできません。

したがって、 _ C_ の端数(つまり、 (60 − 50)/20)が選択されます。

これで、ナップザックの容量は選択したアイテムと等しくなります。 したがって、これ以上アイテムを選択できません。

選択したアイテムの合計重量は 10 + 40 + 20&ast;です。 (10/20)= 60

合計利益は 100 + 280 + 120&ast;です。 (10/20)= 380 + 60 = 440

これが最適なソリューションです。 アイテムの異なる組み合わせを選択しても、それ以上の利益は得られません。

DAA-期限付きジョブシーケンス

問題文

ジョブシーケンスの問題の目的は、期限内に完了し、最大の利益をもたらす一連のジョブを見つけることです。

溶液

ジョブが期限までに完了した場合、期限と利益に関連する n の一連のジョブを考えてみましょう。 これらのジョブは、最大の利益が得られるように注文する必要があります。

指定されたすべてのジョブが期限内に完了しない場合があります。

*i ^ th ^* ジョブ *_J〜i〜_* の締め切りは *_d〜i〜_* であり、このジョブから受け取る利益は *_p〜i〜_* であるとします。 したがって、このアルゴリズムの最適なソリューションは、最大の利益を伴う実現可能なソリューションです。

したがって、$ 1 \ leqslant i \ leqslant n $に対して$ D(i)> 0 $です。

最初は、これらのジョブは利益に従って注文されます。 $ p _ \ {1} \ geqslant p _ \ {2} \ geqslant p _ \ {3} \ geqslant \:…​ \:\ geqslant p _ \ {n} $。

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k)
D(0) := J(0) := 0
k := 1
J(1) := 1  //means first job is selected
for i = 2 … n do
   r := k
   while D(J(r)) > D(i) and D(J(r)) ≠ r do
      r := r – 1
   if D(J(r)) ≤ D(i) and D(i) > r then
      for l = k … r + 1 by -1 do
         J(l + 1) := J(l)
         J(r + 1) := i
         k := k + 1

分析

このアルゴリズムでは、1つが別のループ内にある2つのループを使用しています。 したがって、このアルゴリズムの複雑さは$ O(n ^ 2)$です。

次の表に示すように、与えられたジョブのセットを考えてみましょう。 期限内に完了し、最大の利益をもたらす一連のジョブを見つける必要があります。 各ジョブには、期限と利益が関連付けられています。

Job J1 J2 J3 J4 J5
Deadline 2 1 3 2 1
Profit 60 100 20 40 20

溶液

この問題を解決するために、特定のジョブは利益に従って降順にソートされます。 したがって、ソート後、ジョブは次の表に示すように順序付けられます。

Job J2 J1 J4 J3 J5
Deadline 1 2 2 3 1
Profit 100 60 40 20 20

この一連のジョブから、最初に J〜2〜 を選択します。これは、期限内に完了することができ、最大の利益をもたらすためです。

  • 次に、 _ J〜4〜' と比較してより多くの利益が得られるため、 ' J〜1〜_ が選択されます。
  • 次のクロックでは、期限が過ぎているため、 _ J〜4〜' を選択できません。したがって、 ' J〜3〜_ は、期限内に実行されるときに選択されます。
  • ジョブ J〜5〜 は、期限内に実行できないため破棄されます。

したがって、ソリューションはジョブのシーケンス( J〜2〜、J〜1〜、J〜3〜 )であり、期限内に実行され、最大の利益をもたらします。

このシーケンスの総利益は 100 + 60 + 20 = 180 です。

DAA-最適なマージパターン

異なる長さのソート済みファイルのセットを単一のソート済みファイルにマージします。 結果のファイルが最短時間で生成される最適なソリューションを見つける必要があります。

ソートされたファイルの数が指定されている場合、それらを単一のソートされたファイルにマージする多くの方法があります。 このマージはペアで実行できます。 したがって、このタイプのマージは* 2-wayマージパターン*と呼ばれます。

異なるペアリングには異なる時間を必要とするため、この戦略では、多くのファイルをマージする最適な方法を決定します。 各ステップで、2つの最短シーケンスがマージされます。

  • p-recordファイル*と* q-recordファイル*をマージするには、 p + q レコードの移動が必要になる可能性があります。当然のことながら、各ステップで2つの最小ファイルをマージします。

双方向マージパターンは、バイナリマージツリーで表すことができます。 一連の n ソート済みファイル \ {f〜1〜、f〜2〜、f〜3〜、…、f〜n〜} を考えてみましょう。 最初は、この各要素は単一ノードのバイナリツリーと見なされます。 この最適なソリューションを見つけるために、次のアルゴリズムが使用されます。

Algorithm: TREE (n)
for i := 1 to n – 1 do
   declare new node
   node.leftchild := least (list)
   node.rightchild := least (list)
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)
   insert (list, node);
return least (list);

このアルゴリズムの最後に、ルートノードの重みが最適なコストを表します。

与えられたファイル、f〜1〜、f〜2〜、f〜3〜、f〜4〜、f〜5〜をそれぞれ20、30、10、5、30個の要素で考えてみましょう。

提供されたシーケンスに従ってマージ操作が実行される場合、

  • M〜1〜= f〜1〜とf〜2〜をマージ* ⇒ 20 + 30 = 50
  • M〜2〜= M〜1〜とf〜3〜をマージ ⇒ 50 + 10 = 60
  • M〜3〜= M〜2〜とf〜4〜をマージします。 ⇒ 60 + 5 = 65
  • M〜4〜= M〜3〜とf〜5〜のマージ ⇒ 65 + 30 = 95

したがって、操作の総数は

50 + 60 + 65 + 95 = 270

さて、より良い解決策はありますか?

昇順でサイズに応じて番号を並べ替えると、次のシーケンスが得られます-

  • f〜4〜、f〜3〜、f〜1〜、f〜2〜、f〜5〜*

したがって、このシーケンスでマージ操作を実行できます

  • M〜1〜= f〜4〜とf〜3〜をマージ ⇒ 5 + 10 = 15
  • M〜2〜= M〜1〜とf〜1〜をマージ ⇒ 15 + 20 = 35
  • M〜3〜= M〜2〜とf〜2〜*をマージする⇒ 35 + 30 = 65
  • M〜4〜= M〜3〜とf〜5〜のマージ ⇒ 65 + 30 = 95

したがって、操作の総数は

15 + 35 + 65 + 95 = 210

明らかに、これは前のものよりも優れています。

このコンテキストでは、このアルゴリズムを使用して問題を解決します。

初期セット

初期セット

ステップ1

ステップ-1

ステップ2

初期セット

ステップ-3

初期セット

ステップ-4

初期セット

したがって、ソリューションには15 + 35 + 60 + 95 = 205の比較が必要です。

DAA-動的プログラミング

動的プログラミングは、最適化問題でも使用されます。 分割統治法と同様に、動的計画法は、部分問題の解決策を組み合わせることで問題を解決します。 さらに、ダイナミックプログラミングアルゴリズムは各副問題を一度だけ解決し、その回答をテーブルに保存するため、毎回回答を再計算する作業を回避できます。

問題の2つの主な特性は、与えられた問題が動的計画法を使用して解決できることを示唆しています。 これらのプロパティは、*重複するサブ問題と最適なサブ構造*です。

重複するサブ問題

分割統治アプローチと同様に、ダイナミックプログラミングもサブ問題のソリューションを組み合わせます。 主に、1つの副問題の解決が繰り返し必要な場合に使用されます。 計算されたソリューションはテーブルに保存されるため、これらを再計算する必要はありません。 したがって、重複する副問題が存在する場合、この手法が必要です。

たとえば、バイナリ検索には重複する副問題はありません。 一方、フィボナッチ数の再帰プログラムには、多くの重複する副問題があります。

最適なサブ構造

与えられた問題の最適解がその副問題の最適解を使用して得られる場合、与えられた問題には最適な部分構造プロパティがあります。

たとえば、最短経路問題には、次の最適な部分構造プロパティがあります-

ノード x がソースノード u から宛先ノード v への最短パスにある場合、 u から v への最短パスは u から*への最短パスの組み合わせです。 x 、および *x から v への最短パス。

Floyd-WarshallやBellman-Fordなどの標準的な全ペア最短パスアルゴリズムは、動的プログラミングの典型的な例です。

動的プログラミングアプローチの手順

ダイナミックプログラミングアルゴリズムは、次の4つのステップを使用して設計されています-

  • 最適なソリューションの構造を特徴付けます。
  • 最適なソリューションの値を再帰的に定義します。
  • 通常はボトムアップ方式で、最適なソリューションの価値を計算します。
  • 計算された情報から最適なソリューションを構築します。

動的計画法アプローチの応用

  • 行列チェーンの乗算
  • 最長共通部分列
  • 巡回セールスマン問題

DAA-0-1ナップザック

このチュートリアルでは、先に、Greedyアプローチを使用した分数ナップザック問題について説明しました。 GreedyアプローチがFractional Knapsackの最適なソリューションを提供することを示しました。 ただし、この章では、0-1ナップザック問題とその分析について説明します。

0-1ナップザックでは、アイテムを破壊することはできません。つまり、泥棒はアイテムをまとめて持ち去るか、そのままにしておく必要があります。 これが、0-1ナップザックと呼ばれる理由です。

したがって、0-1ナップザックの場合、 _ x〜i〜' の値は _0' または 1 のいずれかで、他の制約は同じままです。

0-1ナップザックは貪欲なアプローチでは解決できません。 貪欲なアプローチは、最適なソリューションを保証しません。 多くの場合、貪欲なアプローチは最適なソリューションを提供します。

次の例は、ステートメントを確立します。

例1

ナップザックの容量はW = 25で、アイテムは次の表に示すとおりであると考えてみましょう。

Item A B C D
Profit 24 18 18 10
Weight 24 10 10 7

単位重量あたりの利益( p〜i〜/w〜i〜 )を考慮せずに、この問題を解決するために貪欲なアプローチを適用すると、最大の利益をもたらすため、最初の項目 A が選択されますすべての要素の中で。

アイテム A を選択すると、それ以上アイテムは選択されません。 したがって、この特定のアイテムセットでは、総利益は 24 です。 一方、最適なソリューションは、項目 B およびCを選択することで達成できます。総利益は18 + 18 = 36です。

例2

全体的な利益に基づいてアイテムを選択する代わりに、この例では、アイテムは比_p〜i〜/w〜i〜に基づいて選択されます。 ナップザックの容量は_W = 60で、アイテムは次の表に示すとおりであると考えてみましょう。

Item A B C
Price 100 280 120
Weight 10 40 20
Ratio 10 7 6

貪欲なアプローチを使用して、最初の項目 A が選択されます。 次に、次の項目 B が選択されます。 したがって、総利益は 100 + 280 = 380 です。 ただし、このインスタンスの最適なソリューションは、項目 B および C を選択することで実現できます。ここで、総利益は 280 + 120 = 400 です。

したがって、貪欲なアプローチは最適なソリューションを提供しない可能性があると結論付けることができます。

0-1ナップザックを解くには、ダイナミックプログラミングアプローチが必要です。

問題文

泥棒は店を強奪しており、最大重量 W をナップザックに運ぶことができます。 n 個のアイテムがあり、 i ^ th ^ アイテムの重量は w〜i〜 であり、このアイテムを選択する利益は p〜i〜 です。 泥棒はどのようなアイテムを取るべきですか?

動的プログラミングのアプローチ

*_i_* を、 *W* ドルの最適なソリューション *S* で最も高い番号のアイテムとします。 そして、 *_ S ^ '^ = S-\ {i} _* は *_W-w〜i〜_* ドルの最適なソリューションであり、ソリューション *_S_* の値は *_V〜i〜_* に値を加えたものです。副問題の。

この事実を次の式で表すことができます: c [i、w] をアイテム 1,2、…、i および最大〜i〜mum重量 w の解となるように定義します。

アルゴリズムは次の入力を取ります

  • 最大重量 W
  • アイテムの数 n
  • 2つのシーケンス v = <v〜1〜、v〜2〜、…、v〜n〜> および w = <w〜1〜、w〜2〜、…、w〜n〜>
Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
   c[0, w] = 0
for i = 1 to n do
   c[i, 0] = 0
   for w = 1 to W do
      if wi ≤ w then
         if vi + c[i-1, w-wi] then
            c[i, w] = vi + c[i-1, w-wi]
         else c[i, w] = c[i-1, w]
      else
         c[i, w] = c[i-1, w]

取得するアイテムのセットは、 c [n、w] から開始して、最適な値がどこから来たかを逆方向にトレースして、テーブルから推測できます。

c [i、w] = c [i-1、w] _の場合、アイテム _i はソリューションの一部ではないため、 c [i-1、w] でトレースを続けます。 それ以外の場合、アイテム i はソリューションの一部であり、 c [i-1、w-W] でトレースを続けます。

分析

このアルゴリズムは、テーブル_c_に(n + 1)。(_ w_ + 1)エントリがあるため、各エントリが計算にθ(1)時間を必要とするため、θ(nw)回かかります。

DAA-最長共通サブシーケンス

最も長い共通サブシーケンス問題は、指定された両方の文字列に存在する最も長いシーケンスを見つけることです。

サブシーケンス

シーケンスS = <s〜1〜、s〜2〜、s〜3〜、s〜4〜、…、s〜n〜>を考えてみましょう。

S上のシーケンスZ = <z〜1〜、z〜2〜、z〜3〜、z〜4〜、…、z〜m〜>は、Sのサブシーケンスと呼ばれます。いくつかの要素の削除。

共通サブシーケンス

*_X_* と *_Y_* は、有限要素セット上の2つのシーケンスであるとします。 *_Z_* が *_X_* と *_Y_* の両方のサブシーケンスである場合、 *_ Z_* は *_X_* と *_Y_* の共通サブシーケンスであると言えます。

最長共通部分列

シーケンスのセットが指定されている場合、最長の共通サブシーケンス問題は、最大長のすべてのシーケンスの共通サブシーケンスを見つけることです。

最も長い共通サブシーケンス問題は、diff-utilityなどのデータ比較プログラムの基礎である古典的なコンピューターサイエンスの問題であり、バイオインフォマティクスに応用されています。 また、SVNやGitなどのリビジョン管理システムによって、リビジョン管理されたファイルのコレクションに加えられた複数の変更を調整するために広く使用されています。

ナイーブ法

*_X_* を長さ *_m_* のシーケンスとし、 *_ Y_* を長さ *_n_* のシーケンスとします。 *_X_* のすべてのサブシーケンスが *_Y_* のサブシーケンスであるかどうかを確認し、見つかった最長の共通サブシーケンスを返します。
*_X_* には *_2 ^ m ^ _* サブシーケンスがあります。 シーケンスが *_Y_* のサブシーケンスであるかどうかをテストするには、 *_ O(n)_* 時間かかります。 したがって、ナイーブアルゴリズムには *_O(n2 ^ m ^)_* 時間かかります。

動的計画法

_X = <x〜1〜、x〜2〜、x〜3〜、…、x〜m〜> _および_Y = <y〜1〜、y〜2〜、y〜3〜、…、y〜 n〜> _はシーケンスです。 要素の長さを計算するには、次のアルゴリズムが使用されます。

この手順では、テーブル _C [m、n] _ が行優先順に計算され、別のテーブル _B [m、n] _ が計算されて最適なソリューションが構築されます。

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X)
n := length(Y)
for i = 1 to m do
   C[i, 0] := 0
for j = 1 to n do
   C[0, j] := 0
for i = 1 to m do
   for j = 1 to n do
      if xi = yj
         C[i, j] := C[i - 1, j - 1] + 1
         B[i, j] := ‘D’
      else
         if C[i -1, j] ≥ C[i, j -1]
            C[i, j] := C[i - 1, j] + 1
            B[i, j] := ‘U’
         else
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’
return C and B
Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0
   return
if B[i, j] = ‘D’
   Print-LCS(B, X, i-1, j-1)
   Print(xi)
else if B[i, j] = ‘U’
   Print-LCS(B, X, i-1, j)
else
   Print-LCS(B, X, i, j-1)

このアルゴリズムは、 X および Y の最長共通サブシーケンスを出力します。

分析

テーブルにデータを入力するには、外側の for' ループが m 回繰り返され、内側の for ループが n 回繰り返されます。 したがって、アルゴリズムの複雑さは_O(m、n)です。ここで、 ' m_ および n は2つの文字列の長さです。

この例では、2つの文字列 X = BACDB および Y = BDCB を使用して、最も長い共通サブシーケンスを見つけます。

アルゴリズムLCS-Length-Table-Formulation(上記)に従って、テーブルC(左側に表示)とテーブルB(右側に表示)を計算しました。

表Bでは、「D」、「L」、「U」の代わりに、それぞれ斜め矢印、左矢印、上矢印を使用しています。 テーブルBを生成した後、LCSは関数LCS-Printによって決定されます。 結果はBCBです。

LCS

DAA-スパニングツリー

  • スパニングツリー*は、すべての頂点が最小数のエッジで接続されている無向グラフのサブセットです。

すべての頂点がグラフで接続されている場合、少なくとも1つのスパニングツリーが存在します。 グラフには、複数のスパニングツリーが存在する場合があります。

プロパティ

  • スパニングツリーにはサイクルがありません。
  • 他の頂点から任意の頂点に到達できます。

次のグラフでは、強調表示されたエッジがスパニングツリーを形成しています。

エッジスピニングツリー

最小スパニングツリー

  • Minimum Spanning Tree(MST)*は、すべての頂点を最小の総エッジウェイトと一緒に接続する、接続された重み付き無向グラフのエッジのサブセットです。 MSTを導出するには、PrimのアルゴリズムまたはKruskalのアルゴリズムを使用できます。 したがって、この章では、Primのアルゴリズムについて説明します。

すでに説明したように、1つのグラフに複数のスパニングツリーが存在する場合があります。 n 個の頂点がある場合、スパニングツリーには n-1 個のエッジが必要です。 このコンテキストで、グラフの各エッジが重みに関連付けられ、複数のスパニングツリーが存在する場合、グラフの最小スパニングツリーを見つける必要があります。

さらに、重複する重み付きエッジが存在する場合、グラフには複数の最小スパニングツリーが含まれることがあります。

最小スピニングツリー

上記のグラフでは、スパニングツリーを示していますが、これは最小スパニングツリーではありません。 このスパニングツリーのコストは、(5 + 7 + 3 + 3 + 5 + 8 + 3 + 4)= 38です。

Primのアルゴリズムを使用して、最小スパニングツリーを見つけます。

プリムのアルゴリズム

プリムのアルゴリズムは、最小スパニングツリーを見つける貪欲なアプローチです。 このアルゴリズムでは、MSTを形成するために、任意の頂点から開始できます。

Algorithm: MST-Prim’s (G, w, r)
for each u є G.V
   u.key = ∞
   u.∏ = NIL
r.key = 0
Q = G.V
while Q ≠ Ф
   u = Extract-Min (Q)
   for each v є G.adj[u]
      if each v є Q and w(u, v) < v.key
         v.∏ = u
         v.key = w(u, v)

関数Extract-Minは、最小のエッジコストで頂点を返します。 この関数はmin-heapで機能します。

Primのアルゴリズムを使用して、任意の頂点から開始できます。頂点 1 から開始しましょう。

頂点 3 は最小のエッジコストで頂点 1 に接続されているため、エッジ*(1、2)*がスパニングツリーに追加されます。

次に、エッジ*(2、3)は、エッジ *\ {(1、2)、(2、3)、(3、4)、(3、7)} の最小値であると見なされます。

次のステップでは、最小コストでエッジ*(3、4)および(2、4)を取得します。 エッジ(3、4)*はランダムに選択されます。

同様に、エッジ*(4、5)、(5、7)、(7、8)、(6、8)および(6、9)*が選択されます。 すべての頂点にアクセスすると、アルゴリズムが停止します。

スパニングツリーのコストは、(2 + 2 + 3 + 2 + 5 + 2 + 3 + 4)= 23です。 このグラフには、 23 未満のコストのスパニングツリーはありません。

Prim’s Algorithm

DAA-最短経路

ダイクストラのアルゴリズム

ダイクストラのアルゴリズムは、有向グラフ_G =(V、E)の単一ソース最短パス問題を解決します。ここで、すべてのエッジは非負です(つまり、各エッジ_(u、v)≥0 u、v)ЄE)。

次のアルゴリズムでは、最小のキーを持つノードを抽出する1つの関数 Extract-Min() を使用します。

Algorithm: Dijkstra’s-Algorithm (G, w, s)
for each vertex v Є G.V
   v.d := ∞
   v.∏ := NIL
s.d := 0
S := Ф
Q := G.V
while Q ≠ Ф
   u := Extract-Min (Q)
   S := S U {u}
   for each vertex v Є G.adj[u]
      if v.d > u.d + w(u, v)
         v.d := u.d + w(u, v)
         v.∏ := u

分析

このアルゴリズムの複雑さは、Extract-Min関数の実装に完全に依存しています。 最小検索関数が線形検索を使用して実装されている場合、このアルゴリズムの複雑さは O(V ^ 2 ^ + E) です。

このアルゴリズムでは、 _ Extract-Min()' 関数が最小のキーで _Q' からノードを返すmin-heapを使用すると、このアルゴリズムの複雑さをさらに減らすことができます。

頂点 19 をそれぞれ開始頂点と宛先頂点として考えてみましょう。 最初は、開始頂点を除くすべての頂点に∞のマークが付けられ、開始頂点に 0 のマークが付けられます。

Vertex Initial Step1 V1 Step2 V3 Step3 V2 Step4 V4 Step5 V5 Step6 V7 Step7 V8 Step8 V6
1 0 0 0 0 0 0 0 0 0
2 5 4 4 4 4 4 4 4
3 2 2 2 2 2 2 2 2
4 7 7 7 7 7 7
5 11 9 9 9 9 9
6 17 17 16 16
7 11 11 11 11 11 11 11
8 16 13 13 13
9 20

したがって、頂点 1 からの頂点 9 の最小距離は 20 です。 そしてその道は

1→3→7→8→6→9

このパスは、先行情報に基づいて決定されます。

パス

ベルマンフォードアルゴリズム

このアルゴリズムは、エッジの重みが負になる可能性のある有向グラフ G =(V、E) の単一ソース最短パス問題を解決します。 さらに、負の加重サイクルが存在しない場合、このアルゴリズムを適用して最短経路を見つけることができます。

Algorithm: Bellman-Ford-Algorithm (G, w, s)
for each vertex v Є G.V
   v.d := ∞
   v.∏ := NIL
s.d := 0
for i = 1 to |G.V| - 1
   for each edge (u, v) Є G.E
      if v.d > u.d + w(u, v)
         v.d := u.d +w(u, v)
         v.∏ := u
for each edge (u, v) Є G.E
   if v.d > u.d + w(u, v)
      return FALSE
return TRUE

分析

最初の for ループは初期化に使用され、 _ O(V)' 回実行されます。 次の for ループが実行されます| * ' V-1 '' | _O(E) *回かかるエッジを通過します。

したがって、Bellman-Fordアルゴリズムは O(V、E) 時間で実行されます。

次の例は、Bellman-Fordアルゴリズムが段階的に機能する方法を示しています。 このグラフにはネガティブエッジがありますが、ネガティブサイクルはないため、この手法を使用して問題を解決できます。

初期化時には、ソースを除くすべての頂点に∞のマークが付けられ、ソースには 0 のマークが付けられます。

グラフ

最初のステップでは、ソースから到達可能なすべての頂点が最小コストで更新されます。 したがって、頂点 a および h が更新されます。

更新済み

次のステップでは、頂点 a、b、f および e が更新されます。

次のパス

同じロジックに従って、このステップで頂点 b、f、c および g が更新されます。

頂点

ここでは、頂点 c および d が更新されます。

頂点の更新

したがって、頂点 s と頂点 d の間の最小距離は 20 です。

先行情報に基づいて、パスはs→h→e→g→c→d

DAA-多段グラフ

多段グラフ* G =(V、E)は、頂点が *kk> 1 )個の互いに素なサブセットに分割されている有向グラフです S = \ {s〜1〜、s〜2〜 、…、s〜k〜} _ エッジ(u、v)がEにある場合、パーティション内の一部のサブセットに対して_uЄs〜i〜_および_v s s〜1 + 1〜 * _ s〜1〜' | = | ' s〜k〜_ * | = 1。

頂点 sЄs〜1〜source と呼ばれ、頂点 tЄs〜k〜sink と呼ばれます。

*_G_* は通常、重み付きグラフであると想定されます。 このグラフでは、エッジのコスト_(i、j)_は_c(i、j)_で表されます。 したがって、ソース *_s_* からシンク *_t_* へのパスのコストは、このパスの各エッジのコストの合計です。

多段グラフの問題は、ソース s からシンク t への最小コストのパスを見つけることです。

多段グラフの概念を理解するには、次の例を検討してください。

多段グラフ

式に従って、次の手順を使用してコスト*(i、j)*を計算する必要があります

ステップ-1:コスト(K-2、j)

このステップでは、3つのノード(ノード4、5。 6) j として選択されます。 したがって、このステップで最小コストを選択する3つのオプションがあります。

Cost(3、4)= min \ {c(4、7)+ Cost(7、9)、c(4、8)+ Cost(8、9)} = 7

Cost(3、5)= min \ {c(5、7)+ Cost(7、9)、c(5、8)+ Cost(8、9)} = 5

Cost(3、6)= min \ {c(6、7)+ Cost(7、9)、c(6、8)+ Cost(8、9)} = 5

ステップ-2:コスト(K-3、j)

ステージk-3 = 2では2と3の2つのノードがあるため、2つのノードがjとして選択されます。 したがって、値i = 2およびj = 2および3です。

_Cost(2、2)= min \ {c(2、4)+ Cost(4、8)+ Cost(8、9)、c(2、6)+ _

Cost(6、8)+ Cost(8、9)} = 8

Cost(2、3)= \ {c(3、4)+ Cost(4、8)+ Cost(8、9)、c(3、5)+ Cost(5、8)+ Cost(8、9) 、c(3、6)+コスト(6、8)+コスト(8、9)} = 10

ステップ-3:コスト(K-4、j)

Cost(1、1)= \ {c(1、2)+ Cost(2、6)+ Cost(6、8)+ Cost(8、9)、c(1、3)+ Cost(3、5) +コスト(5、8)+コスト(8、9))} = 12

c(1、3)+コスト(3、6)+コスト(6、8 +コスト(8、9))} = 13

したがって、最小コストのパスは 1→3→5→8→9 です。

DAA-巡回セールスマン問題

問題文

旅行者は、リストからすべての都市を訪問する必要があります。このリストでは、すべての都市間の距離がわかっており、各都市を一度だけ訪問する必要があります。 彼が各都市を一度だけ正確に訪れ、元の都市に戻る最短ルートは何ですか?

溶液

巡回セールスマンの問題は、最も悪名高い計算上の問題です。 ブルートフォースアプローチを使用して、可能なすべてのツアーを評価し、最適なツアーを選択できます。 グラフ内の n 個の頂点には、*(_ n_-1)!*個の可能性があります。

多項式時間アルゴリズムはありませんが、動的プログラミングアプローチを使用したブルートフォースの代わりに、短時間でソリューションを取得できます。

グラフ G =(V、E) を考えてみましょう。 _ V_ は都市のセットで、 _ E_ は重み付きエッジのセットです。 エッジ e(u、v) は、頂点 u および v が接続されていることを表します。 頂点 uv の間の距離は d(u、v) であり、非負でなければなりません。

私たちが都市 1 で出発し、いくつかの都市を訪れた後、都市 j にいるとします。 したがって、これは部分的なツアーです。 j を知っておく必要があります。これにより、次に訪れるのに最も便利な都市が決まるからです。 また、これまでに訪れたすべての都市を知る必要があります。そのため、それらの都市のいずれも繰り返さないようにします。 したがって、これは適切な副問題です。

都市のサブセットの場合 SЄ\ {1、2、3、…​ n_1 _j *で終わる。

いつ| * _ S ' * | > 1、パスは 1 で開始および終了できないため、 ' C(S、1)_ = defineを定義します。

さて、小さな副問題に関して* C(S、j)を表現しましょう。 *1 で開始し、 j で終了する必要があります。 次の都市を選択する必要があります

C(S、j)= min \:C(S-\ lbrace j \ rbrace、i)+ d(i、j)\:where \:i \ in S \:and \:i \ neq jc( S、j)= minC(s- \ lbrace j \ rbrace、i)+ d(i、j)\:where \:i \ in S \:and \:i \ neq j

Algorithm: Traveling-Salesman-Problem
C ({1}, 1) = 0
for s = 2 to n do
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1
      C (S, 1) = ∞
   for all j Є S and j ≠ 1
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

分析

サブ問題は最大で$ 2 ^ n.n $個あり、それぞれの解決には線形の時間がかかります。 したがって、合計実行時間は$ O(2 ^ n.n ^ 2)$です。

次の例では、巡回セールスマンの問題を解決する手順を示します。

分析

上記のグラフから、次の表を作成します。

1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0

S =Φ

\ smallコスト(2、\ Phi、1)= d(2,1)= 5 \ smallコスト(2、\ Phi、1)= d(2,1)= 5

\ smallコスト(3、\ Phi、1)= d(3,1)= 6 \ smallコスト(3、\ Phi、1)= d(3,1)= 6

\ smallコスト(4、\ Phi、1)= d(4,1)= 8 \ smallコスト(4、\ Phi、1)= d(4,1)= 8

S = 1

\ smallコスト(i、s)=最小\ lbraceコスト(j、s –(j))+ d [i、j] \ rbrace \ smallコスト(i、s)= min \ lbraceコスト(j、s )-(j))+ d [i、j] \ rbrace

\ smallコスト(2、\ lbrace 3 \ rbrace、1)= d [2,3] +コスト(3、\ Phi、1)= 9 + 6 = 15cost(2、\ lbrace3 \ rbrace、1)= d [2,3] + cost(3、\ Phi、1)= 9 + 6 = 15

\ smallコスト(2、\ lbrace 4 \ rbrace、1)= d [2,4] +コスト(4、\ Phi、1)= 10 + 8 = 18cost(2、\ lbrace4 \ rbrace、1)= d [2,4] + cost(4、\ Phi、1)= 10 + 8 = 18

\ smallコスト(3、\ lbrace 2 \ rbrace、1)= d [3,2] +コスト(2、\ Phi、1)= 13 + 5 = 18cost(3、\ lbrace2 \ rbrace、1)= d [3,2] + cost(2、\ Phi、1)= 13 + 5 = 18

\ smallコスト(3、\ lbrace 4 \ rbrace、1)= d [3,4] +コスト(4、\ Phi、1)= 12 + 8 = 20cost(3、\ lbrace4 \ rbrace、1)= d [3,4] + cost(4、\ Phi、1)= 12 + 8 = 20

\ smallコスト(4、\ lbrace 3 \ rbrace、1)= d [4,3] +コスト(3、\ Phi、1)= 9 + 6 = 15cost(4、\ lbrace3 \ rbrace、1)= d [4,3] + cost(3、\ Phi、1)= 9 + 6 = 15

\ smallコスト(4、\ lbrace 2 \ rbrace、1)= d [4,2] +コスト(2、\ Phi、1)= 8 + 5 = 13cost(4、\ lbrace2 \ rbrace、1)= d [4,2] + cost(2、\ Phi、1)= 8 + 5 = 13

S = 2

\ small Cost(2、\ lbrace 3、4 \ rbrace、1)= \ begin \ {cases} d [2、3] + Cost(3、\ lbrace 4 \ rbrace、1)= 9 + 20 = 29 \\ d [2、4] + Cost(4、\ lbrace 3 \ rbrace、1)= 10 + 15 = 25 = 25 \ small Cost(2、\ lbrace 3,4 \ rbrace、1)\\\ lbrace d [2,3] + \ small cost(3、\ lbrace4 \ rbrace、1)= 9 + 20 = 29d [2,4] + \ small Cost(4、\ lbrace 3 \ rbrace、1)= 10 + 15 = 25 \ end \ {cases} = 25

\ small Cost(3、\ lbrace 2、4 \ rbrace、1)= \ begin \ {cases} d [3、2] + Cost(2、\ lbrace 4 \ rbrace、1)= 13 + 18 = 31 \\ d [3、4] + Cost(4、\ lbrace 2 \ rbrace、1)= 12 + 13 = 25 = 25 \ small Cost(3、\ lbrace 2,4 \ rbrace、1)\\\ lbrace d [3,2] + \ small cost(2、\ lbrace4 \ rbrace、1)= 13 + 18 = 31d [3,4] + \ small Cost(4、\ lbrace 2 \ rbrace、1)= 12 + 13 = 25 \ end \ {cases} = 25

\ small Cost(4、\ lbrace 2、3 \ rbrace、1)= \ begin \ {cases} d [4、2] + Cost(2、\ lbrace 3 \ rbrace、1)= 8 + 15 = 23 \\ d [4、3] + Cost(3、\ lbrace 2 \ rbrace、1)= 9 + 18 = 27 = 23 \ small Cost(4、\ lbrace 2,3 \ rbrace、1)\\\ lbrace d [4,2] + \ small cost(2、\ lbrace3 \ rbrace、1)= 8 + 15 = 23d [4,3] + \ small Cost(3、\ lbrace 2 \ rbrace、1)= 9 + 18 = 27 \ end \ {cases} = 23

S = 3

\ small Cost(1、\ lbrace 2、3、4 \ rbrace、1)= \ begin \ {cases} d [1、2] + Cost(2、\ lbrace 3、4 \ rbrace、1)= 10 + 25 = 35 \\ d [1、3] + Cost(3、\ lbrace 2、4 \ rbrace、1)= 15 + 25 = 40 \\ d [1、4] + Cost(4、\ lbrace 2、 3 \ rbrace、1)= 20 + 23 = 43 = 35 cost(1、\ lbrace 2,3,4 \ rbrace)、1)\\ d [1,2] + cost(2、\ lbrace 3,4 \ rbrace、1)= 10 + 25 = 35 \\ d [1,3] + cost(3、\ lbrace 2,4 \ rbrace、1)= 15 + 25 = 40 \\ d [1,4] + cost( 4、\ lbrace 2,3 \ rbrace、1)= 20 + 23 = 43 = 35 \ end \ {cases}

最小コストパスは35です。

コスト \ {1、\ {2、3、4}、1} から始めて、 d [1、2] の最小値を取得します。 s = 3 の場合、1から2(コストは10)のパスを選択し、逆方向に進みます。 s = 2 の場合、 d [4、2] の最小値を取得します。 2から4(コストは10)のパスを選択し、逆方向に進みます。

*s = 1* の場合、 *d [4、3]* の最小値を取得します。 パス4から3(コストは9)を選択して、* s =Φ*ステップに進みます。 *d [3、1]* (コストは6)の最小値を取得します。

DAA-最適コストバイナリ検索ツリー

バイナリ検索ツリー(BST)は、キー値が内部ノードに保存されるツリーです。 外部ノードはヌルノードです。 キーは辞書順、つまり 内部ノードごとに、左側のサブツリーのすべてのキーはノードのキーよりも小さく、右側のサブツリーのすべてのキーは大きくなります。

各キーを検索する頻度がわかっている場合、ツリー内の各ノードにアクセスするための予想コストを計算するのは非常に簡単です。 最適なバイナリ検索ツリーはBSTであり、各ノードを見つけるための予想コストは最小限です。

BSTの要素の検索時間は O(n) ですが、Balanced-BSTの検索時間は O(log n) です。 この場合も、最適コストバイナリ検索ツリーで検索時間を改善することができ、最も頻繁に使用されるデータをルートおよびルート要素により近く配置し、最も頻繁に使用されないデータをリーフおよびリーフに配置します。

ここでは、最適なバイナリ検索ツリーアルゴリズムを示します。 まず、提供された n 個の異なるキーのセットからBSTを構築します _ <k〜1〜、k〜2〜、k〜3〜、…​ k〜n〜> ' 。 ここで、キー _K〜i〜' にアクセスする確率は p〜i〜 です。 いくつかのダミーキー(* d〜0〜、d〜1〜、d〜2〜、…​ キーセット _K に存在しない値に対していくつかの検索が実行される可能性があるため、d〜n〜_ )が追加されます。 各ダミーキー *d〜i〜 に対するアクセスの確率は q〜i〜 です。

Optimal-Binary-Search-Tree(p, q, n)
e[1…n + 1, 0…n],
w[1…n + 1, 0…n],
root[1…n + 1, 0…n]
for i = 1 to n + 1 do
   e[i, i - 1] := qi - 1
   w[i, i - 1] := qi - 1
for l = 1 to n do
   for i = 1 to n – l + 1 do
      j = i + l – 1 e[i, j] := ∞
      w[i, i] := w[i, i -1] + pj + qj
      for r = i to j do
         t := e[i, r - 1] + e[r + 1, j] + w[i, j]
         if t < e[i, j]
            e[i, j] := t
            root[i, j] := r
return e and root

分析

3つのネストされた for ループが使用されるため、アルゴリズムには* O(n ^ 3 ^)時間が必要です。 これらの各ループは、最大で *n の値を取ります。

次のツリーを考慮すると、コストは2.80ですが、これは最適な結果ではありません。

ツリー

Node Depth Probability Contribution
k1 1 0.15 0.30
k2 0 0.10 0.10
k3 2 0.05 0.15
k4 1 0.10 0.20
k5 2 0.20 0.60
d0 2 0.05 0.15
d1 2 0.10 0.30
d2 3 0.05 0.20
d3 3 0.05 0.20
d4 3 0.05 0.20
d5 3 0.10 0.40
Total 2.80

この章で説明するアルゴリズムを使用して最適なソリューションを得るために、次の表が生成されます。

次の表では、列インデックスは i 、行インデックスは j です。

e 1 2 3 4 5 6
5 2.75 2.00 1.30 0.90 0.50 0.10
4 1.75 1.20 0.60 0.30 0.05
3 1.25 0.70 0.25 0.05
2 0.90 0.40 0.05
1 0.45 0.10
0 0.05
w 1 2 3 4 5 6
5 1.00 0.80 0.60 0.50 0.35 0.10
4 0.70 0.50 0.30 0.20 0.05
3 0.55 0.35 0.15 0.05
2 0.45 0.25 0.05
1 0.30 0.10
0 0.05
root 1 2 3 4 5
5 2 4 5 5 5
4 2 2 4 4
3 2 2 3
2 1 2
1 1

これらのテーブルから、最適なツリーを形成できます。

DAA-バイナリヒープ

ヒープにはいくつかの種類がありますが、この章ではバイナリヒープについて説明します。 バイナリヒープ*は、完全なバイナリツリーに似たデータ構造です。 ヒープデータ構造は、以下で説明する順序付けプロパティに従います。 通常、ヒープは配列で表されます。 この章では、ヒープを *H で表します。

ヒープの要素は配列に格納されるため、開始インデックスを 1 として、 i ^ th ^ 要素の親ノードの位置は*⌊i/2⌋*で見つけることができます。 i ^ th ^ ノードの左の子と右の子は、位置 2i および 2i + 1 にあります。

バイナリヒープは、順序付けプロパティに基づいて max-heap または min-heap としてさらに分類できます。

最大ヒープ

このヒープでは、ノードのキー値は最上位の子のキー値以上です。

したがって、 _ H [Parent(i)]≥H [i] _

Max-Heap

最小ヒープ

平均ヒープでは、ノードのキー値は最下位の子のキー値以下です。

したがって、 _ H [Parent(i)]≤H [i] _

これに関連して、Max-Heapに関する基本的な操作を以下に示します。 ヒープ内の要素の挿入と削除には、要素の再配置が必要です。 したがって、 Heapify 関数を呼び出す必要があります。

Min-Heap

配列表現

完全な二分木は、レベル順序走査を使用して要素を格納する配列で表すことができます。

配列 H で表されるヒープ(以下に示す)を考えてみましょう。

配列表現

レベル順走査を使用して、開始インデックスを 0 と見なすと、要素は次のように配列に保持されます。

Index 0 1 2 3 4 5 6 7 8 …​
elements 70 30 50 12 20 35 25 4 8 …​

このコンテキストでは、ヒープの操作はMax-Heapに関して表されています。

インデックス i の要素の親のインデックスを見つけるには、次のアルゴリズム Parent(numbers []、i) が使用されます。

Algorithm: Parent (numbers[], i)
if i == 1
   return NULL
else
   [i/2]

インデックス i の要素の左の子のインデックスは、アルゴリズム Left-Child(numbers []、i) を使用して見つけることができます。

Algorithm: Left-Child (numbers[], i)
If 2 *i ≤ heapsize
   return [2* i]
else
   return NULL

インデックス i の要素の右の子のインデックスは、アルゴリズム Right-Child(numbers []、i) を使用して見つけることができます。

Algorithm: Right-Child (numbers[], i)
if 2 *i < heapsize
   return [2* i + 1]
else
   return NULL

DAA-挿入メソッド

ヒープに要素を挿入するには、最初に新しい要素が配列の最後の要素としてヒープの最後に追加されます。

この要素を挿入した後、ヒーププロパティに違反する可能性があるため、追加された要素をその親と比較し、追加された要素をレベルを上げて親と位置を交換することで、ヒーププロパティが修復されます。 このプロセスは percolation up と呼ばれます。

親がパーコレーション要素以上になるまで、比較が繰り返されます。

Algorithm: Max-Heap-Insert (numbers[], key)
heapsize = heapsize + 1
numbers[heapsize] = -∞
i = heapsize
numbers[i] = key
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i]
   exchange(numbers[i], numbers[Parent(numbers[], i)])
   i = Parent (numbers[], i)

分析

最初は、配列の最後に要素が追加されています。 ヒーププロパティに違反する場合、要素はその親と交換されます。 ツリーの高さは log n です。 操作の最大 log n 数を実行する必要があります。

したがって、この関数の複雑さは O(log n) です。

以下に示すように、新しい要素5を追加する必要がある最大ヒープを考えてみましょう。

新しい要素

最初は、この配列の最後に55が追加されます。

配列

挿入後、ヒーププロパティに違反します。 したがって、要素はその親と交換する必要があります。 スワップ後、ヒープは次のようになります。

スワップ

繰り返しますが、この要素はヒープのプロパティに違反しています。 したがって、親と交換されます。

スワップ

今、私たちは停止する必要があります。

DAA-ヒープ化メソッド

Heapifyメソッドは、 i ^ th ^ 要素の左右のサブツリーがヒーププロパティに従う配列の要素を再配置します。

Algorithm: Max-Heapify(numbers[], i)
leftchild := numbers[2i]
rightchild := numbers [2i + 1]
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i]
   largest := leftchild
else
   largest := i
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest]
   largest := rightchild
if largest ≠ i
   swap numbers[i] with numbers[largest]
   Max-Heapify(numbers, largest)

指定された配列がヒーププロパティに従わない場合、ヒープは次のアルゴリズム Build-Max-Heap(numbers []) に基づいて構築されます。

Algorithm: Build-Max-Heap(numbers[])
numbers[].size := numbers[].length
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1
   Max-Heapify (numbers[], i)

DAA-抽出メソッド

抽出メソッドは、ヒープのルート要素を抽出するために使用されます。 アルゴリズムは次のとおりです。

Algorithm: Heap-Extract-Max (numbers[])
max = numbers[1]
numbers[1] = numbers[heapsize]
heapsize = heapsize – 1
Max-Heapify (numbers[], 1)
return max

前述の同じ例を考えてみましょう。 次に、要素を抽出します。 このメソッドは、ヒープのルート要素を返します。

メソッド

ルート要素を削除すると、最後の要素がルート位置に移動します。

ルート要素

これで、Heapify関数が呼び出されます。 ヒープ化後、次のヒープが生成されます。

Heapify

DAA-バブルソート

バブルソートは基本的なソートアルゴリズムで、必要に応じて隣接する要素を繰り返し交換することで機能します。 交換が不要な場合、ファイルはソートされます。

これは、すべてのソートアルゴリズムの中で最も単純な手法です。

Algorithm: Sequential-Bubble-Sort (A)
fori← 1 to length [A] do
for j ← length [A] down-to i +1 do
   if A[A] < A[j - 1] then
      Exchange A[j] ↔ A[j-1]

実装

voidbubbleSort(int numbers[], intarray_size) {
   inti, j, temp;
   for (i = (array_size - 1); i >= 0; i--)
   for (j = 1; j <= i; j++)
      if (numbers[j - 1] > numbers[j]) {
         temp = numbers[j-1];
         numbers[j - 1] = numbers[j];
         numbers[j] = temp;
      }
}

分析

ここで、比較の数は

  • 1 + 2 + 3 + …​ +(n-1)= n _( n_-1)/2 = O(n ^ 2 ^)*

明らかに、グラフはバブルソートの _n ^ 2 ^ _ の性質を示しています。

このアルゴリズムでは、比較の数はデータセットに関係しません。 提供された入力要素がソート順か、逆順か、ランダムか。

メモリー要件

上記のアルゴリズムから、バブルソートが余分なメモリを必要としないことは明らかです。

Unsorted list:

|5 |2 |1 |4 |3 |7 |6

1 ^ st ^反復:

5 > 2 swap

|2 |5 |1 |4 |3 |7 |6

5 > 1 swap

|2 |1 |5 |4 |3 |7 |6

5 > 4 swap

|2 |1 |4 |5 |3 |7 |6

5 > 3 swap

|2 |1 |4 |3 |5 |7 |6

5 < 7 no swap

|2 |1 |4 |3 |5 |7 |6

7 > 6 swap

|2 |1 |4 |3 |5 |6 |7

2 ^ nd ^反復:

2 > 1 swap

|1 |2 |4 |3 |5 |6 |7

2 < 4 no swap

|1 |2 |4 |3 |5 |6 |7

4 > 3 swap

|1 |2 |3 |4 |5 |6 |7

4 < 5 no swap

|1 |2 |3 |4 |5 |6 |7

5 < 6 no swap

|1 |2 |3 |4 |5 |6 |7

3 ^ rd ^、4 ^ th ^、5 ^ th ^、および6 ^ th ^の繰り返しに変更はありません。

最後に、

the sorted list is

|1 |2 |3 |4 |5 |6 |7

DAA-挿入ソート

挿入ソートは、数字を昇順または降順にソートする非常に簡単な方法です。 この方法は、増分方法に従います。 これは、ゲームのプレイ時にカードがどのようにソートされるかという手法と比較できます。

ソートする必要がある番号は、*キー*と呼ばれます。 挿入ソート方法のアルゴリズムは次のとおりです。

Algorithm: Insertion-Sort(A)
for j = 2 to A.length
   key = A[j]
   i = j – 1
   while i > 0 and A[i] > key
      A[i + 1] = A[i]
      i = i -1
   A[i + 1] = key

分析

このアルゴリズムの実行時間は、指定された入力に大きく依存します。

指定された数値がソートされている場合、このアルゴリズムは O(n) 時間で実行されます。 指定された数値が逆順の場合、アルゴリズムは O(n ^ 2 ^) 時間で実行されます。

Unsorted list:

|2 |13 |5 |18 |14

  • 1 ^ st ^反復:*

キー= a [2] = 13

a [1] = 2 <13

Swap, no swap

|2 |13 |5 |18 |14

  • 2 ^ nd ^反復:*

キー= a [3] = 5

a [2] = 13> 5

Swap 5 and 13

|2 |5 |13 |18 |14

次に、a [1] = 2 <13

Swap, no swap

|2 |5 |13 |18 |14

  • 3 ^ rd ^反復:*

キー= a [4] = 18

a [3] = 13 <18

a [2] = 5 <18

a [1] = 2 <18

Swap, no swap

|2 |5 |13 |18 |14

  • 4 ^ th ^反復:*

キー= a [5] = 14

a [4] = 18> 14

Swap 18 and 14

|2 |5 |13 |14 |18

次に、a [3] = 13 <14

a [2] = 5 <14

a [1] = 2 <14

So, no swap

|2 |5 |13 |14 |18

最後に、

the sorted list is

|2 |5 |13 |14 |18

DAA-選択ソート

このタイプのソートは、エレメントを繰り返しソートすることで機能するため、*選択ソート*と呼ばれます。 次のように機能します。最初に配列の最小値を見つけて最初の位置の要素と交換し、次に2番目に小さい要素を見つけて2番目の位置の要素と交換し、配列全体がこのようになるまで続けますソート済み。

Algorithm: Selection-Sort (A)
fori ← 1 to n-1 do
   min j ← i;
   min x ← A[i]
   for j ←i + 1 to n do
      if A[j] < min x then
         min j ← j
         min x ← A[j]
   A[min j] ← A [i]
   A[i] ← min x

選択ソートは、最も単純なソート手法の1つであり、小さなファイルに対して非常にうまく機能します。 各アイテムが実際に一度だけ移動されるため、非常に重要なアプリケーションがあります。

セクションの並べ替えは、非常に大きなオブジェクト(レコード)と小さなキーを持つファイルの並べ替えに適した方法です。 配列が既に降順でソートされていて、昇順でソートしたい場合、最悪のケースが発生します。

それにもかかわらず、選択ソートアルゴリズムに必要な時間は、ソートされる配列の元の順序にあまり敏感ではありません: A [j] _ < '_min x' がすべての場合に正確に同じ回数実行されるかどうかのテスト。

選択ソートは、配列のソートされていない部分の最小要素を見つけるために、ほとんどの時間を費やします。 選択ソートとバブルソートの類似性を明確に示しています。

  • バブルソートは、各段階で最大の残りの要素を選択しますが、配列のソートされていない部分に何らかの順序を付与するための労力を浪費します。

  • 選択ソートは、最悪の場合と平均的な場合の両方で2次であり、追加のメモリを必要としません。

    *_1_* から *_n-1_* までの各 *_i_* には、1回の交換と *_n-i_* の比較があるため、合計で *_n-1_* の交換と
    *_(n − 1)+(n − 2)+ ... + 2 + 1 = n(n − 1)/2_* 比較。

これらの観察結果は、入力データが何であっても保持されます。

最悪の場合、これは2次の場合がありますが、平均的な場合、この量は O(n log n) です。 これは、* Selectionソートの実行時間が入力にまったく影響されないことを意味します*。

実装

Void Selection-Sort(int numbers[], int array_size) {
   int i, j;
   int min, temp;
   for (i = 0; I < array_size-1; i++) {
      min = i;
      for (j = i+1; j < array_size; j++)
         if (numbers[j] < numbers[min])
            min = j;
      temp = numbers[i];
      numbers[i] = numbers[min];
      numbers[min] = temp;
   }
}

Unsorted list:

|5 |2 |1 |4 |3

1 ^ st ^反復:

最小= 5

2 <5、最小= 2

1 <2、最小= 1

4> 1、最小= 1

3> 1、最小= 1

Swap 5 and 1

|1 |2 |5 |4 |3

2 ^ nd ^反復:

最小= 2

2 <5、最小= 2

2 <4、最小= 2

2 <3、最小= 2

No Swap

|1 |2 |5 |4 |3

3 ^ rd ^反復:

最小= 5

4 <5、最小= 4

3 <4、最小= 3

Swap 5 and 3

|1 |2 |3 |4 |5

4 ^ th ^反復:

最小= 4

4 <5、最小= 4

No Swap

|1 |2 |3 |4 |5

最後に、

the sorted list is

|1 |2 |3 |4 |5

DAA-クイックソート

分割統治の原理で使用されます。 クイックソートは、実装するのが難しくないため、多くの状況で選択されるアルゴリズムです。 これは適切な汎用ソートであり、実行中に比較的少ないリソースを消費します。

利点

  • 小さな補助スタックのみを使用するため、インプレースです。
  • n 個のアイテムをソートするには、 _ n(log n)_ 時間だけが必要です。
  • 非常に短い内部ループがあります。
  • このアルゴリズムは徹底的な数学的分析を受けており、パフォーマンスの問題について非常に正確な声明を出すことができます。

デメリット

  • 再帰的です。 特に、再帰が利用できない場合、実装は非常に複雑です。
  • 最悪の場合、2次(つまりn2)時間を必要とします。
  • 壊れやすい、つまり 実装の単純な間違いは、気付かれずにパフォーマンスが低下する可能性があります。

クイックソートは、特定の配列 A [p …​ r] _ 2つの空でないサブ配列 _A [p …​ q] _' および _A [q + 1 …​ r] _ * A [p …​のすべてのキー q] _ は、 ' A [q + 1 …​のすべてのキー以下です r] _

次に、2つのサブ配列は、クイックソートの再帰呼び出しによってソートされます。 パーティションの正確な位置は、指定された配列に依存し、インデックス q はパーティション化手順の一部として計算されます。

Algorithm: Quick-Sort (A, p, r)
if p < r then
   q Partition (A, p, r)
   Quick-Sort (A, p, q)
   Quick-Sort (A, q + r, r)

配列全体をソートするには、最初の呼び出しが Quick-Sort(A、1、length [A]) であることに注意してください。

最初のステップとして、クイックソートは、ピボットとしてソートされる配列内のアイテムの1つを選択します。 次に、配列はピボットの両側で分割されます。 ピボット以下の要素は左に移動し、ピボット以上の要素は右に移動します。

アレイの分割

分割手順は、サブアレイをその場で再配置します。

Function: Partition (A, p, r)
x ← A[p]
i ← p-1
j ← r+1
while TRUE do
   Repeat j ← j - 1
   until A[j] ≤ x
   Repeat i← i+1
   until A[i] ≥ x
   if i < j then
      exchange A[i] ↔ A[j]
   else
      return j

分析

Quick-Sortアルゴリズムの最悪の複雑さは O(n ^ 2 ^) です。 ただし、この手法を使用すると、一般的には O(n log n) 時間で出力が得られます。

DAA-基数ソート

  • 基数ソート*は、多くの人が名前の大きなリストをアルファベット順に並べるときに直感的に使用する小さな方法です。 具体的には、名前のリストは最初に各名前の最初の文字に従ってソートされます。つまり、名前は26のクラスに配置されます。

直観的には、数字を最上位桁でソートしたい場合があります。 ただし、Radixソートは、最下位桁を最初にソートすることにより、直感に反して機能します。 最初のパスでは、すべての数値が最下位桁でソートされ、配列に結合されます。 次に、2回目のパスで、数値全体が2番目に下位の桁で再度ソートされ、配列などに結合されます。

Algorithm: Radix-Sort (list, n)
shift = 1
for loop = 1 to keysize do
   for entry = 1 to n do
      bucketnumber = (list[entry].key/shift) mod 10
      append (bucket[bucketnumber], list[entry])
   list = combinebuckets()
   shift = shift * 10

分析

各キーは、最長キーの各桁(またはキーがアルファベットの場合は文字)ごとに1回調べられます。 したがって、最長キーに m 桁があり、 n キーがある場合、基数ソートの順序は* O(m.n)*です。

ただし、これらの2つの値を見ると、キーの数と比較すると、キーのサイズは比較的小さくなります。 たとえば、6桁のキーがある場合、100万件の異なるレコードを作成できます。

ここで、キーのサイズは重要ではなく、このアルゴリズムは線形複雑度* O(n)*であることがわかります。

次の例は、基数ソートが7つの3桁の数値でどのように動作するかを示しています。

Input 1st Pass 2nd Pass 3rd Pass
329 720 720 329
457 355 329 355
657 436 436 436
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839

上記の例では、最初の列が入力です。 残りの列は、次第に有効数字の位置で連続してソートした後のリストを示しています。 Radixソートのコードは、 _ n_ 要素の配列 A の各要素が d 桁であると想定しています。ここで、桁 1 は最下位桁で、 _ d_ は最上位桁です。

確定的vs. 非決定的計算

クラス P および NP を理解するには、最初に計算モデルを知っておく必要があります。 したがって、この章では、2つの重要な計算モデルについて説明します。

決定論的計算とクラスP

決定論的チューリングマシン

これらのモデルの1つは、決定論的な1テープチューリングマシンです。 このマシンは、有限状態制御、読み取り/書き込みヘッド、および無限シーケンスの双方向テープで構成されています。

以下は、決定論的な1テープチューリングマシンの概略図です。

確定的チューリングマシン

決定論的なチューリングマシンのプログラムは、次の情報を指定します-

  • テープシンボルの有限セット(入力シンボルと空白シンボル)
  • 状態の有限セット
  • 遷移関数

アルゴリズム分析では、決定論的な1つのテープチューリングマシンによって多項式時間で問題を解決できる場合、問題はPクラスに属します。

非決定的計算とクラスNP

非決定性チューリングマシン

計算問題を解決するための別のモデルは、非決定性チューリングマシン(NDTM)です。 NDTMの構造はDTMに似ていますが、ここでは推測モジュールと呼ばれる1つの追加モジュールがあり、1つの書き込み専用ヘッドに関連付けられています。

以下は概略図です。

非決定性チューリングマシン

問題が非決定的チューリングマシンによって多項式時間で解ける場合、問題はNPクラスに属します。

DAA-最大クリーク

無向グラフでは、*クリーク*は与えられたグラフの完全な部分グラフです。 完全なサブグラフとは、このサブグラフのすべての頂点がこのサブグラフの他のすべての頂点に接続されていることを意味します。

最大クリーク問題は、グラフの最大クリークを見つける計算上の問題です。 マックスクリークは、多くの実世界の問題で使用されています。

頂点が人々のプロファイルを表し、エッジがグラフの相互の知人を表すソーシャルネットワーキングアプリケーションを考えてみましょう。 このグラフでは、クリークはすべてがお互いを知っている人々のサブセットを表します。

最大のクリークを見つけるには、すべてのサブセットを体系的に検査できますが、この種のブルートフォース検索は、数十以上の頂点を含むネットワークでは時間がかかりすぎます。

Algorithm: Max-Clique (G, n, k)
S := Φ
for i = 1 to k do
   t := choice (1…n)
   if t Є S then
      return failure
   S := S ∪ t
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do
   if (i, j) is not a edge of the graph then
      return failure
return success

分析

Max-Clique問題は非決定的なアルゴリズムです。 このアルゴリズムでは、最初に k 個の異なる頂点のセットを決定し、次にこれらの頂点が完全なグラフを形成するかどうかをテストします。

この問題を解決する多項式時間決定論的アルゴリズムはありません。 この問題はNP完全です。

次のグラフをご覧ください。 ここでは、頂点2、3、4、および6を含むサブグラフが完全なグラフを形成します。 したがって、このサブグラフは*クリーク*です。 これは提供されたグラフの最大の完全なサブグラフであるため、* 4-クリーク*です。

最大クリーク

DAA-頂点カバー

無向グラフ G =(V、E) の頂点カバーは、頂点 V ^ '^⊆V のサブセットであるため、エッジ (u、v) が* G_のエッジである場合*、次に '_Vu または V ^ '^ __v' 、あるいはその両方。

特定の無向グラフで最大サイズの頂点カバーを見つけます。 この最適な頂点カバーは、NP完全問題の最適化バージョンです。 ただし、最適に近い頂点カバーを見つけることはそれほど難しくありません。

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G]
while E' is not empty do
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v}
   Remove from E' every edge incident on either u or v
return c

与えられたグラフのエッジのセットは-

*\ {(1,6)、(1,2)、(1,4)、(2,3)、(2,4)、(6,7)、(4,7)、(7,8) 、(3,8)、(3,5)、(8,5)}*

エッジの設定

ここで、任意のエッジ(1,6)を選択することから始めます。 頂点1または6に付随するすべてのエッジを削除し、カバーにエッジ(1,6)を追加します。

任意のエッジ

次のステップでは、ランダムに別のエッジ(2,3)を選択しました

Another Edge

次に、別のエッジ(4,7)を選択します。

別のエッジを選択

別のエッジ(8,5)を選択します。

エッジ

したがって、このグラフの頂点カバーは\ {1,2,4,5}です。

分析

このアルゴリズムの実行時間は O(V + E) であり、隣接リストを使用して _E ^ '^ _ を表すことは簡単にわかります。

DAA-P&NPクラス

コンピューターサイエンスでは、いくつかの値を最大化または最小化することが目的である多くの問題が解決されますが、他の問題では解決策があるかどうかを見つけようとします。 したがって、問題は次のように分類することができます-

最適化の問題

最適化の問題は、目的がいくつかの値を最大化または最小化することです。 例えば、

  • 特定のグラフに色を付けるために必要な色の最小数を見つける。
  • グラフ内の2つの頂点間の最短経路を見つける。

決定問題

答えが「はい」または「いいえ」である多くの問題があります。 これらのタイプの問題は、*決定問題*として知られています。 例えば、

  • 特定のグラフを4色のみで着色できるかどうか。
  • グラフでハミルトニアンサイクルを見つけることは決定問題ではありませんが、グラフをチェックすることはハミルトニアンであるかどうかは決定問題です。

言語とは?

すべての決定問題には、yesまたはnoの2つの答えしかありません。 したがって、特定の入力に対して「はい」と答えた場合、決定問題は言語に属する可能性があります。 言語は、答えが「はい」である入力の全体です。 前の章で説明したアルゴリズムのほとんどは、*多項式時間アルゴリズム*です。

入力サイズ n の場合、アルゴリズムの最悪の時間複雑度が O(n ^ k ^)k は定数)の場合、アルゴリズムは多項式時間アルゴリズムです。

マトリックスチェーン乗算、単一ソース最短パス、全ペア最短パス、最小スパニングツリーなどのアルゴリズム 多項式時間で実行します。 ただし、巡回セールスマン、最適なグラフの色付け、ハミルトニアンサイクル、グラフ内の最長パスの検出、多項式時間アルゴリズムが不明なブール式を満たすなど、多くの問題があります。 これらの問題は、 NP-Complete 問題と呼ばれる興味深い状態の問題に属し、そのステータスは不明です。

この文脈では、次のように問題を分類することができます-

Pクラス

クラスPは、多項式時間で解ける問題で構成されます。 これらの問題は、 k が一定の場合、 _ O(n ^ k ^)_ を最悪の場合に時間内に解決できます。

これらの問題は tractable と呼ばれ、他の問題は intractableまたはsuperpolynomial と呼ばれます。

形式的には、アルゴリズムが時間 O(p(n)) でサイズ n の任意のインスタンスを解決できる多項式 p(n) が存在する場合、アルゴリズムは多項式時間アルゴリズムです。

解決に &ohm;(n ^ 50 ^) 時間を要する問題は、本質的に大きな n では扱いにくいです。 ほとんどの既知の多項式時間アルゴリズムは、 _ O(n ^ k ^)'_k' のかなり低い値で実行します。

多項式時間アルゴリズムのクラスを考慮することの利点は、すべての合理的な*決定論的な単一プロセッサ計算モデル*が、せいぜい多項式スローdで互いにシミュレートできることです。

NPクラス

クラスNPは、多項式時間で検証可能な問題で構成されます。 NPは、わずかな追加情報を使用して、主張された回答の正確性を簡単に確認できる意思決定問題のクラスです。 したがって、解決策を見つける方法を求めているのではなく、申し立てられた解決策が本当に正しいことを検証するだけです。

このクラスのすべての問題は、徹底的な検索を使用して指数関数的に解決できます。

P対NP

決定論的多項式時間アルゴリズムによって解決可能なすべての決定問題は、多項式時間非決定論的アルゴリズムによっても解決可能です。

Pのすべての問題は多項式時間アルゴリズムで解決できますが、_NP-P_のすべての問題は難解です。

*_P = NP_* かどうかは不明です。 しかし、NPには、Pに属している場合、P = NPであることが証明できるという性質を持つ多くの問題が知られています。
*_P≠NP_* の場合、PにもNP-Completeにもない問題がNPにあります。

問題の解決策を見つけやすい場合、問題はクラス P に属します。 問題は、非常に退屈な解決策を簡単に確認できる場合、 NP に属します。

DAA-クックの定理

スティーブンクックは、彼の論文「定理証明手順の複雑さ」で4つの定理を提示しました。 これらの定理を以下に示します。 この章では多くの未知の用語が使用されていることを理解していますが、すべてを詳細に議論する範囲はありません。

以下は、スティーブンクックによる4つの定理です。

定理-1

文字列のセット S が多項式時間内に非決定論的なチューリングマシンによって受け入れられる場合、 S は\ {DNFトートロジー}に対してP簡約可能です。

定理-2

次のセットはペアで互いにP簡約可能です(したがって、それぞれの多項式の難易度は同じです):\ {tautologies}、\ {DNF tautologies}、D3、\ {sub-graph pairs}。

定理-3

  • タイプ QT〜Q〜(k) の場合、$ \ mathbf \ {\ frac \ {T _ \ {Q}(k)} \ {\ frac \ {\ sqrt \ {k}} \ {(log \:k)^ 2}}} $は無制限です
  • $ T _ \ {Q}(k)\ leqslant 2 ^ \ {k(log \:k)^ 2} $のような Q タイプの T〜Q〜(k) があります

定理-4

文字列のセットSが時間内に非決定的マシンによって受け入れられる場合 T(n)= 2 ^ n ^ _ 、および _T〜Q〜(k)' が正直な場合(つまり、 Q' 型のリアルタイムカウント可能)関数の場合、定数 K が存在するため、 S は、 _ T〜Q〜(K8 ^ n ^)_ 以内に決定論的なマシンによって認識されます。

  • 最初に、彼は多項式時間の縮約可能性の重要性を強調しました。 これは、ある問題から別の問題への多項式時間の削減がある場合、2番目の問題からの多項式時間アルゴリズムを、最初の問題に対する対応する多項式時間アルゴリズムに変換できることを意味します。
  • 第二に、彼は非決定論的なコンピューターによって多項式時間で解くことができる決定問題のクラスNPに注意を集中しました。 扱いにくい問題のほとんどは、このクラスNPに属します。
  • 第三に、NPのある特定の問題には、NPの他のすべての問題を多項式で縮約できるという性質があることを証明しました。 充足可能性の問題が多項式時間アルゴリズムで解決できる場合、NPのすべての問題も多項式時間で解決できます。 NPの問題が難治性である場合、充足可能性の問題は難治性でなければなりません。 したがって、充足可能性の問題はNPで最も難しい問題です。
  • 4番目に、クックは、NPの他の問題が、NPの最も難しいメンバーであるというこの特性を充足可能性の問題と共有するかもしれないと示唆しました。

NPハードクラスとNP完全クラス

問題は、NPにあり、NPの問題と同様に*困難*である場合、クラスNPCにあります。 NP内のすべての問題が、NP自体に存在しない場合でも、NP時間の多項式時間還元可能であれば、問題は* NP困難*です。

NP-hard

これらの問題のいずれかに多項式時間アルゴリズムが存在する場合、NPのすべての問題は多項式時間で解決可能になります。 これらの問題は NP-complete と呼ばれます。 NP完全性の現象は、理論的および実用的な理由の両方で重要です。

NP完全性の定義

言語 B は、2つの条件を満たす場合、 _ NP-complete_ です。

  • B はNPにあります
  • NPのすべての A は、 B に還元可能な多項式時間です。

言語が2番目のプロパティを満たしているが、必ずしも最初のプロパティを満たしているわけではない場合、言語 BNP-Hard として知られています。 非公式には、チューリングが B に還元する* NP-完全*問題 A が存在する場合、検索問題 B は* NP-ハード*です。

NPハードの問題は、 P = NP になるまで、多項式時間で解決できません。 問題がNPCであることが判明した場合、そのための効率的なアルゴリズムを見つけるために時間を浪費する必要はありません。 代わりに、設計近似アルゴリズムに焦点を当てることができます。

NP完全問題

以下は、NP時間問題の一部であり、多項式時間アルゴリズムは知られていません。

  • グラフにハミルトニアンサイクルがあるかどうかを判断する
  • ブール式が充足可能かどうかの判定など。

NPハード問題

次の問題はNPハードです

  • 回路充足可能性の問題
  • セットカバー
  • 頂点カバー
  • 巡回セールスマン問題

これに関連して、TSPがNP完全であることを説明します。

TSPはNP完全です

巡回セールスマン問題は、セールスマンと一連の都市で構成されています。 セールスマンは、特定の都市から始まり、同じ都市に戻る各都市を訪問する必要があります。 問題の課題は、巡回セールスマンが旅行の全長を最小限にしたいということです

証明

*_TSPがNP-Complete_* であることを証明するには、最初に *_TSPがNP_* に属していることを証明する必要があります。 TSPでは、ツアーを見つけ、ツアーに各頂点が1回含まれていることを確認します。 次に、ツアーのエッジの合計コストが計算されます。 最後に、コストが最小かどうかを確認します。 これは、多項式時間で完了することができます。 したがって、 *_ TSPはNP_* に属します。

次に、 _ TSPがNP-hard_ であることを証明する必要があります。 これを証明する1つの方法は、 ハミルトニアンサイクル≤〜p〜TSP を示すことです(ハミルトニアンサイクルの問題はNPcompleteであることがわかっています)。

*_G =(V、E)_* をハミルトニアンサイクルのインスタンスと仮定します。

したがって、TSPのインスタンスが構築されます。 完全なグラフ G ^ '^ =(V、E ^' ^) を作成します。ここで、

E ^ \ {'} = \ lbrace(i、j)\ colon i、j \ in V \:\:and \:i \ neq j

したがって、コスト関数は次のように定義されます-

t(i、j)= \ begin \ {cases} 0&if \:(i、j)\:\ in E \\ 1&else \ end \ {cases}

ここで、ハミルトニアンサイクル hG に存在するとします。 h の各エッジのコストは、各エッジが E に属するため、 _ G ^ '^ '0 であることは明らかです。 したがって、 ' G ^ '^ '_h' のコストは 0 です。 したがって、グラフ G のハミルトニアンサイクルがある場合、グラフ _G ^ '^ _ のコストは 0 になります。

逆に、 _ G ^ '^ ' のツアーのコストは最大で 0_h ^' ^ _ であると仮定します。 _E ^ '^ _ のエッジのコストは、定義により 0 および 1 です。 したがって、 ' h ^ '^ ' のコストは 0 であるため、各エッジのコストは 0 でなければなりません。 したがって、 ' h ^ '^ ' には _E' のエッジのみが含まれると結論付けます。

したがって、 _ G ^ '^ ' のコストツアーが最大で 0 である場合に限り、 ' G_ がハミルトニアンサイクルを持つことを証明しました。 TSPはNP完全です。

DAA-ヒルクライミングアルゴリズム

前の章で説明したアルゴリズムは体系的に実行されます。 目標を達成するには、最適なソリューションを見つけるために、以前に探索したソリューションへのパスを1つ以上保存する必要があります。

多くの問題では、目標への道は無関係です。 たとえば、Nクイーンの問題では、クイーンの最終的な構成や、クイーンが追加される順序を気にする必要はありません。

山登り

ヒルクライミングは、特定の最適化の問題を解決する手法です。 この手法では、次善のソリューションから開始し、ある条件が最大になるまでソリューションを繰り返し改善します。

ヒルクライミング

最適ではない解決策から始めるという考えは、丘のふもとから始めることと比較され、解決策の改善は丘を登るのと比較され、最終的に何らかの条件を最大化することは丘の頂上に達することと比較されます。

したがって、山登り技術は、次の段階とみなすことができます-

  • 問題の制約に従う準最適なソリューションの構築
  • ソリューションを段階的に改善する
  • 改善が不可能になるまでソリューションを改善する

ヒルクライミング技術は、主に計算が難しい問題を解決するために使用されます。 現在の状態とその直後の状態のみを調べます。 したがって、この手法は検索ツリーを維持しないため、メモリ効率が高くなります。

Algorithm: Hill Climbing
Evaluate the initial state.
Loop until a solution is found or there are no new operators left to be applied:
   - Select and apply a new operator
   - Evaluate the new state:
      goal -→ quit
      better than current state -→ new current state

反復的な改善

反復改善法では、すべての反復で最適なソリューションに向かって前進することにより、最適なソリューションが達成されます。 ただし、この手法では極大値が発生する場合があります。 この状況では、より良い解決策のための近くの州はありません。

この問題はさまざまな方法で回避できます。 これらの方法の1つは、シミュレーテッドアニーリングです。

ランダム再起動

これは、局所最適の問題を解決する別の方法です。 この手法は、一連の検索を実行します。 毎回、ランダムに生成された初期状態から開始します。 したがって、実行された検索のソリューションを比較して、最適なソリューションまたはほぼ最適なソリューションを取得できます。

登山技術の問題

ローカルマキシマ

ヒューリスティックが凸でない場合、ヒルクライミングはグローバルな最大値ではなくローカルな最大値に収束する可能性があります。

尾根と路地

ターゲット関数が狭い尾根を作成する場合、登山者はジグザグで尾根を登るか、路地を下ることしかできません。 このシナリオでは、登山者は非常に小さなステップを踏む必要があり、目標を達成するためにより多くの時間を必要とします。

高原

探索空間がフラットであるか、またはターゲット関数によって返される値が近くの領域に対して返される値と区別できないほど十分に平坦である場合、プラトーが発生します。

登山技術の複雑さ

この手法は、現在の状態のみを調べるため、スペースに関連する問題の影響を受けません。 以前に探索されたパスは保存されません。

ランダムリスタートヒルクライミングテクニックのほとんどの問題では、多項式時間で最適なソリューションを実現できます。 ただし、NP完全問題の場合、計算時間は局所的な最大数に基づいて指数関数的になります。

ヒルクライミング技術の応用

ヒルクライミング技術は、ネットワークフロー、巡回セールスマン問題、8クイーン問題、集積回路設計など、現在の状態が正確な評価関数を可能にする多くの問題を解決するために使用できます。

ヒルクライミングは帰納的学習法でも使用されます。 この手法は、チーム内の複数のロボット間の調整のためにロボット工学で使用されます。 この手法が使用される他の多くの問題があります。

この手法は、巡回セールスマンの問題を解決するために適用できます。 最初に、すべての都市を一度だけ訪問する初期ソリューションが決定されます。 したがって、ほとんどの場合、この初期ソリューションは最適ではありません。 この解決策でさえ非常に貧弱な場合があります。 Hill Climbingアルゴリズムは、このような初期ソリューションから始まり、反復的な方法で改善を行います。 最終的には、はるかに短いルートが取得される可能性があります。