ランダム化されたアルゴリズムを使用することができますか？

Question

ランダムなアルゴリズムは間違った答えを与える可能性があります。例えば、グラフの最小カット問題を解決するために収縮アルゴリズムを使用すると、アルゴリズムn^2 * ln（n）回実行する必要があります。正解は最大1/nです。失敗の可能性がどれほど小さいかにかかわらず、その答えは間違っている可能性があります。そもそも

Answer 1

は、私はあなたが乱択アルゴリズムの異なるクラスを区別する必要があると思う：

1. Monte Carlo algorithmはランダムw.r.t.あるアルゴリズムであり、正しさ。あなたの質問からランダム化されたmin-cutアルゴリズムは、そのようなアルゴリズムの例です。

2. Las Vegas algorithmはランダムw.r.tであるアルゴリズムです。実行時間。たとえば、無作為化されたクイックソートは、そのようなアルゴリズムです。

質問にモンテカルロアルゴリズムがあると思われます。それはecomonic theory of utilityのようなものに基づいているため

---

モンテカルロアルゴリズムはあなたに適しているかどうかの問題は、おそらく、客観的にはお答えできません。 2つのアルゴリズム、とB、またはBの各呼び出しを考えると、いくつかの時間トンを取り、あなたにその正しさCある結果を提供します。ユーティリティU（T、C）は確率変数であり、そしてだけがの分布U （T、C）が優れているか悪いよりU _B（T、C）かどうかを決定することができます。アルゴリズムは二倍の速としてBを実行しますが、確率1E-6でERRSいくつかの例には、これらのウェブサイト上で好みの推奨事項がある場合は

1. は、それがためにそれだけの価値があるかもしれませんまれにクライアントが間違った推奨を取得するリスクで、競合他社の2倍の反応を示すウェブサイトを持つことができます。

2. これらは、原子炉（TemplateTypedefさんのコメントから借りる）のための制御システムがある場合は、故障のわずかなチャンスが倍の速（例えば、あなたはおそらくプロセッサでより良い投資になる時間節約価値はないかもしれませんより遅いアルゴリズムを実行する）。

上記の2つの例は、2つの選択肢のそれぞれが異なる設定に対して正しいことを示しています。実際、ユーティリティ理論は、明らかに間違っている選択肢の集合を示すことはめったにありません。しかしながら、書籍Randomized Algorithms by Motwani and Raghavanの紹介では、著者はに、モンテカルロアルゴリズムを回避するという誤った例を挙げています。 の確率はα（その価値は忘れてしまいます）です。したがって、おそらくαよりも低い確率の確率でモンテカルロアルゴリズムを実行することを回避することは、おそらく単純に不合理なことです。

Answer 2

アルゴリズムのプロパティを分析して、最適ではない回答のリスクがアプリケーションで耐えられるかどうかを判断する必要があります。 （答えはブール値である場合、「非最適では」と同じである「間違っている。」）

が最適に近く、妥当な時間で得られたのですいくつかの答えはずっとある場合のプログラミングの問題の多くの種類があります。が最適な回答よりも良好が遅すぎるまたは全くありませんです。

Traveling Salesmanの問題は一例です。あなたがウォルマートであり、毎晩各都市の配送ルートを計画する必要がある場合は、のルートを最適に近づけることは、ルートがないか、または2日後に得られる可能性が最も高いルートよりも優れています。

ランダム化されたアルゴリズムによって多くの種類の保証が提供されています。彼らはしばしば形error <= F(cost)を持っています。ここではerrorとcostはほとんど何でもあります。コストは、ランタイムで表現することができます。スペースもコストに見合うかもしれません。エラーは、間違った1/0答えの確率、最適な結果からの距離メトリック、誤ったコンポーネントの離散カウントなどである可能性があります。

多分間違った答えで生きなければならないことがあります。有用な選択肢はありません。ビッグナンバーの素数性テストはこのカテゴリにあります。多項式時間決定論的テストがありますが、実際のすべての目的に対して正しい答えを出す確率的テストよりもずっと遅いです。

例えば、True結果が常に正しいが、Falseが時間の50％間違っているブールランダム化関数を使用すると、かなり良い形になります。 （実際にはMiller-Rabinの素数検定がこれより優れています。）

アルゴリズムを40回実行することができます。実行のいずれかがFalseと表示された場合、答えはFalseであることがわかります。それらがすべて真であれば、真の答えがfalseの確率はおよそ2^40 = 1 /（1兆）です。

安全性が重要なアプリケーションであっても、これは良い結果になる可能性があります。一生のうちに落雷する可能性は、約1/10,000です。私たちは皆それと共に生きていて、もう一度考えることはしません。