Advanced Algorithm Lecture 2(高等アルゴリズムカリキュラムノート2)
2840 ワード
作者のブログ:CSDN:https://blog.csdn.net/u013031229ブログ園:https://www.cnblogs.com/fzyz999/マスタ:https://www.pig2earth.top/
目次 Contrast Algorithm Fast Cutアルゴリズム ランダムアルゴリズムの分類 複雑性クラス Contrast Algorithm Pick an edge uniformly at random Merge the endpoints of this edge Remove self-loops Repeat steps 1-3 until there are only two vertices remain.5The remaining edges form a candidate cut
Fast Cutアルゴリズム
構想:Constraastアルゴリズムの問題は成功確率が低すぎることにある.成功確率を高めることができれば、繰り返し回数を少なくすることができます.
成功率が低すぎる原因:最初はペアを選ぶ確率が高いが、後ろに行くほど小さくなる.
改善構想1:前のk輪だけを走って、後の残りの図は他の方法で1つのmin cutを解く.
改善構想2:一歩ごとの成功確率は異なり、後になるほど低くなる.したがって,毎回nステップをやり直す必要はなく,最後の成功確率の低い部分だけをやり直すことができる.
どのようにnの时に少なく缲り返すことができて、后ろの时多く缲り返しますか?エッジを選ぶたびに1回多く選択します.これは次のようなものです.
このように,k 3の場合はnの場合よりはるかに多く8雌を繰り返したことに相当する.しかし、このような拡張は指数級であり、複雑さが高すぎるという問題がある.指数級を避けるためには、もう一つの改善が必要です.
すなわち,n/cから初めてn/cに走り,その後n/cというノードを2回再走し,$n/c^2$に走るたびに指数成長を回避できる.
明らかにcの大きさは時間的複雑さと成功確率を決定する.cが大きいほど成功率は低いが,速度は速い.逆に,cが小さいほど成功確率は高くなるが,速度は遅くなる.
時間複雑度:$T(n)=2 T(frac{n}{c}+O(n^2)$
成功確率:$P(n)geqslant 1-(1-P(frac{n}{c})^2$,すなわち成功確率は$1-text{失敗確率}$
毎回2回繰り返すので失敗する確率は$(1-P(frac{n}{c})^2$
ランダムアルゴリズムの分類
ラスベガスアルゴリズムの結果は正しい に違いない.ですが、実行時間または他の計算リソースはランダムである可能性があります. 例えば、クイックソート モンテカルロアルゴリズム結果質量はランダムな であった.例えば、ランダム最小分割アルゴリズム 回数が多ければ多いほど正確な に近づく.
複雑性クラス
判定問題:出力がYesまたはNoの問題です.他の問題は一般的に1つの判定問題に変換することができる.例えば、最小割を求めることは、ある割が最小割であるかどうかを求めることと考えられる.
P問題:任意のP問題に対して多項式時間複雑度のアルゴリズムAが存在し,この判定問題の答えを与えることができる.
NP問題:多項式時間のアルゴリズムAが存在し,その問題の和の証拠yが存在し,アルゴリズムAはこの証拠に基づいて結果を判断することができる.つまり、多項式時間は検証できるとよく言われています.
その他複雑性類:EXP(指数時間内計算可能)、PSPASE(多項式空間)…
NP-hard問題:AがNPであり、Aが多項式時間で解ける場合、すべてのNP問題は多項式時間で解ける.
NP完全問題:AはNP-hardであり、AはNP問題に属する.つまりNP問題の中で最も難しい問題です.
RP(Randomized Polynomial time):ランダムアルゴリズムAが最悪の場合は多項式複雑度であり,答えがNoの場合は,必ず受け入れない.
co-RPがRPの反対の場合,正しい答えに対しては必ず受け入れるが,間違った答えに対しては,必ずしもそうではない.
推論:$RPsubseteq NP$、$coRPsubseteq coNP$.証明:ランダムアルゴリズム$A(x)$に対して、$r$がランダム数列である決定的アルゴリズム$A(x,r)$と考えられる.ランダムなアルゴリズムで、私たちはそれを使ったすべてのランダム数を抽出して、$r$を形成して、残りの部分は確定しました.
NPの定義によれば$r$は多項式であるため,$RP$は$NP$の定義を満たす.
BPP:二国間エラー、つまり両方にエラーがある可能性があります.
まとめ:$Psubseteq RPsubseteq NPsubseteq PP$かつ$Psubseteq coRPsubseteq coNPsubseteq PP$
つまり,ランダムアルゴリズムは現在多項式解法が見つからない問題を多項式時間ランダムアルゴリズムで解くことができる問題に変えることはできない.その役割は主に$O(n 3)$を$O(n 2)$にする可能性があることにある.
マルコフ不等式:$Pr(T_Ageq C)leqfrac{E(T_A)}{C}$
目次
Fast Cutアルゴリズム
構想:Constraastアルゴリズムの問題は成功確率が低すぎることにある.成功確率を高めることができれば、繰り返し回数を少なくすることができます.
成功率が低すぎる原因:最初はペアを選ぶ確率が高いが、後ろに行くほど小さくなる.
改善構想1:前のk輪だけを走って、後の残りの図は他の方法で1つのmin cutを解く.
改善構想2:一歩ごとの成功確率は異なり、後になるほど低くなる.したがって,毎回nステップをやり直す必要はなく,最後の成功確率の低い部分だけをやり直すことができる.
どのようにnの时に少なく缲り返すことができて、后ろの时多く缲り返しますか?エッジを選ぶたびに1回多く選択します.これは次のようなものです.
：
n #
k1 k1 # , k1=n-1
k2 k2 k2 k2 # , k2=k1-1
k3 k3 k3 k3 k3 k3 k3 k3 # , k3=k2-1
このように,k 3の場合はnの場合よりはるかに多く8雌を繰り返したことに相当する.しかし、このような拡張は指数級であり、複雑さが高すぎるという問題がある.指数級を避けるためには、もう一つの改善が必要です.
n #
k1 k1 # , k1=n/c
k2 k2 k2 k2 # , k2=k1/c
k3 k3 k3 k3 k3 k3 k3 k3 # , k3=k2/c
すなわち,n/cから初めてn/cに走り,その後n/cというノードを2回再走し,$n/c^2$に走るたびに指数成長を回避できる.
明らかにcの大きさは時間的複雑さと成功確率を決定する.cが大きいほど成功率は低いが,速度は速い.逆に,cが小さいほど成功確率は高くなるが,速度は遅くなる.
時間複雑度:$T(n)=2 T(frac{n}{c}+O(n^2)$
成功確率:$P(n)geqslant 1-(1-P(frac{n}{c})^2$,すなわち成功確率は$1-text{失敗確率}$
毎回2回繰り返すので失敗する確率は$(1-P(frac{n}{c})^2$
ランダムアルゴリズムの分類
ラスベガスアルゴリズム
複雑性クラス
判定問題:出力がYesまたはNoの問題です.他の問題は一般的に1つの判定問題に変換することができる.例えば、最小割を求めることは、ある割が最小割であるかどうかを求めることと考えられる.
P問題:任意のP問題に対して多項式時間複雑度のアルゴリズムAが存在し,この判定問題の答えを与えることができる.
NP問題:多項式時間のアルゴリズムAが存在し,その問題の和の証拠yが存在し,アルゴリズムAはこの証拠に基づいて結果を判断することができる.つまり、多項式時間は検証できるとよく言われています.
その他複雑性類:EXP(指数時間内計算可能)、PSPASE(多項式空間)…
NP-hard問題:AがNPであり、Aが多項式時間で解ける場合、すべてのNP問題は多項式時間で解ける.
NP完全問題:AはNP-hardであり、AはNP問題に属する.つまりNP問題の中で最も難しい問題です.
RP(Randomized Polynomial time):ランダムアルゴリズムAが最悪の場合は多項式複雑度であり,答えがNoの場合は,必ず受け入れない.
co-RPがRPの反対の場合,正しい答えに対しては必ず受け入れるが,間違った答えに対しては,必ずしもそうではない.
推論:$RPsubseteq NP$、$coRPsubseteq coNP$.証明:ランダムアルゴリズム$A(x)$に対して、$r$がランダム数列である決定的アルゴリズム$A(x,r)$と考えられる.ランダムなアルゴリズムで、私たちはそれを使ったすべてのランダム数を抽出して、$r$を形成して、残りの部分は確定しました.
NPの定義によれば$r$は多項式であるため,$RP$は$NP$の定義を満たす.
BPP:二国間エラー、つまり両方にエラーがある可能性があります.
まとめ:$Psubseteq RPsubseteq NPsubseteq PP$かつ$Psubseteq coRPsubseteq coNPsubseteq PP$
つまり,ランダムアルゴリズムは現在多項式解法が見つからない問題を多項式時間ランダムアルゴリズムで解くことができる問題に変えることはできない.その役割は主に$O(n 3)$を$O(n 2)$にする可能性があることにある.
マルコフ不等式:$Pr(T_Ageq C)leqfrac{E(T_A)}{C}$