私はコンピュータサイエンス学士です。私は決勝戦のために勉強しています。私は、様々な動的プログラミングのタイプの問題を抱えていた問題を見つけました。ランダム化アルゴリズム確率最大化
効率的なランダム化アルゴリズムAが与えられ、独立したセットが返されます。このアルゴリズムは、確率が少なくとも1 /（n^3）の最大独立集合を返します。ここで、nはグラフの頂点の数です。少なくとも1/2の確率で最大のセットを返す、Aを使って別のアルゴリズムを提案する。
私は無作為アルゴリズムを研究しましたが、これは単純な実装のように思えます。 A n^3回実行すると、最大独立集合が1に近い確率が得られます。それをn^3/2回実行すると望ましい効果が得られると言えますか？私はこれをもっと難しくしようとしていますか？どんな助けもありがとうございます。
正確ではないが、ランの1つが正解を返す確率は、少なくとも1/n^3です。つまり、1回の実行で間違った答えが得られる確率は（1-1/n^3）です。つまり、M回実行した後に正解を得る確率は1-（1-1/n^3）^ Mです。
e (Wikipedia link)の式を思い出してください。n^3回実行すると、確率は1/2よりも大きくなります（1に近似はしませんが）。ちょうど1/2 - （n^3）* ln（2）になるまでの正確なラン数。
これは私が探していたものです。ありがとうございました。私は私の確率のルールで少し錆びている。 – Championcake
私は最大の独立したセットを研究していないので、あまりにも多くの助けを与えることはできません。ただし、実行時間を要求する前にまずアルゴリズムを書き出す必要があります。
n^3のアルゴリズムAを実行すると、n^3の最大独立集合が得られます。ただし、最大値を1つだけ戻す必要があります。それらのn^3の中の正しいものをどうやって見つけ出すのですか？ここでは、あなたの質問に欠けている検証アルゴリズムが必要な場合があります。
問題自体（最大独立セット）によっては、O（n^3）よりもはるかに少ないランニング数を必要とする正しい最大独立セットを見つけるのに十分な情報を得ることができます。
この質問をする間違ったサイト... –